Перестановки последовательностей Python

Следующая наша тема в обзоре структур данных — реализация функциональных возможностей для работы с последовательностями, отсутствующих во встроенных объектах Python. Функции, объявленные в примере 18.22, реализуют несколько способов перестановки элементов последовательностей:

permute

строит список всех возможных перестановок элементов последовательности

subset

строит список всех возможных перестановок указанной длины combo

действует, как subset, но порядок не имеет значения: перестановки с одинаковыми элементами удаляются.

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

Пример 18.22. PP4E\Dstruct\Classics\permcomb.py

"операции перестановки элементов последовательностей"

def permute(list):

if not list: # перестановка в любых последовательностях

return [list] # пустая последовательность

else:

res = []

for i in range(len(list)):

rest = list[:i] + list[i+1:] # удалить текущий узел

for x in permute(rest): # выполнить перестановку остальных

res.append(list[i:i+1] + x) # добавить узел в начало

return res

def subset(list, size):

if size == 0 or not list: # здесь порядок имеет значение

return [list[:0]] # пустая последовательность

else:

result = []

for i in range(len(list)):

pick = list[i:i+1] # срез последовательности

rest = list[:i] + list[i+1:] # сохранить часть [:i]

for x in subset(rest, size-1):

result.append(pick + x) return result

def combo(list, size):

if size == 0 or not list: # здесь порядок не имеет значения return [list[:0]] # xyz == yzx

else:

result = []

for i in range(0, (len(list) — size) + 1): # если осталось достаточно pick = list[i:i+1]

rest = list[i+1:] # отбросить часть [:i]

for x in combo(rest, size — 1):

result.append(pick + x) return result

Все три функции могут оперировать любыми объектами последовательностей, поддерживающими операции len, извлечения среза и конкатенации. Например, можно применить функцию permute к экземплярам некоторых классов стеков, определенных в начале этой главы (поэкспериментируйте с ними самостоятельно).

Ниже приводится несколько примеров использования наших функций перестановки. Перестановка элементов списка позволяет найти все способы, которыми могут быть упорядочены элементы. Например, для списка из четырех элементов возможны 24 перестановки (4 х 3 х 2 х 1). После выбора одного из четырех элементов для первой позиции остается только три, из которых можно выбрать элемент для второй позиции, и так далее. Порядок имеет значение: [1,2,3] не то же самое, что [1,3,2], поэтому в результате появляются оба варианта перестановки:

C:\…\PP4E\Dstruct\Classics> python

>>> from permcomb import *

>>> permute([1, 2, 3])

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

>>> permute(‘abc’)

[‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, ‘cba’]

>>> permute(‘help’)

[‘help’, ‘hepl’, ‘hlep’, ‘hlpe’, ‘hpel’, ‘hple’, ‘ehlp’, ‘ehpl’, ‘elhp’,

‘elph’, ‘ephl’, ‘eplh’, ‘lhep’, ‘lhpe’, ‘lehp’, ‘leph’, ‘lphe’, ‘lpeh’,

‘phel’, ‘phle’, ‘pehl’, ‘pelh’, ‘plhe’, ‘pleh’]

Функция combo возвращает похожие результаты, но здесь накладывается ограничение фиксированной длины, а порядок не имеет значения: abc — то же самое, что acb, поэтому только один элемент добавляется в множество результатов:

>>> combo([1, 2, 3], 3)

[[1, 2, 3]]

>>> combo(‘abc‘, 3)

[‘abc‘]

>>> combo(‘abc‘, 2) [‘ab‘, ‘ac‘, ‘bc‘]

>>> combo(‘abc’, 4)

[]

>>> combo((1, 2, 3, 4), 3)

[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

>>> for i in range(0, 6): print(i, combo("help", i))

0 [»]

1  [‘h’, ‘e’, ‘l’, ‘p’]

2   [‘he’, ‘hl’, ‘hp’, ‘el’, ‘ep’, ‘lp’]

3   [‘hel’, ‘hep’, ‘hlp’, ‘elp’]

4   [‘help’]

5   []

Наконец, функция subset представляет просто перестановки фиксированной длины — порядок здесь имеет значение, поэтому результат получается больше по объему, чем для функции combo. На самом деле вызов subset с длиной последовательности идентичен вызову функции permute:

>   >> subset([1, 2, 3], 3)

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

>   >> subset(‘abc’, 3)

[‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, ‘cba’]

>   >> for i in range(0, 6): print(i, subset("help", i))

 

Эти функции реализуют достаточно компактные алгоритмы (и кому-то может показаться, что для полного их понимания необходимо пройти через «момент истины»), но они не настолько замысловаты, чтобы вы не смогли проследить их работу на простых примерах. Кроме того, они представляют также класс операций, требующих реализации собственных структур данных, в отличие от тех, что будут продемонстрированы в последнем пункте нашего обзора структур данных.

Использованная литература:

Марк Лутц — Программирование на Python, 4-е издание, II том, 2011