Алгоритм для генерации всех возможных перестановок списка?
Скажите, что у меня есть список n элементов, я знаю, что существуют n! возможные способы заказать эти элементы. Что алгоритм должен генерировать все возможные упорядочивания этого списка? Пример, у меня есть список [a, b, c]. Алгоритм возвратился бы [[a, b, c], [a, c, b], [b, a, c], [b, c], [c, a, b], [c, b]].
Я читаю это здесь http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
Но Википедия никогда не была способна объяснять. Я не понимаю большую часть его.
2 ответа
По сути, для каждого элемента слева направо генерируются все перестановки оставшихся элементов (и к каждому добавляются текущие элементы). Это можно делать рекурсивно (или итеративно, если вам нравится боль) до тех пор, пока не будет достигнут последний элемент, и в этот момент существует только один возможный порядок.
Итак, со списком [1,2,3,4] генерируются все перестановки, начинающиеся с 1, затем все перестановки, начинающиеся с 2, затем 3, затем 4.
Это эффективно уменьшает проблему с единицы. поиска перестановок списка из четырех элементов в список из трех элементов. После сокращения до 2, а затем 1 списков, все они будут найдены.
Пример, показывающий перестановки процессов с использованием 3 цветных шариков:
(из https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg )
Самый простой способ, который я могу придумать, чтобы объяснить это, - использовать некоторый псевдокод
, поэтому
list of 1, 2 ,3
for each item in list
templist.Add(item)
for each item2 in list
if item2 is Not item
templist.add(item)
for each item3 in list
if item2 is Not item
templist.add(item)
end if
Next
end if
Next
permanentListofPermutaitons,add(templist)
tempList.Clear()
Next
Очевидно, что это не самый гибкий способ сделать это, и, по моему мнению, выполнение его рекурсивно было бы намного более функциональным. усталый мозг воскресной ночью не хочет думать об этом в данный момент. Если к утру рекурсивную версию никто не выставит, я ее сделаю.