كيفية إنشاء جميع التباديل لقائمة في بايثون
-
01-07-2019 - |
سؤال
كيف يمكنك إنشاء جميع التباديلات لقائمة في بايثون، بغض النظر عن نوع العناصر في تلك القائمة؟
على سبيل المثال:
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]
المحلول
بدءًا من بايثون 2.6 (وإذا كنت تستخدم Python 3) فلديك ملف مكتبة قياسية أداة لهذا: itertools.permutations
.
import itertools
list(itertools.permutations([1, 2, 3]))
إذا كنت تستخدم بايثون الأقدم (<2.6) لسبب ما أو كنت مهتمًا فقط بمعرفة كيفية عمله، إليك طريقة لطيفة مأخوذة من http://code.activestate.com/recipes/252178/:
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
.هنا واحد:
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)
نصائح أخرى
و في بايثون 2.6 فصاعدا:
import itertools
itertools.permutations([1,2,3])
(عاد كمولد.يستخدم list(permutations(l))
للعودة كقائمة.)
الكود التالي مع Python 2.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)]
المنتج الديكارتي (مع نفسه وقابل للتكرار):
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)]
def permutations(head, tail=''):
if len(head) == 0: print tail
else:
for i in range(len(head)):
permutations(head[0:i] + head[i+1:], tail+head[i])
كما دعا:
permutations('abc')
#!/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 هذا مستوحى من الخوارزمية المقدمة في الكتاب خوارزميات الكمبيوتر من قبل هورويتز، ساهني وراجاسيكيران.
يطبق هذا الحل مولدًا لتجنب الاحتفاظ بجميع التباديل على الذاكرة:
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
الكود التالي عبارة عن تبديل موضعي لقائمة معينة، ويتم تنفيذه كمولد.نظرًا لأنها تقوم بإرجاع المراجع إلى القائمة فقط، فلا ينبغي تعديل القائمة خارج المولد.الحل غير متكرر، لذا فهو يستخدم ذاكرة منخفضة.العمل بشكل جيد أيضًا مع نسخ متعددة من العناصر الموجودة في قائمة الإدخال.
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
قد تكون الطريقة الواضحة تمامًا في رأيي أيضًا:
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
بأسلوب وظيفي
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]]
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]
]
لقد استخدمت خوارزمية تعتمد على نظام الأعداد العاملية- للحصول على قائمة بالطول n، يمكنك تجميع كل عنصر التقليب حسب العنصر، والاختيار من العناصر المتبقية في كل مرحلة.لديك n اختيار للعنصر الأول، n-1 للعنصر الثاني، وخيار واحد فقط للأخير، لذا يمكنك استخدام أرقام الرقم في نظام الأرقام العاملية كمؤشرات.بهذه الطريقة تتوافق الأرقام من 0 إلى n!-1 مع جميع التباديل الممكنة في الترتيب المعجمي.
from math import factorial
def permutations(l):
permutations=[]
length=len(l)
for x in xrange(factorial(length)):
available=list(l)
newPermutation=[]
for radix in xrange(length, 0, -1):
placeValue=factorial(radix-1)
index=x/placeValue
newPermutation.append(available.pop(index))
x-=index*placeValue
permutations.append(newPermutation)
return permutations
permutations(range(3))
انتاج:
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
هذه الطريقة غير متكررة، ولكنها أبطأ قليلاً على جهاز الكمبيوتر الخاص بي ويثير xrange خطأً عند n!كبير جدًا بحيث لا يمكن تحويله إلى عدد صحيح طويل C (n = 13 بالنسبة لي).لقد كان ذلك كافيًا عندما كنت في حاجة إليه، لكنه ليس أدوات itertools.permutations على المدى الطويل.
لاحظ أن هذه الخوارزمية لديها 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]
يمكن للمرء بالفعل التكرار على العنصر الأول من كل تبديل، كما في إجابة 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
)، كما هو الحال في حل ريكاردو رييس.
هذا مستوحى من تطبيق 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
للأداء، حل Numpy مستوحى من نوث, ، (ص22):
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, :]
يوفر نسخ الكتل الكبيرة من الذاكرة الوقت - إنه أسرع 20x من 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
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)
فيما يلي خوارزمية تعمل على القائمة دون إنشاء قوائم وسيطة جديدة مشابهة لحل Ber في https://stackoverflow.com/a/108651/184528.
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
print p
يمكنك تجربة الكود بنفسك هنا: http://repl.it/J9v
جمال التكرار:
>>> import copy
>>> def perm(prefix,rest):
... for e in rest:
... new_rest=copy.copy(rest)
... new_prefix=copy.copy(prefix)
... new_prefix.append(e)
... new_rest.remove(e)
... if len(new_rest) == 0:
... print new_prefix + new_rest
... continue
... perm(new_prefix,new_rest)
...
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']
هذه الخوارزمية هي الأكثر فعالية، فهي تتجنب تمرير المصفوفة والتلاعب بها في الاستدعاءات المتكررة، وتعمل في بايثون 2، 3:
def permute(items):
length = len(items)
def inner(ix=[]):
do_yield = len(ix) == length - 1
for i in range(0, length):
if i in ix: #avoid duplicates
continue
if do_yield:
yield tuple([items[y] for y in ix + [i]])
else:
for p in inner(ix + [i]):
yield p
return inner()
الاستخدام:
for p in permute((1,2,3)):
print(p)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
def pzip(c, seq):
result = []
for item in seq:
for i in range(len(item)+1):
result.append(item[i:]+c+item[:i])
return result
def perm(line):
seq = [c for c in line]
if len(seq) <=1 :
return seq
else:
return pzip(seq[0], perm(seq[1:]))
توليد كافة التباديل الممكنة
أنا أستخدم بيثون3.4:
def calcperm(arr, size):
result = set([()])
for dummy_idx in range(size):
temp = set()
for dummy_lst in result:
for dummy_outcome in arr:
if dummy_outcome not in dummy_lst:
new_seq = list(dummy_lst)
new_seq.append(dummy_outcome)
temp.add(tuple(new_seq))
result = temp
return result
حالات تجريبية:
lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)
أرى أ كثير من التكرار الذي يحدث داخل هذه الوظائف العودية، ليس بالضبط نقي العودية...
لذلك بالنسبة لأولئك منكم الذين لا يستطيعون الالتزام حتى بحلقة واحدة، فإليك حل عودي إجمالي وغير ضروري على الإطلاق
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])
حل آخر:
def permutation(flag, k =1 ):
N = len(flag)
for i in xrange(0, N):
if flag[i] != 0:
continue
flag[i] = k
if k == N:
print flag
permutation(flag, k+1)
flag[i] = 0
permutation([0, 0, 0])
لتوفير ساعات طويلة من البحث والتجربة، إليك حل التبديلات غير العودية في Python والذي يعمل أيضًا مع Numba (اعتبارًا من الإصدار v.0.41):
@numba.njit()
def permutations(A, k):
r = [[i for i in range(0)]]
for i in range(k):
r = [[a] + b for a in A for b in r if (a in b)==False]
return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
لإعطاء انطباع عن الأداء:
%timeit permutations(np.arange(5),5)
243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms
%timeit list(itertools.permutations(np.arange(5),5))
15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s
لذا استخدم هذا الإصدار فقط إذا كان عليك استدعاؤه من وظيفة njitted، وإلا ففضل تطبيق itertools.
نهج آخر (بدون libs)
def permutation(input):
if len(input) == 1:
return input if isinstance(input, list) else [input]
result = []
for i in range(len(input)):
first = input[i]
rest = input[:i] + input[i + 1:]
rest_permutation = permutation(rest)
for p in rest_permutation:
result.append(first + p)
return result
يمكن أن يكون الإدخال سلسلة أو قائمة
print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
حل بايثون الخاص بي:
def permutes(input,offset):
if( len(input) == offset ):
return [''.join(input)]
result=[]
for i in range( offset, len(input) ):
input[offset], input[i] = input[i], input[offset]
result = result + permutes(input,offset+1)
input[offset], input[i] = input[i], input[offset]
return result
# input is a "string"
# return value is a list of strings
def permutations(input):
return permutes( list(input), 0 )
# Main Program
print( permutations("wxyz") )
def permutation(word, first_char=None):
if word == None or len(word) == 0: return []
if len(word) == 1: return [word]
result = []
first_char = word[0]
for sub_word in permutation(word[1:], first_char):
result += insert(first_char, sub_word)
return sorted(result)
def insert(ch, sub_word):
arr = [ch + sub_word]
for i in range(len(sub_word)):
arr.append(sub_word[i:] + ch + sub_word[:i])
return arr
assert permutation(None) == []
assert permutation('') == []
assert permutation('1') == ['1']
assert permutation('12') == ['12', '21']
print permutation('abc')
انتاج:["abc"، "acb"، "bac"، "bca"، "cab"، "cba"]
استخدام Counter
from collections import Counter
def permutations(nums):
ans = [[]]
cache = Counter(nums)
for idx, x in enumerate(nums):
result = []
for items in ans:
cache1 = Counter(items)
for id, n in enumerate(nums):
if cache[n] != cache1[n] and items + [n] not in result:
result.append(items + [n])
ans = result
return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
هذه الطريقة أفضل من البدائل التي أراها، تحقق منها.
def permutations(arr):
if not arr:
return
print arr
for idx, val in enumerate(arr):
permutations(arr[:idx]+arr[idx+1:])
بالنسبة إلى Python، يمكننا استخدام itertools واستيراد كل من التباديل والمجموعات لحل مشكلتك
from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))