回溯置换

Question

我试图改变一个列表，但我做不到，它会无限循环。我尝试了不同的方法，但不知怎么的，它只显示了12.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将需要完全不同的逻辑，返回“带有交换字符的字符串”，而不是能够像“回溯”逻辑所要求的那样就地工作）。在