An Arbitrary List Permutation Algorithm

On occasion I find myself needing to be able to take a list of data and generate permutation number n of all possible permutations. I've developed a neat, simple algorithm to do so and I've added two new List methods to the Rogue Standard Library to make generating arbitrary list permutations easy.

First is the permutation count, which is just the factorial of the list count - a list of 4 values can have 4*3*2*1 = 24 orderings:

class List<<$DataType>>
...
    method permutation_count->Int64
      if (count == 0) return 0

      local c = 1 : Int64
      forEach (n in 2..count)
        c *= n
      endForEach

      return c

Next is the actual permutation generator that accepts a permutation number between 0 and permutation_count-1. If you send it 0 you'll get the list in the original order, if you send it the max value you'll get the list in reverse order, and all numbers in between give you a different unique ordering. It accepts an optional output list to allow for minimal dynamic allocation:

method permutation( n:Int64, output_list=null:$DataType[] )
    ->$DataType[]
  if (not output_list) output_list = $DataType[]( count )
  output_list.clear
  if (count == 0) return output_list

  forEach (value in this) output_list.add( value )

  local c = count
  while (c)
    output_list.add( output_list.remove_at(n % c) )
    n /= c
    --c
  endWhile

  return output_list

First the output list is filled with the data values in the original order. Then values are removed one by one from arbitrary spots dictated be the permutation number n and added to the end of the list, similar to how insertion sort works.

The math determining which index to remove next is simple and yet a bit difficult to explain. Let me start with a discussion of converting 2D coordinates to a single index and back.

If you have a 3x4 array (columns x rows in this case) you can represent a specific cell using a pair of (x,y) coordinates or a single cell index. In the table below the intersection of any pair of (x,y) coordinates contains the cell index of that location. For example we could use the (x,y) coordinates (1,2) or the cell index 7 to refer to the 2nd column on the 3rd row:

The formulas to convert between (x,y) and a single cell index are as follows:

index = y * width + x   # 'width' is 3 in the above table
max_index = height * width - 1
...
x = index % width
y = index / width

We can do the same thing in three dimensions like this:

index = ((z * height) + y) * width + x
max_index = depth * height * width - 1
...
x = index % width
index /= width
y = index % height
z = index / height

To create a permutation of a 4-count list you first choose between 4 values, then the 3 remaining values, then the remaining 2, then the last 1 - it's effectively a multidimensional data set with dimensions 4*3*2*1. So given an arbitrary permutation number n between 0 and 4*3*2*1 - 1 we can convert n into a series of locations by using the same cell index decoding technique:

# Pick 1 of 4 original values to remove
first_index = n % 4  
n /= 4

# Pick 1 of 3 remaining
second_index = n % 3
n /= 3

# Pick 1 of 2 remaining
third_index = n % 2
n /= 2

# Last one
fourth_index = n % 1
n /= 1

The proof is in the pudding; here's my test program and its output!

# Test.rogue
local numbers = (1..4)->Int32[]
forEach (n in 0..(numbers.permutation_count-1))
  println "$$" (n->String.left_justified(3), numbers.permutation(n))
endForEach

# Console Log
> roguec Test.rogue --execute
Writing Test.h...
Writing Test.cpp...
g++ Test.cpp -o test && ./test 

0   [1,2,3,4]
1   [2,1,3,4]
2   [3,1,2,4]
3   [4,1,2,3]
4   [1,3,2,4]
5   [2,3,1,4]
6   [3,2,1,4]
7   [4,2,1,3]
8   [1,4,2,3]
9   [2,4,1,3]
10  [3,4,1,2]
11  [4,3,1,2]
12  [1,2,4,3]
13  [2,1,4,3]
14  [3,1,4,2]
15  [4,1,3,2]
16  [1,3,4,2]
17  [2,3,4,1]
18  [3,2,4,1]
19  [4,2,3,1]
20  [1,4,3,2]
21  [2,4,3,1]
22  [3,4,2,1]
23  [4,3,2,1]