Challenge: recreate a permutation list entry from an index

[Swash004]

Consider a series of digits (say 1-6). We know that there are 6 factorial or 720 different arrangements of these digits. Tt is possible to create these 720 examples in a table, and sort them into a standard sequence, give each one a unique index, and use a simple Vlookup to find any given arrangement.

Now for the challenge: if there are more integers (say 12) the list becomes 479 Million rows - too much for Excel. Can someone help me calculate (formulae or VBA) from a given index what the unique series arrangement would be if we had a complete database of them stored as above?

The first position can be done like this: 1+(given index / int(fact(11)-1))

thanks

Swash004

 

[Damon Ostrander]

Hi Swash004,

If I understand your question correctly, you would like an algorithm (it could be implemented via either a VBA function or macro, or via worksheet formulas) that given an index in the range from 1 to N! would generate one of the permutations, with no permutation being repeated over the entire range, and a particular index always returning the same permutation.

I have a solution in mind that I believe could be easily implemented, but because this question requires quite a bit of thought and is interesting, why not suggest it to Bill Jelen as a Challenge of the Month? That way this problem would get much more exposure and potentially a much better solution.

My approach would be to implement it as a VBA array function (UDF) that would yield N values (N=6 in this case, but I believe this could be generalized) given a Long integer index value.

Damon

PS. If you are in too much of a hurry to pose it as a Challenge and wait for a solution, let me know and I'll PM you my solution.

 

[Swash004]

Damon,

You are correct in your assessment of the challenge. My VBA attempt to date feels like your suggestion - N nested loops creating values and an overall counter up to the given index. Kinda tricky, but doable. However, since the N in N! changes, the nesting has to be recursion, and the rules are similar - but not identical. My version is also currently resisting my overall counter (Global Variable). I had not considered actually storing the array of values. I would also like to optimize the routine to shorten the number of necesary cycles when N > 7 or so.

I'd be fine with proposing this as a challenge of the month, but do not know how. I am a newby to this forum.

 

[Damon Ostrander]

Hi again Swash004,

I checked and found out that there is already a Challenge of the Month for March and April, and May is quite a while to wait, so I'll take a crack at your problem and let you know. It could be a day or two before I get back to you.

Damon

PS. you can find out about the Challenge here:

http://www.mrexcel.com/challenge.shtml