Bagaimana cara menghasilkan semua permutasi daftar?

592

Bagaimana Anda menghasilkan semua permutasi daftar dalam Python, terlepas dari jenis elemen dalam daftar itu?

Sebagai contoh:

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]
Ricardo Reyes
sumber
5
Saya setuju dengan jawaban rekursif dan diterima - HARI INI. Namun, ini masih menggantung di luar sana sebagai masalah ilmu komputer yang sangat besar. Jawaban yang diterima menyelesaikan masalah ini dengan kompleksitas eksponensial (2 ^ NN = len (daftar)) Selesaikan (atau buktikan Anda tidak dapat) dalam waktu polinomial :) Lihat "masalah salesman keliling"
FlipMcF
38
@FlipMcF Akan sulit untuk "menyelesaikannya" dalam waktu polinomial, mengingat dibutuhkan waktu faktorial untuk bahkan hanya menghitung output ... jadi, tidak, itu tidak mungkin.
Thomas

Jawaban:

489

Dimulai dengan Python 2.6 (dan jika Anda berada di Python 3) Anda memiliki standar-library alat untuk ini: itertools.permutations.

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

Jika Anda menggunakan Python yang lebih lama (<2.6) karena alasan tertentu atau hanya ingin tahu cara kerjanya, berikut ini satu pendekatan yang bagus, diambil dari 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:]

Beberapa pendekatan alternatif tercantum dalam dokumentasi itertools.permutations. Ini dia:

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

Dan yang lain, berdasarkan 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)
Eli Bendersky
sumber
14
Ini dan solusi rekursif lainnya memiliki potensi bahaya memakan semua RAM jika daftar permutasi cukup besar
Boris Gorelik
3
Mereka juga mencapai batas rekursi (dan mati) dengan daftar besar
dbr.
58
bgbg, dbr: Menggunakan generator, jadi fungsinya sendiri tidak memakan memori. Yang tersisa untuk Anda tentang cara mengkonsumsi iterator dikembalikan oleh all_perms (katakanlah Anda bisa menulis setiap iterasi ke disk dan tidak khawatir tentang memori). Saya tahu posting ini sudah tua tetapi saya menulis ini untuk kepentingan semua orang yang membacanya sekarang. Juga sekarang, cara terbaik adalah menggunakan itertools.permutations () seperti yang ditunjukkan oleh banyak orang.
Jagtesh Chadha
18
Bukan hanya sebuah pembangkit. Ini menggunakan generator bersarang, yang masing-masing menghasilkan yang sebelumnya menumpuk panggilan, jika itu tidak jelas. Ini menggunakan O (n) memori, yang bagus.
cdunn2001
1
PS: Saya memperbaikinya, for i in range(len(elements))bukan for i in range(len(elements)+1). Faktanya, elemen yang dipilih elements[0:1]dapat berada di len(elements)posisi yang berbeda, sehingga hasilnya tidak len(elements)+1.
Eric O Lebigot
339

Dan dengan Python 2.6 dan seterusnya:

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

(dikembalikan sebagai generator. Gunakan list(permutations(l))untuk kembali sebagai daftar.)

Brian
sumber
15
Bekerja di Python 3 juga
wheleph
10
Perhatikan bahwa ada rparameter, misalnya itertools.permutations([1,2,3], r=2), yang akan menghasilkan semua kemungkinan permutasi dengan memilih 2 elemen:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
toto_tico
278

Kode berikut dengan Python 2.6 dan di atas SAJA

Pertama, impor itertools:

import itertools

Permutasi (masalah pesanan):

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

Kombinasi (pesanan TIDAK masalah):

print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]

Produk Cartesian (dengan beberapa iterables):

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

Produk Cartesian (dengan satu iterable dan sendiri):

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)]
e-satis
sumber
2
+1! Tautan dokumen
Pramod
`print list (itertools.permutations ([1,2,3,4], 2)) ^` SyntaxError: invalid syntax` Baru memulai menggunakan VS Code Apa yang saya lakukan salah? Pointer menunjuk di bawah "t" dari "daftar"
gus
39
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])

disebut sebagai:

permutations('abc')
kx2k
sumber
Mengapa mencetak ekor lalu tidak kembali? Mengapa tidak mengembalikan ekor saja? Kenapa tidak mengembalikan apa pun?
bugmenot123
30
#!/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])

Keluaran:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

Saat saya menukar konten daftar itu diperlukan jenis urutan yang bisa berubah sebagai input. Misalnya perm(list("ball"))akan bekerja dan perm("ball")tidak akan karena Anda tidak dapat mengubah string.

Implementasi Python ini terinspirasi oleh algoritma yang disajikan dalam buku Algoritma Komputer oleh Horowitz, Sahni dan Rajasekeran .

Silveira Neto
sumber
Saya menganggap k adalah panjang atau permutasi. Untuk k = 2 keluaran [1, 2, 3]. Bukankah seharusnya (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) ??
Konstantinos Monachopoulos
k adalah indeks elemen yang ingin Anda
tukarkan
22

Solusi ini mengimplementasikan generator, untuk menghindari memegang semua permutasi pada memori:

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
Ricardo Reyes
sumber
16

Dalam gaya fungsional

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

Hasil:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
Paolo
sumber
15

Kode berikut adalah permutasi di tempat dari daftar yang diberikan, diimplementasikan sebagai generator. Karena hanya mengembalikan referensi ke daftar, daftar tidak boleh dimodifikasi di luar generator. Solusinya adalah non-rekursif, jadi gunakan memori rendah. Bekerja dengan baik juga dengan banyak salinan elemen dalam daftar input.

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
Ber
sumber
15

Cara yang cukup jelas menurut saya mungkin juga:

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
tzwenn
sumber
11
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

Keluaran:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]
zmk
sumber
2
Meskipun secara teknis menghasilkan output yang diinginkan, Anda sedang memecahkan sesuatu yang bisa jadi O (n lg n) di O (n ^ n) - "sedikit" tidak efisien untuk set besar.
James
3
@ James: Saya sedikit bingung dengan O (n log n) yang Anda berikan: jumlah permutasi adalah n !, yang sudah jauh lebih besar dari O (n log n); jadi, saya tidak bisa melihat bagaimana sebuah solusi bisa menjadi O (n log n). Namun, memang benar bahwa solusi ini ada di O (n ^ n), yang jauh lebih besar dari n !, seperti yang jelas dari perkiraan Stirling.
Eric O Lebigot
9

Saya menggunakan algoritma yang didasarkan pada sistem bilangan faktorial - Untuk daftar panjang n, Anda dapat mengumpulkan setiap item permutasi dengan item, memilih dari item yang tersisa di setiap tahap. Anda memiliki n pilihan untuk item pertama, n-1 untuk item kedua, dan hanya satu untuk item terakhir, sehingga Anda dapat menggunakan digit angka dalam sistem angka faktorial sebagai indeks. Dengan cara ini angka 0 hingga n! -1 berhubungan dengan semua permutasi yang mungkin dalam urutan leksikografis.

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

keluaran:

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Metode ini non-rekursif, tetapi sedikit lebih lambat di komputer saya dan xrange memunculkan kesalahan ketika n! terlalu besar untuk dikonversi ke integer C panjang (n = 13 untuk saya). Sudah cukup ketika saya membutuhkannya, tapi itu bukan itertools.permutasi oleh tembakan panjang.

penerima waktu
sumber
3
Hai, selamat datang di Stack Overflow. Meskipun memposting metode brute force memiliki kelebihan, jika Anda tidak berpikir solusi Anda lebih baik daripada solusi yang diterima, Anda mungkin tidak boleh mempostingnya (terutama pada pertanyaan lama yang sudah memiliki begitu banyak jawaban).
Hannele
1
Saya benar-benar mencari pendekatan non-perpustakaan kasar, jadi terima kasih!
Jay Taylor
8

Perhatikan bahwa algoritma ini memiliki n factorialkompleksitas waktu, di mana npanjang daftar input

Cetak hasilnya dalam pelarian:

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

Contoh:

permutation([1,2,3])

Keluaran:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Chen Xie
sumber
8

Seseorang memang bisa mengulangi elemen pertama dari setiap permutasi, seperti pada jawaban twwenn. Namun lebih efisien untuk menulis solusi ini dengan cara ini:

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

Solusi ini sekitar 30% lebih cepat, tampaknya berkat rekursi yang berakhir pada len(elements) <= 1bukan 0. Ini juga jauh lebih hemat memori, karena menggunakan fungsi generator (melalui yield), seperti dalam solusi Riccardo Reyes.

Eric O Lebigot
sumber
6

Ini terinspirasi oleh implementasi Haskell menggunakan pemahaman daftar:

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
piggybox
sumber
6

Implementasi reguler (tanpa hasil - akan melakukan segalanya dalam memori):

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

Implementasi hasil:

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]

Ide dasarnya adalah untuk membahas semua elemen dalam array untuk posisi 1, dan kemudian di posisi 2 memeriksa semua elemen tanpa elemen yang dipilih untuk 1, dll. Anda dapat melakukan ini dengan rekursi , di mana kriteria stop mencapai array 1 elemen - dalam hal ini Anda mengembalikan array itu.

masukkan deskripsi gambar di sini

David Refaeli
sumber
Ini tidak berfungsi untuk saya _> ValueError: operan tidak dapat disiarkan bersama dengan bentuk (0,) (2,) , untuk baris ini:perms = getPermutations(array[:i] + array[i+1:])
RK1
@ RK1 apa inputnya?
David Refaeli
Saya melewati numpyarray _> getPermutations(np.array([1, 2, 3])), saya melihatnya berfungsi untuk daftar, baru saja bingung karena func arg adalah array:)
RK1
@ RK1 senang berfungsi :-) daftar adalah kata kunci dalam python, jadi biasanya bukan ide yang baik untuk memanggil parameter Anda kata kunci, karena akan "membayangi" itu. Jadi saya menggunakan kata array, karena ini adalah fungsi sebenarnya dari daftar yang saya gunakan - cara mereka seperti array. Saya kira jika saya akan menulis dokumentasi saya akan mengklarifikasi. Saya juga percaya bahwa pertanyaan "wawancara" dasar harus diselesaikan tanpa paket eksternal, seperti numpy.
David Refaeli
Haha itu benar, ya sedang mencoba menggunakannya numbadan menjadi serakah dengan kecepatan jadi coba gunakan secara eksklusif dengan numpyarray
RK1
4

Untuk kinerja, solusi numpy yang terinspirasi oleh Knuth , (hal 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, :]

Menyalin blok memori yang besar menghemat waktu - 20x lebih cepat dari 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
BM
sumber
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)
Adrian Statescu
sumber
3

Berikut adalah algoritme yang berfungsi pada daftar tanpa membuat daftar perantara baru yang mirip dengan solusi Ber di 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

Anda dapat mencoba kode ini sendiri di sini: http://repl.it/J9v

cdiggins
sumber
3

Keindahan rekursi:

>>> 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']
darxtrix
sumber
3

Algoritme ini adalah yang paling efektif, menghindari array passing dan manipulasi dalam panggilan rekursif, bekerja dengan Python 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()

Pemakaian:

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)
Cmyker
sumber
3
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:]))
manish kumar
sumber
3

PENDEKATAN LAIN (tanpa lib)

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

Input dapat berupa string atau daftar

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
Tatsu
sumber
Ini tidak berfungsi untuk daftar dengan bilangan bulat, mis. [1, 2, 3]kembali[6, 6, 6, 6, 6, 6]
RK1
@ RK1, Anda dapat mencobanyaprint(permutation(['1','2','3']))
Tatsu
Terima kasih itu berhasil
RK1
3

Penafian: plug tak berbentuk oleh penulis paket. :)

The pengeliling paket berbeda dari kebanyakan implementasi dalam hal menghasilkan daftar semu yang tidak benar-benar berisi permutasi melainkan menggambarkan pemetaan antara permutasi dan posisi masing dalam pemesanan, sehingga memungkinkan untuk bekerja dengan sangat besar 'daftar' permutasi, seperti yang ditunjukkan dalam demo ini yang melakukan operasi yang sangat instan dan mencari dalam daftar semu 'berisi' semua permutasi dari huruf-huruf dalam alfabet, tanpa menggunakan lebih banyak memori atau pemrosesan daripada halaman web biasa.

Bagaimanapun, untuk menghasilkan daftar permutasi, kita dapat melakukan hal berikut.

import trotter

my_permutations = trotter.Permutations(3, [1, 2, 3])

print(my_permutations)

for p in my_permutations:
    print(p)

Keluaran:

Daftar pseudo yang mengandung 6 3-permutasi [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]
Richard Ambler
sumber
2

Hasilkan semua permutasi yang mungkin

Saya menggunakan python3.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

Kasus uji:

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)
Miled Louis Rizk
sumber
2

Untuk menyelamatkan Anda dari kemungkinan berjam-jam mencari dan bereksperimen, berikut ini adalah solusi permutasi non-rekursif dalam Python yang juga bekerja dengan Numba (pada 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]]

Untuk memberi kesan tentang kinerja:

%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

Jadi gunakan versi ini hanya jika Anda harus memanggilnya dari fungsi njitted, jika tidak, pilih itertools implementasinya.

Anatoly Alekseev
sumber
1

Saya melihat banyak iterasi terjadi di dalam fungsi rekursif ini, bukan rekursi murni ...

jadi bagi Anda yang tidak dapat mematuhi bahkan satu loop, inilah solusi rekursif sepenuhnya, benar-benar tidak perlu

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])
Karo Castro-Wunsch
sumber
1

Solusi lain:

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])
anhldbk
sumber
0

Solusi Python Saya:

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") )
kasar
sumber
0
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')

Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Ilgorbek Kuchkarov
sumber
0

Menggunakan 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]]
Halo Dunia
sumber