从 C 回溯到 Python 的排列

Question

我必须编写一个程序，使用回溯给出 n 个数字的所有排列 {1,2,3..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 模块中有一个 "permutations" 函数：

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，因为还有很多可以改进的地方。

从 C 回溯到 Python 的排列

Permutation with backtraking from C to Python

c

python

algorithm

permutation

backtracking