我试图在寻找唯一排列的问题中使用回溯法。我写了这个:
def f(A, start, end):
if start == end - 1:
print(A)
else:
for idx in range(start, end):
if idx != start and A[idx] == A[start]:
continue
A[idx], A[start] = A[start], A[idx]
f(A, start + 1, end)
这个例子有效
A = [2, 3, 2]
f(A, 0, len(A))
[2, 3, 2]
[2, 2, 3]
[3, 2, 2]
这个不行
A = [2, 2, 1, 1]
f(A, 0, len(A))
[2, 2, 1, 1]
[2, 1, 2, 1]
[2, 1, 1, 2]
[2, 2, 1, 1] #unwanted duplicate!
[1, 2, 2, 1]
[1, 2, 1, 2]
[1, 1, 2, 2]
[1, 2, 2, 1]
[1, 2, 1, 2]
[2, 2, 1, 1]
[2, 1, 2, 1]
[2, 1, 1, 2]
[2, 2, 1, 1]
为什么结果中仍然有重复项？
最佳答案
在过滤中，您使用一对一检查。因此，但是从超过三个元素的那一刻起，这将不起作用。
这是因为，您可以在多次(实际)交换后获得相同的排列。例如:
[1 ,2(1),2(2),3 ] -> swap 1 with 3
[1 ,3, 2(2),2(1)] -> swap 1 with 2
[1 ,2(2),3 ,2(1)] -> swap 2 with 3
[1 ,2(2),2(1),3 ]
如您所见，排列是相同的(但两个 two 的来源不同)。所以我们间接交换了这两个。
不过，没必要搞得那么复杂。有两种方法可能适用于此:
- 对列表进行排序，并强制执行约束，即您只能发出字典顺序上比前一个更多的列表；和
- 首先计算出现次数(使用
Counter，然后确保根据计数器发出)。
后者将运行得更快，因为它不会生成必须忽略的排列。
一个示例实现可以是:
from collections import Counter
def f(lst):
def g(l,c,n):
if n <= 0:
yield tuple(l)
else:
for k,v in c.items():
if v > 0:
c[k] -= 1
l.append(k)
for cfg in g(l,c,n-1):
yield cfg
l.pop()
c[k] += 1
for cfg in g([],Counter(lst),len(lst)):
yield cfg
这给出:
>>> list(f([1,1,2,2]))
[(1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1)]
>>> list(f([1,1,2,2,3]))
[(1, 1, 2, 2, 3), (1, 1, 2, 3, 2), (1, 1, 3, 2, 2), (1, 2, 1, 2, 3), (1, 2, 1, 3, 2), (1, 2, 2, 1, 3), (1, 2, 2, 3, 1), (1, 2, 3, 1, 2), (1, 2, 3, 2, 1), (1, 3, 1, 2, 2), (1, 3, 2, 1, 2), (1, 3, 2, 2, 1), (2, 1, 1, 2, 3), (2, 1, 1, 3, 2), (2, 1, 2, 1, 3), (2, 1, 2, 3, 1), (2, 1, 3, 1, 2), (2, 1, 3, 2, 1), (2, 2, 1, 1, 3), (2, 2, 1, 3, 1), (2, 2, 3, 1, 1), (2, 3, 1, 1, 2), (2, 3, 1, 2, 1), (2, 3, 2, 1, 1), (3, 1, 1, 2, 2), (3, 1, 2, 1, 2), (3, 1, 2, 2, 1), (3, 2, 1, 1, 2), (3, 2, 1, 2, 1), (3, 2, 2, 1, 1)]
关于python - 使用回溯的唯一排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44161971/