从C到Python的回溯排列

Question

我要做一个程序，用回溯法给出n个数的所有排列。我用C语言完成了，效果很好，下面是代码：

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;
}

现在我必须用Python来写。以下是我所做的：

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)

我得到这个错误：

list assignment index out of range

在st[k]==st[i]。你知道吗

Answer 1

Python在itertools模块中有一个“置换”函数：

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

如果您需要自己编写代码（例如，如果这是家庭作业），问题如下：

Python列表没有预先确定的大小，因此不能仅将第10个元素设置为3。只能更改现有图元或将其添加到末尾。你知道吗

Python列表（和C数组）也从0开始。这意味着您必须使用st[0]而不是st[1]访问第一个元素。你知道吗

启动程序时，st的长度为0；这意味着您不能分配给st[1]，因为它不是结束。你知道吗

如果这让人困惑，我建议您改用st.append(element)方法，它总是添加到结尾。你知道吗

如果代码已经完成并且可以运行，我建议您转到code review stack exchange，因为还有很多事情需要改进。你知道吗