Algorithm For Calculating Permutations

I would like to propose a recursive algorithm for calculating the
permutations of a set S = {s[1], s[2], ..., s[n]} and a proof of its
correctness. I would very much appreciate if someone can give me the
thumbs up that it is OK. Here we go.

Input: A set of n > 1 elements, S = {s[1], s[2], ..., s[n]} and n.
Output: A set with all the permutations of S. Each permutation is given
as a tuple.

function permutation(S, n)
begin
if n = 1 then
return {s[1]}
end if

if n = 2 then
return {(s[1], s[2]), (s[2], s[1])}
end if

P := {}

for i := 1 to n do
S' := S - {s[i]}
P' := permutation(S', n - 1)

for each tuple t = (t[1], t[2], ..., t[n - 1]) in P' do
replace t with {(s[i], t[1], t[2], ..., t[n - 1]) in P'
done

add all the elements of P' to P
done

return P
end

Proof of Correctness. The proof is by induction on n.

Basis Step. If n = 1, then S contains one element and the permutation
of that is just the element which is exactly what the first if
statement returns. If n = 2, then the two permutations are s[1] s[2]
and s[2] s[1] which is exactly what the algorithm returns in the second
if statement (albeit in tuple form).

Inductive Step. Assume the algorithm correctly returns all the
permutations of S = {s[1], ..., s[n - 1]}. Consider the execution of
the algorithm with S = {s[1], ..., s[n]}. The algorithm immediately
proceeds to the for loop. During the ith iteration of the for loop, the
permutations of S - {s[i]} is stored in P' (by the inductive assumption
since |S - {s[i]}| = n - 1). For each permutation, we add s[i] to the
front so that each permutation in P' begins with s[i]. In otherwords,
P' contains all the permutations of S that start with s[i]. All these
permutations are added to P at the end of the for loop. When the for
loop terminates, P contains all the permutations that begin with s[1],
s[2], ..., s[n] which is in fact all of the permutations of S.

.

Relevant Pages

  • Re: Algorithm For Calculating Permutations
    ... A set with all the permutations of S. Each permutation is given ... Proof of Correctness. ... The proof is by induction on n. ... During the ith iteration of the for loop, ...
    (comp.theory)
  • Re: how to use perms when my n is greater than 10?
    ... I had a similar problem and I thought I use a reverse process to ... generate the permutations one at a time and use it in a loop from 1 ... permutations by imagining a loop generating the permutations. ... since n nested loops would generate the combination. ...
    (comp.soft-sys.matlab)
  • Re: balanced REDUCE: a challenge for the brave
    ... Composition of permutations can be used. ... loop -rot 2drop; ... swap over swap hshift swap r> hshift +; ...
    (comp.lang.forth)
  • Re: hard recusive problem?
    ... I'm trying to write a recursive algorithm that generates all the possible ... This doesn't generate allpermutations though because you are ... How do you generate all possible valid RPN expressions directly? ... possibilities except they are for a single binary operator. ...
    (sci.math)
  • Re: Permutations
    ... Jose wrote: ... like to get all possible permutations of the list, ... A neat way to do this is to loop a number from 1 to 2^(number of things ... and include in the selection 'Red' if the first bit ...
    (microsoft.public.dotnet.languages.csharp)