может ли кто-нибудь объяснить этот алгот для перестановки мне?

Question

Может ли кто-нибудь объяснить мне этот перестановочный алго мне? Я знаю, что это pemutations, но я не могу понять, почему это работает.

s = [1,2,3,4,5,6,7,8,9] 
def perm(s, i): 
    if i == len(s): 
     print s 
    for j in range(i, len(s)): 
     s[i], s[j] = s[j], s[i] 
     perm(s, i + 1) 
     s[i], s[j] = s[j], s[i] //why it swaps back?  

Answer 1

Эта функция мутирует массив s в каждую возможную перестановку, затем печатает перестановку и изменяет мутацию на обратном пути.

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

Мне очень полезно понять эту рекурсию, чтобы добавить дополнительные «отладочные отпечатки» в код в интересных точках, таких как начало и конец функции, и в этом случае при свопах.

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

def perm(s, i): 
    print '{padding}starting perm({list}, {index})'.format(list=s, index=i, padding=' '*i) 
    if i == len(s): 
     print s 
    for j in range(i, len(s)): 
     print '{padding}swapping s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i) 
     s[i], s[j] = s[j], s[i] 
     perm(s, i + 1) 
     print '{padding}swapping back s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i) 
     s[i], s[j] = s[j], s[i] 
    print '{padding}returning from perm({list}, {index})'.format(list=s, index=i, padding=' '*i) 

Answer 2

он обменивает назад, потому что это питон код, который означает, что s (список) изменчив, поэтому изменения, внесенные в него в вызываемой функции влияют на массив в вызывающей программе.

Если он не поменялся, тогда массив будет находиться в «странном» состоянии (слева от предыдущих вызовов) после возврата вызова.

альтернатива, которая не должно нуждаться в мутации, является:

s = [1,2,3,4,5,6,7,8,9] 
def perm(s, i): 
    s = list(s) # copy before mutating 
    if i == len(s): 
     print s 
    for j in range(i, len(s)): 
     s[i], s[j] = s[j], s[i] 
     perm(s, i + 1) 

или, возможно, яснее:

 
    s = [1,2,3,4,5,6,7,8,9] 
      def perm(s, i): 
        if i == len(s): 
            print s 
        for j in range(i, len(s)): 
            s[i], s[j] = s[j], s[i] 
            perm(list(s), i + 1) # pass a copy 

комментария уверен, почему это было downvoted. пользователь сделал несколько комментариев по этому вопросу одновременно, но затем удалил их. я думаю, что они ошибались, и я думаю, что удаление комментариев означает, что они это поняли, но я не понимаю, почему они также не удалили нисходящее (если это было их). альтернативно, если это неправильно, пожалуйста, объясните кому-нибудь, чтобы я мог узнать ...