回溯排列列表

Question

我正在尝试排列列表，但我做不到，它进入了无限循环。我尝试了不同的方法，但不知何故，它唯一显示给我的是 1 2 3 ... 1 2 3 等

这是代码：

def prints(v,k):
    s = ''
    for i in range(k + 1):
        s += str(v[i]) + ' '
    print(s)   

def continuare(v,k):
    ok = True
    for i in range(k):
        if v[i] == v[k]:
            ok = False
            break
    return ok

def back(v,a):
    k = 0
    caut = False
    while k>-1:
        caut = False        
        pos = 0
        while pos < len(a) and caut == False:
                v[k] = a[pos]
                pos += 1
                if continuare(v,k):
                    caut = True
        if caut == False:
            k -= 1
        elif k == len(a) - 1:
            prints(v,k)
        else:
            k += 1


a = [1,2,3]
v = []
for x in range(len(a)):
    v.append(a[0])
back(v,a)

Answer 1

这是 http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ 的一个简单的 Python 转录：

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]

def permute(a, i, n):
    if i == n:
        print(a)
        return
    for j in range(i, n+1):
        swap(a, i, j)
        permute(a, i+1, n)
        swap(a, i, j)  # backtrack

def main():
    a = list('ABC')
    permute(a, 0, 2)

if __name__ == '__main__':
    main()

我宁愿让 permute 成为产生排列的生成器，main 在它们上面循环并打印它们，但这可能更接近 C 原始版本，因此更容易理解。请注意，一个区别是必须的：这里被排列的是一个列表，而不是 C 原始字符串中的字符串，因为字符串在 Python 中是不可变的（因此 swap 将需要完全不同的逻辑，返回"string with swapped characters" 而不是能够像 "backtracking" 逻辑要求的那样就地工作。

回溯排列列表

Backtracking permuting a list

python

algorithm

backtracking