Python tillhandahåller direkta metoder för att hitta permutationer och kombinationer av en sekvens. Dessa metoder finns i itertools-paketet.

Permutation

Importera först itertools-paketet för att implementera permutationsmetoden i python. Den här metoden tar en lista som indata och returnerar en objektlista med tupler som innehåller alla permutationer i en listform.

Python3

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

Produktion:

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

Tidskomplexitet: O(n!), där n är längden på inmatningslistan. Detta beror på att det finns n! permutationer av n element, och programmet genererar och skriver ut dem alla.
Extra utrymme: O(n!), eftersom programmet behöver lagra alla n! permutationer i minnet innan du skriver ut dem. Specifikt, perm-variabeln som skapas genom att anropa permutations([1, 2, 3]) lagrar alla n! permutationer i minnet som en lista.

Det genererar n! permutationer om längden på ingångssekvensen är n.
Om du vill få permutationer av längd L, implementera det på detta sätt.

Python3

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

Produktion:

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

Tidskomplexiteten för detta program är O(n^r) där n är längden på inmatningsmatrisen och r är längden på permutationer som ska genereras.

Rymdkomplexiteten är också O(n^r) eftersom alla permutationer lagras i minnet före utskrift.

Det genererar nCr * r! permutationer om längden på ingångssekvensen är n och ingångsparametern är r.

Kombination

Denna metod tar en lista och en ingång r som en ingång och returnerar en objektlista med tupler som innehåller alla möjliga kombinationer av längd r i en listform.

Python3

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

Produktion:

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

1. Kombinationer sänds ut i lexikografisk sorteringsordning för input. Så om inmatningslistan är sorterad kommer kombinationstuplarna att produceras i sorterad ordning.

Python3

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

Produktion:

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

2. Element behandlas som unika baserat på deras position, inte på deras värde. Så om inmatningselementen är unika kommer det inte att finnas några upprepade värden i varje kombination.

Python3

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

Produktion:

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

3. Om vi ​​vill göra en kombination av samma element till samma element använder vi kombinationer_med_ersättning.

Python3

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

Produktion:

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