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