リスト内の要素のタイプに関係なく、Python でリストのすべての順列をどのように生成しますか?
例えば：
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
878940 次
39 に答える
675
このための標準ライブラリに関数があります: itertools.permutations.
import itertools
list(itertools.permutations([1, 2, 3]))
なんらかの理由で自分で実装したい場合、またはそれがどのように機能するか知りたい場合は、 http : //code.activestate.com/recipes/252178/ から取得した 1 つの優れたアプローチを次に示します。
def all_perms(elements):
if len(elements) <=1:
yield elements
else:
for perm in all_perms(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
のドキュメントには、いくつかの代替アプローチがリストされていますitertools.permutations。ここに1つあります：
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
そして別の、に基づくitertools.product：
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
于 2008-09-19T18:43:09.380 に答える
353
そしてPython 2.6以降では:
import itertools
itertools.permutations([1,2,3])
(ジェネレーターとして返されlist(permutations(l))ます。リストとして返すために使用します。)
于 2008-09-19T18:48:48.043 に答える
321
Python2.6以降でのみ次のコード
まず、インポートitertools：
import itertools
順列（順序が重要）：
print list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]
組み合わせ（順序は関係ありません）：
print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]
デカルト積（いくつかの反復可能）：
print list(itertools.product([1,2,3], [4,5,6]))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]
デカルト積（1つの反復可能およびそれ自体を含む）：
print list(itertools.product([1,2], repeat=3))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
于 2008-10-04T12:18:56.230 に答える
57
def permutations(head, tail=''):
if len(head) == 0:
print(tail)
else:
for i in range(len(head)):
permutations(head[:i] + head[i+1:], tail + head[i])
次のように呼ばれます:
permutations('abc')
于 2011-10-12T00:14:09.050 に答える
37
#!/usr/bin/env python
def perm(a, k=0):
if k == len(a):
print a
else:
for i in xrange(k, len(a)):
a[k], a[i] = a[i] ,a[k]
perm(a, k+1)
a[k], a[i] = a[i], a[k]
perm([1,2,3])
出力：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
リストの内容を交換しているので、入力として変更可能なシーケンス タイプが必要です。たとえば、文字列を変更できないため、機能しますがperm(list("ball"))機能しません。perm("ball")
この Python 実装は、Horowitz、Sahni、Rajasekeran による本 Computer Algorithms で紹介されているアルゴリズムに触発されています。
于 2012-08-14T23:58:40.090 に答える
24
このソリューションは、ジェネレーターを実装して、すべての順列をメモリに保持しないようにします。
def permutations (orig_list):
if not isinstance(orig_list, list):
orig_list = list(orig_list)
yield orig_list
if len(orig_list) == 1:
return
for n in sorted(orig_list):
new_list = orig_list[:]
pos = new_list.index(n)
del(new_list[pos])
new_list.insert(0, n)
for resto in permutations(new_list[1:]):
if new_list[:1] + resto <> orig_list:
yield new_list[:1] + resto
于 2008-09-19T18:41:52.287 に答える
19
機能的なスタイルに
def addperm(x,l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
print perm([ i for i in range(3)])
結果：
[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
于 2013-06-30T15:17:16.677 に答える
17
次のコードは、ジェネレーターとして実装された、指定されたリストのインプレース順列です。リストへの参照のみを返すため、ジェネレーターの外部でリストを変更しないでください。ソリューションは非再帰的であるため、使用するメモリが少なくなります。入力リスト内の要素の複数のコピーでもうまく機能します。
def permute_in_place(a):
a.sort()
yield list(a)
if len(a) <= 1:
return
first = 0
last = len(a)
while 1:
i = last - 1
while 1:
i = i - 1
if a[i] < a[i+1]:
j = last - 1
while not (a[i] < a[j]):
j = j - 1
a[i], a[j] = a[j], a[i] # swap the values
r = a[i+1:last]
r.reverse()
a[i+1:last] = r
yield list(a)
break
if i == first:
a.reverse()
return
if __name__ == '__main__':
for n in range(5):
for a in permute_in_place(range(1, n+1)):
print a
print
for a in permute_in_place([0, 0, 1, 1, 1]):
print a
print
于 2008-09-20T16:32:47.673 に答える
17
私の意見では、非常に明白な方法も次のとおりです。
def permutList(l):
if not l:
return [[]]
res = []
for e in l:
temp = l[:]
temp.remove(e)
res.extend([[e] + r for r in permutList(temp)])
return res
于 2011-03-31T13:58:40.663 に答える
12
list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
for a in list2Perm
for b in list2Perm
for c in list2Perm
if ( a != b and b != c and a != c )
]
print listPerm
出力：
[
[1, 2.0, 'three'],
[1, 'three', 2.0],
[2.0, 1, 'three'],
[2.0, 'three', 1],
['three', 1, 2.0],
['three', 2.0, 1]
]
于 2011-08-21T18:28:44.337 に答える
11
通常の実装 (利回りなし - メモリ内ですべてを実行します):
def getPermutations(array):
if len(array) == 1:
return [array]
permutations = []
for i in range(len(array)):
# get all perm's of subarray w/o current item
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
permutations.append([array[i], *p])
return permutations
利回りの実装:
def getPermutations(array):
if len(array) == 1:
yield array
else:
for i in range(len(array)):
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
yield [array[i], *p]
基本的な考え方は、1 番目の位置で配列内のすべての要素を調べ、次に 2 番目の位置で、1 番目の選択された要素を除いて残りのすべての要素を調べるというものです。これはrecursionで行うことができます。停止基準は、1 要素の配列に到達することです。この場合、その配列を返します。
于 2020-01-04T18:50:09.307 に答える
10
このアルゴリズムにはn factorial時間計算量があることに注意してください。ここnで、入力リストの長さは
実行時に結果を出力します。
global result
result = []
def permutation(li):
if li == [] or li == None:
return
if len(li) == 1:
result.append(li[0])
print result
result.pop()
return
for i in range(0,len(li)):
result.append(li[i])
permutation(li[:i] + li[i+1:])
result.pop()
例：
permutation([1,2,3])
出力：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
于 2013-01-23T00:01:57.797 に答える
8
tzwennの答えのように、実際に各順列の最初の要素を繰り返すことができます。ただし、このソリューションを次のように作成する方が効率的です。
def all_perms(elements):
if len(elements) <= 1:
yield elements # Only permutation possible = no permutation
else:
# Iteration over the first element in the result permutation:
for (index, first_elmt) in enumerate(elements):
other_elmts = elements[:index]+elements[index+1:]
for permutation in all_perms(other_elmts):
yield [first_elmt] + permutation
このソリューションは約30％高速です。これは、再帰がのlen(elements) <= 1代わりにで終了するためと思われ0ます。yieldまた、Riccardo Reyesのソリューションのように、ジェネレーター関数（を介して）を使用するため、メモリ効率がはるかに高くなります。
于 2012-05-29T13:08:55.587 に答える
7
これは、リスト内包表記を使用した Haskell 実装に触発されています。
def permutation(list):
if len(list) == 0:
return [[]]
else:
return [[x] + ys for x in list for ys in permutation(delete(list, x))]
def delete(list, item):
lc = list[:]
lc.remove(item)
return lc
于 2013-11-16T04:10:33.230 に答える
6
パフォーマンスのために、 Knuthに触発された numpy ソリューション(p22) :
from numpy import empty, uint8
from math import factorial
def perms(n):
f = 1
p = empty((2*n-1, factorial(n)), uint8)
for i in range(n):
p[i, :f] = i
p[i+1:2*i+1, :f] = p[:i, :f] # constitution de blocs
for j in range(i):
p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f] # copie de blocs
f = f*(i+1)
return p[:n, :]
メモリの大きなブロックをコピーすると時間が節約されます - よりも 20 倍高速ですlist(itertools.permutations(range(n)):
In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop
In [2]: %timeit -n100 perms(10)
100 loops, best of 3: 40 ms per loop
于 2015-05-24T21:56:08.463 に答える
3
from __future__ import print_function
def perm(n):
p = []
for i in range(0,n+1):
p.append(i)
while True:
for i in range(1,n+1):
print(p[i], end=' ')
print("")
i = n - 1
found = 0
while (not found and i>0):
if p[i]<p[i+1]:
found = 1
else:
i = i - 1
k = n
while p[i]>p[k]:
k = k - 1
aux = p[i]
p[i] = p[k]
p[k] = aux
for j in range(1,(n-i)/2+1):
aux = p[i+j]
p[i+j] = p[n-j+1]
p[n-j+1] = aux
if not found:
break
perm(5)
于 2013-05-08T16:48:44.497 に答える
2
純粋な再帰ではなく、これらの再帰関数内で多くの反復が行われているのがわかります...
したがって、単一のループさえも順守できない人のために、これは総体的で完全に不必要な完全再帰的な解決策です
def all_insert(x, e, i=0):
return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []
def for_each(X, e):
return all_insert(X[0], e) + for_each(X[1:],e) if X else []
def permute(x):
return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])
perms = permute([1,2,3])
于 2016-08-05T15:59:00.350 に答える
0
def permuteArray (arr):
arraySize = len(arr)
permutedList = []
if arraySize == 1:
return [arr]
i = 0
for item in arr:
for elem in permuteArray(arr[:i] + arr[i + 1:]):
permutedList.append([item] + elem)
i = i + 1
return permutedList
新しいラインを少しユニークにするために、すべての可能性を使い尽くすつもりはありませんでした。
于 2020-06-04T07:33:40.400 に答える
-3
Python の場合、 itertools を使用して順列と組み合わせの両方をインポートして問題を解決できます
from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))
于 2015-09-08T02:58:55.873 に答える