用重复的元素生成列表的排列

在Python中,使用itertools模块生成列表的所有排列是非常简单的。 我有一个情况,我使用的列表只有两个字符(即“1122”)。 我想要生成所有独特的排列。

对于string“1122”,有6个独特的排列(1122,1212,1221等),但itertools.permutations将产生24个项目。 只logging独特的排列是很简单的,但是由于考虑了全部720个项目,所以收集这些排列所花费的时间会比所需要的长得多。

是否有一个函数或模块在产生排列时考虑重复的元素,所以我不必自己写?

这个网页看起来很有希望。

def next_permutation(seq, pred=cmp): """Like C++ std::next_permutation() but implemented as generator. Yields copies of seq.""" def reverse(seq, start, end): # seq = seq[:start] + reversed(seq[start:end]) + \ # seq[end:] end -= 1 if end <= start: return while True: seq[start], seq[end] = seq[end], seq[start] if start == end or start+1 == end: return start += 1 end -= 1 if not seq: raise StopIteration try: seq[0] except TypeError: raise TypeError("seq must allow random access.") first = 0 last = len(seq) seq = seq[:] # Yield input sequence as the STL version is often # used inside do {} while. yield seq[:] if last == 1: raise StopIteration while True: next = last - 1 while True: # Step 1. next1 = next next -= 1 if pred(seq[next], seq[next1]) < 0: # Step 2. mid = last - 1 while not (pred(seq[next], seq[mid]) < 0): mid -= 1 seq[next], seq[mid] = seq[mid], seq[next] # Step 3. reverse(seq, next1, last) # Change to yield references to get rid of # (at worst) |seq|! copy operations. yield seq[:] break if next == first: raise StopIteration raise StopIteration >>> for p in next_permutation([int(c) for c in "111222"]): ... print p ... [1, 1, 1, 2, 2, 2] [1, 1, 2, 1, 2, 2] [1, 1, 2, 2, 1, 2] [1, 1, 2, 2, 2, 1] [1, 2, 1, 1, 2, 2] [1, 2, 1, 2, 1, 2] [1, 2, 1, 2, 2, 1] [1, 2, 2, 1, 1, 2] [1, 2, 2, 1, 2, 1] [1, 2, 2, 2, 1, 1] [2, 1, 1, 1, 2, 2] [2, 1, 1, 2, 1, 2] [2, 1, 1, 2, 2, 1] [2, 1, 2, 1, 1, 2] [2, 1, 2, 1, 2, 1] [2, 1, 2, 2, 1, 1] [2, 2, 1, 1, 1, 2] [2, 2, 1, 1, 2, 1] [2, 2, 1, 2, 1, 1] [2, 2, 2, 1, 1, 1] >>> 

2017年8月12日

七年后,这是一个更好的algorithm(更清晰):

 from itertools import permutations def unique_perms(series): return {"".join(p) for p in permutations(series)} print(sorted(unique_perms('1122')))