### N-ary Recursion & Permutations

 LA home Computing Algorithms  glossary  Recursion   Linear   Binary   Permutations   Partition   N-Queens   N-Queens 3D   Necklaces   Subgraphs   Brackets   Self-Ref   Permutations

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.Allison

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) ---