CODEWITHSUNDEEP
algorithmmath
Dun Peal
Dun Peal

Reputation: 17679

Is there a proof of the recursive algorithm for generating all permutations of a sequence?

For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible orderings of the elements will be reached, and/or that no ordering will be duplicated.

For example, what if the elements at index 0 and 1 are swapped, then 1 and 2 are swapped? How does the algorithm guarantee this won't result in a duplicate ordering?

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]

Upvotes: 2

Views: 140

Answers (1)

Ehsan
Ehsan

Reputation: 92

Assumption: Take a set of "m" distinct objects (elements of the sequence). Take the initial sequence as l = [a1, a2, a3, ..., am].

Proposition: The algorithm given above produces "m!" distinct sequences.

Proof: Take "n = 0" and some i. The first step is to swap l[i] and l[n].

Observation: When calling "permute(l, n)", the value of "l" at indices j = {0, 1, ..., n - 1} remains intact.

Noting this observation. When calling permute(l, 0) we end up with "m" non-overlapping set of sequences. The common property of the sequences within each set is that all of them start with the same value at l[0], e.g., a1, a2, ..., am. Take A[i = j,n = 0] as the set of all such sequences obtained after swapping l[n = 0] with l[i = j]. Since for different "j", the sets are not overlapping, total sequences obtained equals N_total = n(A[0,0]) + n(A[1,0]) + ... + n(A[m - 1,0]).

Since l[0] will not be changed in the call to "permute(l, 1)" is equivalent to "permute(l', 0)" where "l'" is a subsequence of "l" obtained by removing "l[0]". A similar argument leads to obtaining "m - 1" non-overlapping subset of sequences in this call. i.e., A[i,0] will in turn be a union of "m - 1" non-overlapping sets. By induction, the final result will be a union of m! non-overlapping sets. Since each set is non-empty (guaranteed in the algorithm by checking the case where n == len(l)), then there will be at least m! distinct outputs.

On the other hand, there can be at most m! distinct permutations, therefore, the output of the algorithm will be m! distinct sequences.

Finally, note that this argument works and is applied above if you pass list by value, which I believe is the case in Python. Hope it helped.

Upvotes: 1

Related Questions