كيفية إنشاء جميع التباديل لقائمة في بايثون

Question

كيف يمكنك إنشاء جميع التباديلات لقائمة في بايثون، بغض النظر عن نوع العناصر في تلك القائمة؟

على سبيل المثال:

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]

Answer 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)

Answer 2

و في بايثون 2.6 فصاعدا:

import itertools
itertools.permutations([1,2,3])

(عاد كمولد.يستخدم list(permutations(l)) للعودة كقائمة.)

Answer 3

الكود التالي مع 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)]

Answer 4

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')

Answer 5

#!/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 هذا مستوحى من الخوارزمية المقدمة في الكتاب خوارزميات الكمبيوتر من قبل هورويتز، ساهني وراجاسيكيران.

Answer 6

يطبق هذا الحل مولدًا لتجنب الاحتفاظ بجميع التباديل على الذاكرة:

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

Answer 7

الكود التالي عبارة عن تبديل موضعي لقائمة معينة، ويتم تنفيذه كمولد.نظرًا لأنها تقوم بإرجاع المراجع إلى القائمة فقط، فلا ينبغي تعديل القائمة خارج المولد.الحل غير متكرر، لذا فهو يستخدم ذاكرة منخفضة.العمل بشكل جيد أيضًا مع نسخ متعددة من العناصر الموجودة في قائمة الإدخال.

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

Answer 8

قد تكون الطريقة الواضحة تمامًا في رأيي أيضًا:

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

Answer 9

بأسلوب وظيفي

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]]

Answer 10

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]
]

Answer 11

لقد استخدمت خوارزمية تعتمد على نظام الأعداد العاملية- للحصول على قائمة بالطول 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 على المدى الطويل.

Answer 12

لاحظ أن هذه الخوارزمية لديها 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]

Answer 13

يمكن للمرء بالفعل التكرار على العنصر الأول من كل تبديل، كما في إجابة 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)، كما هو الحال في حل ريكاردو رييس.

Answer 14

هذا مستوحى من تطبيق 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

Answer 15

للأداء، حل 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

Answer 16

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)

Answer 17

فيما يلي خوارزمية تعمل على القائمة دون إنشاء قوائم وسيطة جديدة مشابهة لحل 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

Answer 18

جمال التكرار:

>>> 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']

Answer 19

هذه الخوارزمية هي الأكثر فعالية، فهي تتجنب تمرير المصفوفة والتلاعب بها في الاستدعاءات المتكررة، وتعمل في بايثون 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)

Answer 20

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:]))

Answer 21

توليد كافة التباديل الممكنة

أنا أستخدم بيثون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)

Answer 22

أرى أ كثير من التكرار الذي يحدث داخل هذه الوظائف العودية، ليس بالضبط نقي العودية...

لذلك بالنسبة لأولئك منكم الذين لا يستطيعون الالتزام حتى بحلقة واحدة، فإليك حل عودي إجمالي وغير ضروري على الإطلاق

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])

Answer 23

حل آخر:

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])

Answer 24

لتوفير ساعات طويلة من البحث والتجربة، إليك حل التبديلات غير العودية في 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.

Answer 25

نهج آخر (بدون 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']))

Answer 26

حل بايثون الخاص بي:

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") )

Answer 27

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"]

Answer 28

استخدام 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]]

Answer 29

هذه الطريقة أفضل من البدائل التي أراها، تحقق منها.

def permutations(arr):
  if not arr:
    return
  print arr
  for idx, val in enumerate(arr):
    permutations(arr[:idx]+arr[idx+1:])

Answer 30

بالنسبة إلى Python، يمكننا استخدام itertools واستيراد كل من التباديل والمجموعات لحل مشكلتك

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))