Permutation and Combination in Python

Permutations and combinations are some of the basic ideas in mathematics, especially in the combinatorial world. This can be effectively calculated using Python’s itertools module, which comes with inbuilt functions for computing permutations and combinations of a set of elements.

Permutation

A permutation is an arrangement of a set where the order matters. For example, the permutations of the set {A,B,C} are:

• (A,B,C)
• (A,C,B)(A,C,B)
• (B,A,C)(B,A,C)
• (B,C,A)(B,C,A)
• (C,A,B)(C,A,B)
• (C,B,A)(C,B,A)

Combination

A combination is a selection of items from a set where the order does not matter. For instance, the combinations of two elements from the set {A,B,C}{A,B,C} are:

• (A,B)
• (A,C)(A,C)
• (B,C)(B,C)

Using itertools in Python

To perform permutations and combinations in Python, you need to import the itertools module. Here’s how to use it:

import itertools

Generating Permutations

The permutations() function from itertools returns all possible permutations of a given iterable. The length of permutations can be set to generate just fixed-length permutations.

Example: Generating All Permutations

from itertools import permutations

# Generate all permutations of [1, 2, 3]
perm = permutations([1, 2, 3])
for p in list(perm):
    print(p)

Output:

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

The time complexity for generating permutations is O(n!), where n is the number of elements in the input list 3.

Generating Combinations

The combinations() function generates all possible combinations of a specified length from an iterable.

Example: Generating Combinations

from itertools import combinations

# Generate all combinations of length 2 from [1, 2, 3]
comb = combinations([1, 2, 3], 2)
for c in list(comb):
    print(c)

Output:

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

Fixed Length Permutations and Combinations

You can also generate permutations and combinations of a fixed length by passing an additional argument to the respective functions.

Example: Fixed Length Permutations

# Generate all permutations of length 2 from [1, 2, 3]
fixed_perm = permutations([1, 2, 3], 2)
for p in list(fixed_perm):
    print(p)

Output:

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

Example: Fixed Length Combinations

# Generate all combinations of length 2 from [1, 2, 3]
fixed_comb = combinations([1, 2, 3], 2)
for c in list(fixed_comb):
    print(c)

Output:

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

Combinations with Replacement

If you want to allow repeated elements in combinations (i.e., each element can be chosen more than once), you can use combinations_with_replacement().

Example: Combinations with Replacement

from itertools import combinations_with_replacement

# Generate combinations with replacement
comb_with_replacement = combinations_with_replacement([1], 2)
for c in list(comb_with_replacement):
    print(c)

Output:

(1,)

Conclusion

Python’s itertools library provides powerful tools for generating permutations and combinations easily. By understanding how to use these functions effectively along with their complexities you can solve various combinatorial problems efficiently.