I ended up just shuffling the array with a seed. The seed was based on a counter. This satisfied my use case "enough". But I really wanted to solve this problem. The problem is:

Given a list (say, 1, 2, 3), and a sequence number from 0..factorial(len(list)), write a linear runtime O(n) function such that perm(sequence) yields some unique permutation of the list.

A crazy idea occurred to me over a sleepless night. What if I were able to come up with a sequence of swaps based on the modulus of a sequence number that could generate a unique permutation of a list? I came up with a silly idea of using the modulus of the sequence number against the position of the array and swapping the two elements. If the modulus was zero, skip. If the modulus is 1, swap this element and the next element. If the modulus is 2, swap this element and the second element over. Then, shift to the next element and swap again. It's better if I describe what I did by hand the next morning:

Starting with 1,2,3 and sequence 0: no swaps (by definition)

Starting with 1,2,3 and sequence 1: position 1 1 mod 4 is 1, swap to get 2,1,3. Position 2 1 mod 3 is 1, swap to get 2,3,1. Done

Starting with 1,2,3 and sequence 2: position 1 2 mod 4 is 0, no swap to get 1,2,3. Position 2 2 mod 3 is 1, swap to get 1,3,2. Done

Starting with 1,2,3 and sequence 3: position 1 3 mod 4 is 3, swap to get 3,2,1. Position 2 2 mod 4 is 0, no swaps to get 3,2,1. Done.

And so on. It worked! I wrote a quick program in python:

def generatecombination(number=0,mytuple=()): for i in range(0,len(mylist)-1): modulus = number % (len(mylist) - i) if modulus > 0: swap(i,i+modulus,mylist)

Ran it for a list of 3 elements and impressive city:

[1, 2, 3]

[2, 3, 1]

[3, 2, 1]

[1, 3, 2]

[2, 1, 3]

[3, 1, 2]

It correctly generates each permutation in linear time. Success. Run it with four elements and it fails (elements are sorted to make it easier to find -- the actual order from the algorithm is different):

[1, 2, 3, 4]

[1, 3, 2, 4]

[1, 4, 3, 2]

[2, 1, 4, 3]

[2, 3, 4, 1]

[2, 4, 1, 3]

[3, 1, 2, 4]

[3, 2, 1, 4]

[3, 4, 1, 2]

[4, 1, 2, 3]

[4, 2, 1, 3]

[4, 3, 1, 2]

Each of these sequences is generated twice. This is very suspicious because there are 12 (of 24) sequences represented and 4*3 == 12. Some obvious permutations are missing, for example, 4,3,2,1 (the reverse of the original) is missing.

Suspciouser indeed, running it for 5 elements yielded 60 unique elements duplicated twice (5! == 120, 5*4*3 = 60). So my algorithm has a weakness, and the weakness is that it seems to generate only (n-1)! combinations.

def generatecombination(number=0,mytuple=()):

if number >= (len(mylist)*(len(mylist)-1)): mylist = mylist[::-1]

for i in range(0,len(mylist)-1): modulus = number % (len(mylist) - i) if modulus > 0: swap(i,i+modulus,mylist)

Aha, I thought, I could double the amount of sequences by reversing the starting elements whenever we get higher than n*n-1. Well, almost:

[1, 2, 3, 4]

[1, 2, 4, 3]

[1, 3, 2, 4]

[1, 3, 4, 2]

[2, 4, 1, 3]

[2, 4, 3, 1]

[3, 1, 2, 4]

[3, 1, 4, 2]

[4, 2, 1, 3]

[4, 2, 3, 1]

[4, 3, 1, 2]

[4, 3, 2, 1]

That's only 12+6==18 combinations, so we're still off by a certain amount. At least 4,3,2,1 exists.

Does anyone know why this algorithm works at all? Does anyone know why it fails? What am I missing?