Permutation with backtraking from C to Python

Question

I have to do a program that gives all permutations of n numbers {1,2,3..n} using backtracking. I managed to do it in C, and it works very well, here is the code:

int st[25], n=4;

int valid(int k)
{
    int i;
    for (i = 1; i <= k - 1; i++)
        if (st[k] == st[i])
            return 0;
    return 1;
}
void bktr(int k)
{
    int i;
    if (k == n + 1)
    {
        for (i = 1; i <= n; i++)
            printf("%d ", st[i]);
        printf("\n");
    }
    else
        for (i = 1; i <= n; i++)
        {
            st[k] = i;
            if (valid(k))
                bktr(k + 1);
        }
    }
int main()
{
    bktr(1);
    return 0;
}

Now I have to write it in Python. Here is what I did:

st=[]
n=4
def bktr(k):
    if k==n+1:
        for i in range(1,n):
            print (st[i])

    else:
        for i in range(1,n):
            st[k]=i
            if valid(k):
                bktr(k+1)
def valid(k):
    for i in range(1,k-1):
        if st[k]==st[i]:
            return 0
    return 1
bktr(1)

I get this error:

list assignment index out of range

at st[k]==st[i].

Answer 1

Python has a "permutations" functions in the itertools module:

import itertools
itertools.permutations([1,2,3])

If you need to write the code yourself (for example if this is homework), here is the issue:

Python lists do not have a predetermined size, so you can't just set e.g. the 10th element to 3. You can only change existing elements or add to the end.

Python lists (and C arrays) also start at 0. This means you have to access the first element with st[0], not st[1].

When you start your program, st has a length of 0; this means you can not assign to st[1], as it is not the end.

If this is confusing, I recommend you use the st.append(element) method instead, which always adds to the end.

If the code is done and works, I recommend you head over to code review stack exchange because there are a lot more things that could be improved.