Python tarjoaa suoria menetelmiä sekvenssien permutaatioiden ja yhdistelmien löytämiseen. Nämä menetelmät ovat itertools-paketissa.

Permutaatio

Tuo ensin itertools-paketti toteuttaaksesi permutaatiomenetelmän pythonissa. Tämä menetelmä ottaa syötteenä listan ja palauttaa objektiluettelon monikoista, jotka sisältävät kaikki permutaatiot luettelomuodossa.

Python 3

# A Python program to print all> # permutations using library function> from> itertools> import> permutations> # Get all permutations of [1, 2, 3]> perm> => permutations([> 1> ,> 2> ,> 3> ])> # Print the obtained permutations> for> i> in> list> (perm):> > print> (i)>

Lähtö:

(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) 

Aika monimutkaisuus: O(n!), jossa n on syöttöluettelon pituus. Tämä johtuu siitä, että siellä on n! n elementin permutaatioita, ja ohjelma luo ja tulostaa ne kaikki.
Aputila: O(n!), koska ohjelman on tallennettava kaikki n! permutaatioita muistissa ennen niiden tulostamista. Tarkemmin sanottuna permutaatioita ([1, 2, 3]) kutsumalla luotu perm-muuttuja tallentaa kaikki n! permutaatiot muistissa luettelona.

Se tuottaa n! permutaatiot, jos syötesekvenssin pituus on n.
Jos haluat saada permutaatioita, joiden pituus on L, toteuta se tällä tavalla.

Python 3

# A Python program to print all> # permutations of given length> from> itertools> import> permutations> # Get all permutations of length 2> # and length 2> perm> => permutations([> 1> ,> 2> ,> 3> ],> 2> )> # Print the obtained permutations> for> i> in> list> (perm):> > print> (i)>

Lähtö:

(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 

Tämän ohjelman aikamonimutkaisuus on O(n^r), jossa n on syötetaulukon pituus ja r on generoitavien permutaatioiden pituus.

Tilan monimutkaisuus on myös O(n^r), koska kaikki permutaatiot tallennetaan muistiin ennen tulostusta.

Se tuottaa nCr * r! permutaatiot, jos syötesekvenssin pituus on n ja syöttöparametri on r.

Yhdistelmä

Tämä menetelmä ottaa listan ja syötteen r syötteenä ja palauttaa objektiluettelon monista, jotka sisältävät kaikki mahdolliset pituuden r yhdistelmät luettelomuodossa.

Python 3

# A Python program to print all> # combinations of given length> from> itertools> import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb> => combinations([> 1> ,> 2> ,> 3> ],> 2> )> # Print the obtained combinations> for> i> in> list> (comb):> > print> (i)>

Lähtö:

(1, 2) (1, 3) (2, 3) 

1. Yhdistelmät lähetetään leksikografisessa lajittelujärjestyksessä. Joten jos syöttölista on lajiteltu, yhdistelmätuplet tuotetaan lajiteltuun järjestykseen.

Python 3

# A Python program to print all> # combinations of a given length> from> itertools> import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb> => combinations([> 1> ,> 2> ,> 3> ],> 2> )> # Print the obtained combinations> for> i> in> list> (comb):> > print> (i)>

Lähtö:

(1, 2) (1, 3) (2, 3) 

2. Elementtejä käsitellään ainutlaatuisina niiden sijainnin, ei arvon perusteella. Joten jos syöteelementit ovat ainutlaatuisia, kussakin yhdistelmässä ei ole toistuvia arvoja.

Python 3

# A Python program to print all combinations> # of given length with unsorted input.> from> itertools> import> combinations> # Get all combinations of [2, 1, 3]> # and length 2> comb> => combinations([> 2> ,> 1> ,> 3> ],> 2> )> # Print the obtained combinations> for> i> in> list> (comb):> > print> (i)>

Lähtö:

(2, 1) (2, 3) (1, 3) 

3. Jos haluamme tehdä yhdistelmän samasta elementistä samalle elementille, käytämme kombinaatioita_korvauksella.

Python 3

# A Python program to print all combinations> # with an element-to-itself combination is> # also included> from> itertools> import> combinations_with_replacement> # Get all combinations of [1, 2, 3] and length 2> comb> => combinations_with_replacement([> 1> ,> 2> ,> 3> ],> 2> )> # Print the obtained combinations> for> i> in> list> (comb):> > print> (i)>

Lähtö:

(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)