Ako môžem efektívne použiť funkciu Permute NP v Pythone na generovanie všetkých možných permutácií daného zoznamu?

Zatiaľ čo `np.random.permutation` od numpy je vynikajúca na generovanie * náhodnej * permutácie, nie je to nástroj na generovanie * všetkých * permutácií. Na efektívne generovanie všetkých možných permutácií by ste mali použiť funkciu „itertools.permutations“ zo štandardnej knižnice. Numpy pre túto úlohu vo všeobecnosti nie je potrebný a „Itertools“ je vysoko optimalizovaný pre generovanie permutácie.

Tu je rozdelenie toho, ako efektívne používať „itertools.Permutations“, spolu s dôvodom, prečo `np.random.Permutácia“ nie je vhodná na generovanie všetkých permutácií:

1. Pomocou `itertools.permutations '(odporúčaný prístup)

`` `Python

importovať itertools

def all_permutations (input_list):

"" "

Generuje všetky možné permutácie zoznamu.

ARG:

Input_list:Zoznam, pre ktoré sa má generovať permutácie.

Návraty:

Generátor, ktorý poskytuje n -tice, kde je každá tupá permutácia.

"" "

return itertools.permutations (input_list)

Príklad použitia:

my_list =[1, 2, 3]

permutations =all_permutations (my_list)

Pre perm v permutáciách:

Tlač (perm) # Vytlačí každú permutáciu ako tupo.

výstup:

(1, 2, 3)

(1, 3, 2)

(2, 1, 3)

(2, 3, 1)

(3, 1, 2)

(3, 2, 1)

Ak chcete previesť každú permutáciu na zoznam, použite:

my_list =[1, 2, 3]

permutations =all_permutations (my_list)

Pre perm v permutáciách:

tlač (zoznam (perm)) # Vytlačí každú permutáciu ako zoznam

výstup:

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

Ak chcete získať všetky permutácie ako zoznam zoznamov:

my_list =[1, 2, 3]

permutations =List (all_permutations (my_list)) # Prevod generátora na zoznam

List_of_lists =[List (perm) pre Perm in Permutations] # Konvertujte Tuple na zoznam

tlač (list_of_lists)

výstup:

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

`` `

Vysvetlenie:

* `itertools.permutations (input_list)`: Toto je jadro riešenia. Vráti * iterátor * (konkrétne objekt `permutácie). Iterátor je účinný na pamäť, pretože generuje permutácie na požiadanie, namiesto toho, aby ich všetky vytvoril naraz v pamäti. To je rozhodujúce pre dlhšie zoznamy, v ktorých sa počet permutácií môže stať extrémne veľký (n! Rastie veľmi rýchlo).

* generátor: Použitie generátora (iterátor) je dôležité pre efektívnosť. Ak prevádzate generátor na zoznam vopred (napr. `List (itertools.permutations (input_list))`), vygenerujete * všetky * permutácie, čo môže viesť k problémom s pamäťou pre väčšie vstupné zoznamy. Spracujte permutácie jeden po druhom pomocou `pre„ slučku.

* `Tuple` výstup: `iterTools.Permutations 'vracia každú permutáciu ako` numle`. Ak potrebujete výstup ako „zoznam“, môžete previesť n -zoznam pomocou `Zoznam (perm)`.

* Účinnosť: `itertools.Permutations 'je implementovaný v C a je pre túto úlohu vysoko optimalizovaný. Je to najúčinnejší spôsob, ako generovať permutácie v Pythone.

2. Prečo `np.random.permutation` je nevhodné

`np.random.permutation` je navrhnutý na generovanie * náhodných * permutácií, nie všetky. Preto to nebude fungovať správne pre zamýšľaný účel:

* náhodnosť: Vytvára jednu náhodnú permutáciu zakaždým, keď ju voláte.

* Žiadna záruka všetkých permutácií: Ak chcete získať * všetky * permutácie s `np.random.permutation`, museli by ste to opakovane nazvať, až kým nevidete všetko n! možnosti. Neexistuje spôsob, ako zistiť, kedy ste vyčerpali všetky permutácie bez toho, aby ste sledovali tie, ktoré ste už videli, čo sa stáva mimoriadne zložitým a neefektívnym. Neexistuje žiadna záruka, že týmto spôsobom budete niekedy generovať každú možnú permutáciu.

* neefektívne opakovanie: Generovali by ste mnoho duplikátových permutácií predtým (možno nikdy) ich všetky.

Nesprávny (a neefektívny) pokus s použitím `np.random.permutation` (iba ilustratívne účely - nepoužívajte):

`` `Python

import numpy ako np

DEF pokus_all_permutations_with_Numpy (input_list):

"" "

Nepoužívajte to! Je to nesprávny a neefektívny pokus

Generovanie všetkých permutácií pomocou NP.random.Permutácie.

"" "

seen_permutations =set ()

all_perms =[]

n =len (input_list)

faktory_n =np.math.Factorial (n) # To by mohlo pretekať!

zatiaľ čo Len (Seen_permutations) perm =tuple (np.random.permutation (input_list)) # prevod na uple pre set

Ak perm nie je v Seen_permutáciách:

Seen_permutations.add (perm)

all_perms.append (zoznam (perm))

vráťte all_perms

Nepoužívajte tento príklad! Je to len na demonštráciu toho, prečo je to nesprávne.

my_list =[1, 2, 3]

permutations =fits_all_permutations_with_Numpy (my_list) # potenciálne visí alebo používa nadmernú pamäť.

Print (permutácie)

`` `

Problémy s pokusom Numpy:

* Problémy s pamäťou: Sada `See_permutations 'by rýchlo rástla na obrovskú veľkosť, ktorá by potenciálne prekročila dostupnú pamäť, najmä pre o niečo väčšie zoznamy.

* Účinnosť: Podmienka slučky „Len (Seen_permutations) * Nesprávnosť: Je možné (hoci štatisticky nepravdepodobné), aby slučka predčasne ukončila alebo nikdy neukončila kvôli náhodnej povahe tvorby permutácie.

* konverzia Tuple: Konverzia numpy polia na n -tice a späť do zoznamov je režijné náklady, ktorému sa „Itertools“ vyhýba.

v súhrne:

Na generovanie všetkých možných permutácií zoznamu v Pythone vždy používajte `itertools.permutations . Je to správny, najúčinnejší a pythonický spôsob vyriešenia tohto problému. Vyhýbajte sa použitiu `np.random.permutácia“ na tento účel, pretože je navrhnutý pre inú úlohu a povedie k nesprávnému a neefektívnemu kódu.

• Predchádzajúca strana: Ako môžem implementovať riadený graf v Pythone? 
• Ďalšia strana: Ako je možné v Pythone implementovať kódovanie Huffmana?