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 position i, where i is an iterator starting from the first to the last position of each element of X. Each step, create copies of the two sets X and Y, named X1 and Y1, respectively. Let e be the element at position i in X. Let X1 be the difference of X and the set with the single element e. Append e to Y1. Repeat from top with X = X1 and Y = Y1 unless X is 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