Re: Algorithm For Calculating Permutations


eKo1 wrote:
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],

It's okay, but it's not new.

--- Christopher Heckman

s[2], ..., s[n] which is in fact all of the permutations of S.

.

Relevant Pages

  • Algorithm For Calculating Permutations
    ... I would like to propose a recursive algorithm for calculating the ... A set with all the permutations of S. Each permutation is given ... Proof of Correctness. ... 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: 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)
  • Re: is this a good way to find anagrams?
    ... > letters in your given word. ... Then loop through the word file once. ... Even faster - sort the list of permutations, ... list, then repeat, setting the lower bound of your search to the ...
    (comp.lang.ruby)