8

Как сгенерировать все перестановки списка?

11

Как сгенерировать все перестановки списка? Например:

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 ответ(ов)

3

Чтобы выполнить операции с перестановками, сочетаниями и декартовым произведением в 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.

0

Функция 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])

Объяснение:

  1. Параметры функции:

    • head — текущая строка, из которой мы берем символы для генерации перестановок.
    • tail — строка, в которую мы собираем перестановку (по умолчанию пустая).
  2. Базовый случай:

    • Если длина строки head равна 0, это значит, что мы собрали полную перестановку и можем вывести её через print(tail).
  3. Рекурсивная часть:

    • Проходим в цикле по каждому индексу i в строке head.
    • В каждом шаге рекурсивно вызываем permutations с новой строкой head без символа на позиции i и добавляем этот символ к tail.

Вызов функции:

Когда мы вызываем функцию как permutations('abc'), происходит следующее:

  • head изначально равен 'abc', а tail пустой.
  • Функция будет рекурсивно генерировать и печатать все возможные комбинации символов 'a', 'b', и 'c' в различных порядках.

Пример вывода:

Для строки 'abc' функция выведет:

abc
acb
bac
bca
cab
cba

Каждый вызов функции создает новую конфигурацию строк, что позволяет эффективно генерировать все перестановки.

0

Вот перевод на русский язык в стиле ответа на 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.

0

Этот код реализует генератор, который позволяет избежать хранения всех перестановок в памяти:

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.

Таким образом, этот подход позволяет эффективно генерировать перестановки, не загружая всю их комбинацию в память.

0

В приведённом вами коде реализуется функция для генерации всех возможных перестановок элементов списка. Вот объяснение каждой части кода в функциональном стиле.

Функция 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]]

Таким образом, вывод соответствует всем возможным перестановкам трех элементов.

Чтобы ответить на вопрос, пожалуйста, войдите или зарегистрируйтесь