# Counting permutations in ascending order

There are many ways to calculate all possible permutations of a set by
means of algorithm. I found the article on the Johnson-Trotter Algorithm quite intriguing and was
wondering if there was yet *another way to count all possible
permutations of a set*.

The **Johnson-Trotter algorithm** follows the concept of picking an
element and placing the consecutive element either to the *left* or
*right* of the previous element repeating the process unless all
elements are positioned in all possible ways. The result has an order of
its own.

*What if I were a nitpick and wanted to have it in ascending order just for convenience?*

Say, you had to find all possible permutations for the set [1,2,3] in ascending order …

## First, how many permutations are there?

You have three ways to choose the first number, two ways to choose the
second, and one way to choose the last number. Combined, you choose
3x2x1= **6** ways. That’s factorial of **3**.

*But how do you put them in ascending order?*

## Putting things in order

If there are 6 possible permutations for the set [1,2,3], and you like them in ascending order, you simply had to order them from [1,*,*], …, [2,*,*], …, [3,*,*], …

Given set **X** = [1,2,3], and set **Y** = []. Start with the
number at the first position of **X** (1). Subtract it from **X**,
which is now [2,3], and collect it in **Y**. Now, subtract the number
at the first position of **X** (2) and append it to **Y**.
Subtract the last element of **X** (3) and append it to **Y** to
get the first permutations where **Y** = [1,2,3].

For the second permutation, first reset both sets: **X** = [1,2,3],
**Y** = []. Subtract the number at the first position from **X** (1),
and add it to **Y**. But now subtract the number at the first position
**+1** from **X** (3), and append it to **Y**. Then, subtract the
remaining element of **X** (2), and append it to **Y** to get the second
permutation where **Y** = [1,3,2].

Repeat with number **2** and **3**.

When generalized and implemented via recursion, the order of the collecting sequence is changed to our advantage, and permutations are generated in ascending order in tree fashion:

[1,*,*] | -> | [1,2,*] | -> | [1,2,3] |

-> | [1,3,*] | -> | [1,3,2] | |

[2,*,*] | -> | [2,1,*] | -> | [2,1,3] |

-> | [2,3,*] | -> | [2,3,1] | |

[3,*,*] | -> | [3,1,*] | -> | [3,1,2] |

-> | [3,2,*] | -> | [3,2,1] |

**We arrive at an algorithm that states:**

Start in ascending order, from the first to the last element of a set

X. A step is to pick an element at positioni, whereiis an iterator starting from the first to the last position of each element ofX. Each step, create copies of the two setsXandY, namedX1andY1, respectively. Letebe the element at positioniinX. LetX1be the difference ofXand the set with the single elemente. AppendetoY1. Repeat from top withX=X1andY=Y1unlessXis empty.

**The solution in Ruby:**

1
2
3
4
5
6
7
8
9
**10**
11
12
13
14
15

# Ascending-ordered Permutation Generator
# author:info@elknase.com
def permute(array, tmp_array=[])
if (array.length == 0)
p tmp_array # output resulting permutation
else
for i in 0..(array.length-1)
t1_arr = array - [array[i]] # returns difference
t2_arr = tmp_array + [array[i]] # returns concatenation
permute(t1_arr, t2_arr)
end
end
end
permute([1,2,3]) # find permutations for 1,2,3 ...

**Date:**2011/12/13 10:32:33