Как сгенерировать все перестановки списка?
Как сгенерировать все перестановки списка? Например:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
5 ответ(ов)
Чтобы выполнить операции с перестановками, сочетаниями и декартовым произведением в Python, сначала импортируйте модуль itertools
:
import itertools
Перестановки (порядок имеет значение):
Чтобы получить все возможные перестановки из двух элементов списка [1, 2, 3, 4]
, используйте следующую команду:
print(list(itertools.permutations([1, 2, 3, 4], 2)))
Вывод будет следующим:
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]
Сочетания (порядок не имеет значения):
Для получения всех возможных сочетаний из двух элементов строки '123'
используйте следующий код:
print(list(itertools.combinations('123', 2)))
Вывод будет следующим:
[('1', '2'), ('1', '3'), ('2', '3')]
Декартово произведение (с несколькими итерируемыми объектами):
Чтобы получить декартово произведение массивов [1, 2, 3]
и [4, 5, 6]
, используйте следующий код:
print(list(itertools.product([1, 2, 3], [4, 5, 6])))
Результат будет таким:
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]
Декартово произведение (с одним итерируемым объектом и собой):
Для создания декартова произведения массива [1, 2]
с самим собой с повторением по 3 раза, используйте следующую команду:
print(list(itertools.product([1, 2], repeat=3)))
Вывод будет следующим:
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
Эти функции из модуля itertools
позволяют удобно работать с различными комбинациями данных в Python.
Функция permutations
генерирует все возможные перестановки строк. Давайте разберем код шаг за шагом.
def permutations(head, tail=''):
if len(head) == 0:
print(tail)
else:
for i in range(len(head)):
permutations(head[:i] + head[i+1:], tail + head[i])
Объяснение:
Параметры функции:
head
— текущая строка, из которой мы берем символы для генерации перестановок.tail
— строка, в которую мы собираем перестановку (по умолчанию пустая).
Базовый случай:
- Если длина строки
head
равна 0, это значит, что мы собрали полную перестановку и можем вывести её черезprint(tail)
.
- Если длина строки
Рекурсивная часть:
- Проходим в цикле по каждому индексу
i
в строкеhead
. - В каждом шаге рекурсивно вызываем
permutations
с новой строкойhead
без символа на позицииi
и добавляем этот символ кtail
.
- Проходим в цикле по каждому индексу
Вызов функции:
Когда мы вызываем функцию как permutations('abc')
, происходит следующее:
head
изначально равен'abc'
, аtail
пустой.- Функция будет рекурсивно генерировать и печатать все возможные комбинации символов
'a'
,'b'
, и'c'
в различных порядках.
Пример вывода:
Для строки 'abc'
функция выведет:
abc
acb
bac
bca
cab
cba
Каждый вызов функции создает новую конфигурацию строк, что позволяет эффективно генерировать все перестановки.
Вот перевод на русский язык в стиле ответа на StackOverflow:
#!/usr/bin/env python
def perm(a, k=0):
if k == len(a):
print(a)
else:
for i in range(k, len(a)):
a[k], a[i] = a[i], a[k]
perm(a, k+1)
a[k], a[i] = a[i], a[k]
perm([1, 2, 3])
Вывод:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
Как вы можете видеть, в этом коде реализована функция для генерации всех перестановок элементов списка. Обратите внимание, что для изменения содержимого списка необходимо передавать изменяемый тип последовательности. Например, вызов perm(list("ball"))
сработает, а perm("ball")
— нет, так как строки неизменяемы.
Эта реализация на Python вдохновлена алгоритмом, представленным в книге Computer Algorithms by Horowitz, Sahni and Rajasekeran.
Этот код реализует генератор, который позволяет избежать хранения всех перестановок в памяти:
def permutations(orig_list):
if not isinstance(orig_list, list):
orig_list = list(orig_list)
yield orig_list
if len(orig_list) == 1:
return
for n in sorted(orig_list):
new_list = orig_list[:]
pos = new_list.index(n)
del(new_list[pos])
new_list.insert(0, n)
for resto in permutations(new_list[1:]):
if new_list[:1] + resto != orig_list:
yield new_list[:1] + resto
В данной реализации функция permutations
принимает на вход список и генерирует все его перестановки. Начинается с проверки, является ли входной аргумент списком; если нет, он преобразуется в список. Затем функция возвращает оригинальный список с помощью оператора yield
.
Когда длина списка составляет один элемент, выполнение функции завершается. В противном случае, для каждого элемента n
из отсортированного списка, создается копия списка new_list
и удаляется текущий элемент n
. Затем n
помещается в начало нового списка.
Наконец, происходит рекурсивный вызов функции для оставшегося списка, исключая первый элемент, и генерируются все перестановки. Дается условие, которое проверяет, не равна ли текущая перестановка исходному списку, и если это так, то новая перестановка возвращается с помощью yield
.
Таким образом, этот подход позволяет эффективно генерировать перестановки, не загружая всю их комбинацию в память.
В приведённом вами коде реализуется функция для генерации всех возможных перестановок элементов списка. Вот объяснение каждой части кода в функциональном стиле.
Функция addperm(x, l)
добавляет элемент x
в список l
на все возможные позиции. Она создает новый список, который содержит все возможные варианты вставки x
в l
. С помощью генератора списков мы проходим по всем индексам i
от 0 до длины l
включительно и формируем новый список: элементы списка до индекса i
, затем элемент x
, и оставшиеся элементы списка l
после индекса i
.
def addperm(x, l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
Функция perm(l)
рекурсивно генерирует перестановки для списка l
. Если длина списка равна 0, функция возвращает список, содержащий пустой список (это базовый случай). В противном случае, она берёт первый элемент l[0]
и получает все перестановки оставшихся элементов l[1:]
с помощью рекурсивного вызова perm
. Затем для каждой из этих перестановок вызывается addperm
, чтобы вставить l[0]
на все возможные позиции.
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0], y)]
И в конце, при вызове функции print perm([i for i in range(3)])
, выводятся все перестановки списка с элементами [0, 1, 2]
.
Результаты работы программы:
[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
Таким образом, вывод соответствует всем возможным перестановкам трех элементов.
Перемешать строки DataFrame
Как изменить порядок столбцов в DataFrame?
Получение текущей даты в формате YYYY-MM-DD в Python
Как удалить пакеты, установленные с помощью easy_install в Python?
Использование @property против геттеров и сеттеров