これは、Pythonでリストのすべての順列を生成する方法に関する質問に関連しています
次の基準に一致するすべての順列を生成する方法：2つの順列が互いに逆の場合（つまり、[1,2,3,4]と[4,3,2,1]）、それらは等しいと見なされ、そのうちの1つだけが最終結果になるはずです。
例：
permutations_without_duplicates ([1,2,3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
一意の整数を含むリストを並べ替えています。
結果として生じる順列の数が多くなるので、可能であればPythonのジェネレーターを使用したいと思います。
編集：可能であれば、すべての順列のリストをメモリに保存したくありません。
SilentGhostの提案に対する素晴らしいフォローアップがあります-コメントの余白が狭すぎてコードを含めることができないため、別の回答を投稿します:-)
itertools.permutations組み込み（2.6以降）で高速です。すべての（perm、perm [::-1]）がそれらの1つだけを受け入れるフィルタリング条件が必要です。OPはアイテムが常に別個であると言っているので、2つの要素を比較することができます。
for p in itertools.permutations(range(3)):
if p[0] <= p[-1]:
print(p)
印刷するもの：
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
これが機能するのは、順列を逆にすると、常に最初と最後の要素の関係が反転するためです。
4つ以上の要素の場合、中央で対称な他の要素のペア（たとえば、各側から2番目p[1] <= p[::-1][1]）も機能します。
（以前に主張されたこの回答p[0] < p[1]は機能しますが、機能しません— pが逆になった後、これは異なる要素を選択します。）
順列全体とその逆について、直接辞書式比較を行うこともできます。
for p in itertools.permutations(range(3)):
if p <= p[::-1]:
print(p)
フィルタリングするためのより効率的な方法があるかどうかはわかりません。 itertools.permutations辞書式順序を保証しますが、辞書式順序pとp[::-1]は非常に複雑な方法で関連付けられています。特に、途中で止まるだけではうまくいきません。
しかし、2：1フィルタリングを備えた組み込みのイテレーターは、カスタム実装よりも優れていると思います（チェックしませんでした）。そしてもちろん、それは単純さで勝ちます！
辞書式順序で順列を生成する場合、特定の順列の逆がすでに見られているかどうかを判断するために何も保存する必要はありません。辞書式順序でその逆と比較する必要があります。小さい場合は返し、大きい場合はスキップします。
おそらくもっと効率的な方法がありますが、これは単純で、必要なプロパティがあります（ジェネレーターとして実装可能で、O（n）作業メモリーを使用します）。
これは、ChristopheDが受け入れた回答のより簡潔で高速なバージョンであり、私はとても気に入りました。再帰は素晴らしいです。重複を削除することで着信リストの一意性を強制するようにしましたが、代わりに例外を発生させる必要があるかもしれません。
def fac(x):
return (1 if x==0 else x * fac(x-1))
def permz(plist):
plist = sorted(set(plist))
plen = len(plist)
limit = fac(plen) / 2
counter = 0
if plen==1:
yield plist
else:
for perm in permz(plist[1:]):
for i in xrange(plen):
if counter == limit:
raise StopIteration
counter += 1
yield perm[:i] + plist[0:1] + perm[i:]
# ---- testing ----
plists = [
list('love'),
range(5),
[1,4,2,3,9],
['a',2,2.1],
range(8)]
for plist in plists:
perms = list(permz(plist))
print plist, True in [(list(reversed(i)) in foo) for i in perms]
編集：すべてをジェネレーターとして保持するように完全に変更されました（リスト全体がメモリに保持されることはありません）。要件を満たす必要があります（可能な順列の半分のみを計算します（逆の順列は計算しません） 。EDIT2 ：ここからより短い（そしてより単純な）階乗関数を追加しました。
EDIT3：：(コメントを参照）-改善されたバージョンは、bwopahのバージョンにあります。
def fac(x):
return (1 if x==0 else x * fac(x-1))
def all_permutations(plist):
global counter
if len(plist) <=1:
yield plist
else:
for perm in all_permutations(plist[1:]):
for i in xrange(len(perm)+1):
if len(perm[:i] + plist[0:1] + perm[i:]) == lenplist:
if counter == limit:
raise StopIteration
else:
counter = counter + 1
yield perm[:i] + plist[0:1] + perm[i:]
counter = 0
plist = ['a','b','c']
lenplist = len(plist)
limit = fac(lenplist) / 2
all_permutations_gen = all_permutations(plist)
print all_permutations_gen
print list(all_permutations_gen)
これが私の実装です：
a = [1,2,3,4]
def p(l):
if len(l) <= 1:
yield l
else:
for i in range(len(l)):
for q in p([l[j] for j in range(len(l)) if j != i]):
yield [l[i]] + q
out = (i for i in p(a) if i < i[::-1])
P関数は通常のpermu関数であり、すべての可能性を生み出します。結果を繰り返すときにフィルターが実行されます。簡単に言うと、すべてのpermusの小さい方の半分とpermusの大きい方の2つの結果が考えられます。この例では、outにはリストの小さい方の半分が含まれています。
これがそのトリックを行うコードです。重複を取り除くために、あなたのリストでは、最初の場所の値が最後の場所の値よりも大きい場合、それは重複になることに気づきました。最初に各アイテムがリストのどこにあったかを追跡するためのマップを作成し、そのマップを使用してテストを実行します。また、コードは再帰を使用しないため、メモリフットプリントを小さく保ちます。また、リストは、最後の2つのテストケースを参照するだけでなく、任意のタイプのアイテムにすることができます。
これがコードです。
class Permutation:
def __init__(self, justalist):
self._data = justalist[:]
self._len=len(self._data)
self._s=[]
self._nfact=1
self._map ={}
i=0
for elem in self._data:
self._s.append(elem)
self._map[str(elem)]=i
i+=1
self._nfact*=i
if i != 0:
self._nfact2=self._nfact//i
def __iter__(self):
for k in range(self._nfact):
for i in range(self._len):
self._s[i]=self._data[i]
s=self._s
factorial=self._nfact2
for i in range(self._len-1):
tempi = (k // factorial) % (self._len - i)
temp = s[i + tempi]
for j in range(i + tempi,i,-1):
s[j] = s[j-1]
s[i] = temp
factorial //= (self._len - (i + 1))
if self._map[str(s[0])] < self._map[str(s[-1])]:
yield s
s=[1,2]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[1,2,3]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[1,2,3,4]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[3,2,1]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=["Apple","Pear","Orange"]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
s=[[1,4,5],"Pear",(1,6,9),Permutation([])]
print("_"*25)
print("input list:",s)
for sx in Permutation(s):
print(sx)
これが私のテストケースの出力です。
_________________________
input list: [1, 2]
[1, 2]
_________________________
input list: [1, 2, 3]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
_________________________
input list: [1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 4, 1, 3]
[3, 1, 2, 4]
[3, 2, 1, 4]
_________________________
input list: [3, 2, 1]
[3, 2, 1]
[3, 1, 2]
[2, 3, 1]
_________________________
input list: ['Apple', 'Pear', 'Orange']
['Apple', 'Pear', 'Orange']
['Apple', 'Orange', 'Pear']
['Pear', 'Apple', 'Orange']
_________________________
input list: [[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], 'Pear', (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)]
[[1, 4, 5], (1, 6, 9), 'Pear', <__main__.Permutation object at 0x0142DEF0>]
[[1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>, 'Pear']
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, 'Pear', (1, 6, 9)]
[[1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9), 'Pear']
['Pear', [1, 4, 5], (1, 6, 9), <__main__.Permutation object at 0x0142DEF0>]
['Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>, (1, 6, 9)]
['Pear', (1, 6, 9), [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>]
['Pear', <__main__.Permutation object at 0x0142DEF0>, [1, 4, 5], (1, 6, 9)]
[(1, 6, 9), [1, 4, 5], 'Pear', <__main__.Permutation object at 0x0142DEF0>]
[(1, 6, 9), 'Pear', [1, 4, 5], <__main__.Permutation object at 0x0142DEF0>]
これはどう：
from itertools import permutations
def rev_generator(plist):
reversed_elements = set()
for i in permutations(plist):
if i not in reversed_elements:
reversed_i = tuple(reversed(i))
reversed_elements.add(reversed_i)
yield i
>>> list(rev_generator([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3)]
また、戻り値がリストでなければならない場合は、yieldiをyieldlist（i）に変更するだけで済みますが、反復の目的では、タプルは問題なく機能します。
これは、onebyoneの提案の実装です
http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generationから 次のアルゴリズムは、指定された順列の後に辞書式順序で次の順列を生成します。指定された順列をインプレースで変更します。
関数：
def perms(items):
items.sort()
yield items[:]
m = [len(items)-2] # step 1
while m:
i = m[-1]
j = [ j for j in range(i+1,len(items)) if items[j]>items[i] ][-1] # step 2
items[i], items[j] = items[j], items[i] # step 3
items[i+1:] = list(reversed(items[i+1:])) # step 4
if items<list(reversed(items)):
yield items[:]
m = [ i for i in range(len(items)-1) if items[i]<items[i+1] ] # step 1
私たちの仕事をチェックする：
>>> foo=list(perms([1,3,2,4,5]))
>>> True in [(list(reversed(i)) in foo) for i in foo]
False
最初にいくつかのセットアップコード：
try:
from itertools import permutations
except ImportError:
# straight from http://docs.python.org/library/itertools.html#itertools.permutations
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
def non_reversed_permutations(iterable):
"Return non-reversed permutations for an iterable with unique items"
for permutation in permutations(iterable):
if permutation[0] < permutation[-1]:
yield permutation
itertools.permutationsまさにあなたが望むことをします。reversedビルトインも活用できるかもしれません