N-ary Recursion & Permutations

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

Algorithms
 glossary
 Recursion
  Linear
  Binary
  Permutations
  Partition
  N-Queens
  N-Queens 3D
  Necklaces
  Self-Ref

The most general form of recursion is n-ary recursion where n is not a constant but some parameter of a routine. Routines of this kind are useful in generating combinatorial objects such as permutations. The permutations of the integers 1..3 are:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Permutations of 1..3
There are three choices for the value in each column above (except that no integer can be repeated in a permutation) and three nested loops could be used to iterate through all 3! permutations:
for i1 :1..3
   for i2 :1..3
      if i2 ~= i1 then
         for i3 :1..3
            if i3 ~= i1 and i3 ~= i2 then
               print i1, i2, i3
            end if
         end for
      end if
   end for
end for
However this is ugly and cannot be generalised to produce permutations of 1..n where n is not a constant. The solution is to write a recursive procedure which contains just one loop. Within the loop, the procedure calls itself recursively. This gives the effect of a variable number of nested loops.

Permute(unused, p, L, N)
   if(L > N)
      process the permutation p
   else
      for each i in unused do
         p[L]=i;
         Permute(unused-{i}, p, L+1, N)    <---recursion
      end for
   end if
end Permute;

Permute({1..n}, p, 1, n)  -- initial call

A set is used to hold the free `unused' choices and to ensure that all elements of a permutation differ. Initially all marks are unused. Unused is reduced as choices are made and it is passed on through recursive calls. (If your programming language does not have set as a built in data type, you can implement it as a bit-mask, or as an array of boolean or of integer.)

L
.
A
l
l
i
s
o
n

There are a great many ways to visualise the calls that Permute makes on itself:

-: Permute({1,2,3}, [-,-,-], 1, 3)
   1: Permute({2,3}, [1,-,-], 2, 3)
      1.1: Permute({3}, [1,2,-], 3,3)
           1.1.1: Permute({}, [1,2,3], 4, 3) --> 1,2,3
      1.2: Permute({2}, [1,3,-], 3,3)
           1.1.1: Permute({}, [1,3,2], 4, 3) --> 1,3,2
   2: Permute({1,3}, [2,-,-],  2, 3)
      2.1: Permute({3}, [2,1,-], 3,3)
           1.1.1: Permute({}, [2,1,3], 4, 3) --> 2,1,3
      2.2: Permute({1}, [2,3,-], 3,3)
           1.1.1: Permute({}, [2,3,1], 4, 3) --> 2,3,1
   3: Permute({1,2}, [3,-,-], 2, 3)
      3.1: Permute({2}, [3,1,-], 3,3)
           1.1.1: Permute({}, [3,1,2], 4, 3) --> 3,1,2
      3.2: Permute({1}, [3,2,-], 3,3)
           1.1.1: Permute({}, [3,2,1], 4, 3) --> 3,2,1

--- Call Trace of Permute ---


                      -: Permute({1,2,3}, [-,-,-], 1, 3)
                   .     .
                .           .
             .                 .
          .                       .
         1: Permute({2,3}, [1,-,-], 2, 3)
        .   .                            .
       .       .                            .
      .           .                          2: Permute({1,3}, [2,-,-], 2, 3)
     .               .                          etc.
    .                   .                      3: Permute({1,2}, [3,-,-], 2, 3)
   .                       .                       etc.
1.1: Permute({3}, [1,2,-], 3, 3)
  . .                              .
  .    .                            1.2: Permute({2}, [1,3,-], 3, 3)
  .       .
1.1.1: Permute({}, [1,2,3], 4, 3)
                .
                   .
                   1.2.1: Permute({}, [1,3,2], 4, 3)

--- Partial Tree of Calls for Permute({1,2,3}, p, 1, 3) ---

See also the later section on tree traversal.

Notes

  • There are iterative, non-recursive routines to generate permutations.
  • Many other `combinatorial objects' can be generated by similar routines.
  • An application of permutations is to test parallel programs that take inputs from different devices, simulating input from these devices in many different orders (permutations) to test for dead-lock situations.


L.A.©, Dept. Comp. Sci. UWA 1984-1986,
and (HTML) School of Comp. Sci. and Software Engineering, Monash University 1999
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 27-Nov-2014 09:49:17 EST.