Permutations and combinations in python

Combinations and Permutations in Python with itertools

If you a list, dictionary, or other iterable object of values you need to generate combinations and permutations from, Python has the built-in itertools module as part of its standard library. The permutations of an iterable are every possible ordering of all of the values, while the combinations are every possible selection of some, none, or all of the values. For example, the permutations and combinations of the set are:

Permutations	Combinations
ABC, ACB, BAC, BCA, CAB	(none), A, B, C, AB, AC, BC, ABC

You can also reuse the values multiple times, which is called permutations with repetition and combinations with repetition (also called replacement):

Permutations with Repetition	Combinations with Repetition
AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC	(none), A, B, C, AA, AB, AC, BB, BC, CC, AAA, AAB, AAC, ABB, ABC, ACC, BBB, BBC, BCC, CCC

(Note that permutations with repetition is effectively the same as a password cracker that tries every possible combination of characters to brute force a password.)

The number of permutations and combinations quickly grows when more values are added to the iterable object. The total number of permutations and combinations is given in the following:

Permutations of n Values	Combinations of n Values
Without Repetition	n!	2^n
With Repetition	n^n	«2n choose n», that is, (2n)! / (n!)^2

But to have Python generate permutations, you can use itertools.permutations() :

>>> import itertools >>> for v in itertools.permutations(['A', 'B', 'C']): . print(v) . ('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A') >>> >>> list(itertools.permutations(['A', 'B', 'C'])) [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')] >>> list(itertools.permutations(['A', 'B', 'C'], 2)) [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')] >>> list(itertools.permutations(['A', 'B', 'C'], 1)) [('A',), ('B',), ('C',)]

To have Python generate combinations, you can use itertools.combinations() :

>>> import itertools >>> for v in itertools.combinations(['A', 'B', 'C'], 2): . print(v) . ('A', 'B') ('A', 'C') ('B', 'C') >>> list(itertools.combinations(['A', 'B', 'C'], 1)) [('A',), ('B',), ('C',)] >>> list(itertools.combinations(['A', 'B', 'C'], 2)) [('A', 'B'), ('A', 'C'), ('B', 'C')] >>> list(itertools.combinations(['A', 'B', 'C'], 3)) [('A', 'B', 'C')]

Note that the combinations() function takes a second argument for the number of values to select. To get all combinations (also called the power set), you’ll need to make multiple calls to combinations() :

>>> powerSet = [] >>> import itertools >>> for k in range(4): . powerSet.extend(itertools.combinations(['A', 'B', 'C'], k)) . >>> powerSet [(), ('A',), ('B',), ('C',), ('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B', 'C')]

To get permutations with repetition/replacement, call itertools.product() and pass the size of the iterable object for its repeat argument:

>>> import itertools >>> for v in itertools.product(['A', 'B', 'C'], repeat=3): . print(v) . ('A', 'A', 'A') ('A', 'A', 'B') ('A', 'A', 'C') ('A', 'B', 'A') ('A', 'B', 'B') ('A', 'B', 'C') ('A', 'C', 'A') ('A', 'C', 'B') ('A', 'C', 'C') ('B', 'A', 'A') ('B', 'A', 'B') ('B', 'A', 'C') ('B', 'B', 'A') ('B', 'B', 'B') ('B', 'B', 'C') ('B', 'C', 'A') ('B', 'C', 'B') ('B', 'C', 'C') ('C', 'A', 'A') ('C', 'A', 'B') ('C', 'A', 'C') ('C', 'B', 'A') ('C', 'B', 'B') ('C', 'B', 'C') ('C', 'C', 'A') ('C', 'C', 'B') ('C', 'C', 'C') >>> list(itertools.product(['A', 'B', 'C'], repeat=3)) [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')]

To get combinations with repetition/replacement, call itertools.combinations_with_replacement() :

>>> import itertools >>> for v in itertools.combinations_with_replacement(['A', 'B', 'C'], 3): . print(v) . ('A', 'A', 'A') ('A', 'A', 'B') ('A', 'A', 'C') ('A', 'B', 'B') ('A', 'B', 'C') ('A', 'C', 'C') ('B', 'B', 'B') ('B', 'B', 'C') ('B', 'C', 'C') ('C', 'C', 'C') >>> list(itertools.combinations_with_replacement(['A', 'B', 'C'], 3)) [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'C'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'C'), ('C', 'C', 'C')]

If you’re like me and you had trouble remembering the differences between permutations and combinations, with and without repetition, and which Python functions implement them, bookmark this page to have easy access in the future.

Learn to program for free with my books for beginners:

Sign up for my «Automate the Boring Stuff with Python» online course with this discount link.

Источник

Перестановки и комбинации в Python

Перестановки и комбинации набора элементов в Python – это различные расположения элементов набора:

• Комбинация – это набор элементов, порядок которых не имеет значения.
• Перестановка – это расположение набора, в котором порядок имеет значение.

Перестановки вышеуказанного набора следующие:

('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')

Комбинации вышеуказанного набора, когда два элемента взяты вместе, следующие:

В этом руководстве мы узнаем, как получить перестановки и комбинации группы элементов в Python. Мы рассмотрим наборы символов и цифр.

Мы будем использовать методы combinations() и permutations() в модуле itertools.

Перестановки числовых данных

Чтобы использовать метод permutations() в модуле itertools, нам сначала нужно импортировать модуль.

Теперь давайте определим набор чисел.

Теперь, чтобы получить список перестановок, воспользуемся методом permutations().

perm_set = itertools.permutations(val)

Строка кода выше дает объект itertools. Чтобы напечатать различные перестановки, мы будем перебирать этот объект.

Мы получаем результат как:

1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

Полный код этого раздела приведен ниже:

import itertools val = [1, 2, 3, 4] perm_set = itertools.permutations(val) for i in perm_set: print(i)

Перестановки строки

Далее мы узнаем, как получить перестановки символов в строке.

Мы будем использовать метод permutations(), но на этот раз мы передадим строку в качестве аргумента.

import itertools s = "ABC" perm_set = itertools.permutations(s) for val in perm_set: print(val)

('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')

Перестановки фиксированной длины

Мы можем найти перестановки набора, в котором мы берем только указанное количество элементов в каждой перестановке. Это похоже на nPr в области математики.

Код для поиска перестановок фиксированной длины приведен ниже:

import itertools val = [1, 2, 3, 4] perm_set = itertools.permutations(val,2) for i in perm_set: print(i)

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

Комбинации числовых данных

Так же, как метод permutations(), мы можем использовать combinations() также в itertools для получения комбинаций набора.

При вызове combinations() нам нужно передать два аргумента: набор для поиска комбинаций и число, обозначающее длину каждой комбинации.

import itertools val = [1, 2, 3, 4] com_set = itertools.combinations(val, 2) for i in com_set: print(i)

Комбинации строки

Мы также можем получить комбинации строки. Используйте следующий фрагмент кода:

import itertools s = "ABC" com_set = itertools.combinations(s, 2) for i in com_set: print(i)

Комбинации с заменами

В модуле itertools есть еще один метод, который называется комбинациями_with_replacement(). Этот метод также учитывает комбинацию числа с самим собой.

Посмотрим, как это работает.

Для числового набора

import itertools val = [1, 2, 3, 4] com_set = itertools.combinations_with_replacement(val, 2) for i in com_set: print(i)

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

Вы можете видеть разницу в выводе выше и выводе для работы нормальной комбинации. Здесь у нас есть такие комбинации, как (1,1) и (2,2), которых нет в обычных комбинациях.

Для строки

import itertools val = "ABCD" com_set = itertools.combinations_with_replacement(val, 2) for i in com_set: print(i)

('A', 'A') ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'B') ('B', 'C') ('B', 'D') ('C', 'C') ('C', 'D') ('D', 'D')

Источник