python - 从 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 模块中有一个“排列”函数:

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因为还有很多东西可以改进。