Есть ли доказательство рекурсивного алгоритма для генерации всех перестановок последовательности?

Question

Для ясности я приступаю к сжатой реализации алгоритма в Python. Я понимаю, что он проверяет все возможные свопы элементов, но я не вижу, как это обязательно означает, что все возможные упорядочения элементов будут достигнуты, и/или что никакое упорядочение не будет дублировано.

Например, что, если элементы с индексом 0 и 1 меняются местами, то 1 и 2 меняются местами? Как алгоритм гарантирует, что это не приведет к дублированию заказов?

P = [] 
def permute(l, n=0): 
    if n == len(l): 
     return P.append(list(l)) 
    for i in xrange(n, len(l)): 
     l[i], l[n] = l[n], l[i] 
     permute(l, n+1) 
     l[i], l[n] = l[n], l[i] 

Answer 1

Успение: Возьмите набор «м» различных объектов (элементов последовательности). Возьмите начальную последовательность как l = [a1, a2, a3, ..., am].

Предложение: Алгоритм, приведенный выше, дает «m!». различные последовательности.

Доказательство: Возьмите «n = 0» и некоторые i. Первым шагом является замена l [i] и l [n].

Наблюдение: При вызове «permute (l, n)» значение «l» по индексам j = {0, 1, ..., n - 1} остается неповрежденным.

Отмечая это наблюдение. При вызове перестановки (l, 0) мы получаем «m» неперекрывающийся набор последовательностей. Общее свойство последовательностей в каждом наборе состоит в том, что все они начинаются с того же значения в l [0], например, a1, a2, ..., am. Возьмите A [i = j, n = 0] как множество всех таких последовательностей, полученных после замены l [n = 0] с l [i = j]. Поскольку для разных «j» наборы не перекрываются, полученные полные последовательности равны N_total = n (A [0,0]) + n (A [1,0]) + ... + n (A [m - 1,0]).

Поскольку l [0] не будет изменен при вызове «перестановка (l, 1)», это эквивалентно «перестановке (l ', 0)», где «l» - подпоследовательность «l», полученная удалив "l [0]". Аналогичный аргумент приводит к получению неперекрывающегося подмножества последовательностей «m - 1» в этом вызове. то есть A [i, 0], в свою очередь, будет объединением неперекрывающихся множеств «m - 1». По индукции конечным результатом будет объединение m! неперекрывающиеся множества. Так как каждое множество не пусто (гарантировано в алгоритме, проверяя случай, когда n == len (l)), то будет не меньше m! отдельные выходы.

С другой стороны, может быть не более m! Следовательно, выход алгоритма будет m! различные последовательности.

Наконец, обратите внимание, что этот аргумент работает и применяется выше , если вы передаете список по значению, что, я считаю, имеет место в Python. Надеюсь, это помогло.