Computing a permuation from its number

[W3bbo]

I'm writing a program that generates every possible valid Mastermind code.

That itself is easy. There are 6 colors in 4 possible positions. Cycling through them all is done like so:

for(int i = 0 to 1295 ) { // 1295 == 6^4 - 1, there are 1296 possible permutations of colors
    
    color1 = ( i / 6 ^ 0 ) % 6;
    color2 = ( i / 6 ^ 1 ) % 6;
    color3 = ( i / 6 ^ 2 ) % 6;
    color4 = ( i / 6 ^ 3 ) % 6;
    
}

where each color is represented by a number ( 0 = red, 1 = blue, etc )

which gives combinations like so:

(begin)
0000
0001
0002
...
3005
3010
...
5554
5555
(end)

So that's all perfectly fine.

Now, how do I do the same but for cases where there cannot be duplicate colors?

I know the size of the set is 6*5*4*3 = 360 elements

So I want my loop to be something like this:

for(int i=1;i<=360;i++) {
    
    color1 = // what, exactly?
    
}

So how can I convert a number between 1 and 360 into a permutation of colors?

Thanks!

 

[Hurkyl]

I'm writing a program that generates every possible valid Mastermind code.

That itself is easy. There are 6 colors in 4 possible positions. Cycling through them all is done like so:

for(int i = 0 to 1295 ) { // 1295 == 6^4 - 1, there are 1296 possible permutations of colors
    
    color1 = ( i / 6 ^ 0 ) % 6;
    color2 = ( i / 6 ^ 1 ) % 6;
    color3 = ( i / 6 ^ 2 ) % 6;
    color4 = ( i / 6 ^ 3 ) % 6;
    
}

where each color is represented by a number ( 0 = red, 1 = blue, etc )

It would be even easier to avoid doing anything fancy:

for(color1 = 0 to 5)
for(color2 = 0 to 5)
for(color3 = 0 to 5)
for(color4 = 0 to 5) {
// do something
}

 

[W3bbo]

It would be even easier to avoid doing anything fancy:

for(color1 = 0 to 5)
for(color2 = 0 to 5)
for(color3 = 0 to 5)
for(color4 = 0 to 5) {
// do something
}

Easier, yeah; but due to requirements elsewhere in the program I need to be able to derive a permutation from a number.

 

[Stephen Tashi]

From the perspective of computer programming, your question is repulsive since it seems simpler to store the permutations in an array and then use the index of the array as a method of getting the Nth permutation.

However, as a purely mathematical question it does have some interest. To discuss the matter, consider the simpler case of the permuations of {1,2,3}. We can order these by using the convention that the smaller of two permutations is the one that has the smaller first entry and if the first entries are equal, the smaller is the one that has the smaller second entry, etc.

This puts the list in the order of
N
1. (1,2,3)
2. (1,3,2)
3. (2,1,3)
4. (2,3,1)
5. (3,1,2)
6. (3,2,1)

It's clear that we can the first entry in the list by dividing N+1 by 2 using integer division. But how do we get the second entry? Anyone see a simple formula for the progression 2,3,1,3,1,2 ?

An interesting number theory question is the following: Given a finite string of digits base M, do there exist constants A and B such that (A + B*N) mod M is equal to the Nth digit in the string?

Another thought is to look for a formula that uses the valule of icolor1 to aid in finding icolor2.

 

[Hurkyl]

The direct path to answering the question originally asked, I think, is to apply exactly same trick that leads to the first for-loop in the opening post, with index from 0 to 1295.

Of course, one is unlikely to work through the details if they're unwilling to take the first step and write down the obvious solution to the problem.


Honestly, I think this is an issue of premature optimization -- the opening poster is spending far more effort trying to come up with an elegant solution, clever, or (alledgedly) efficient solution, rather than just implement a dumb solution that is more than adequate for the task.


I take pride in the fact I've written more bubble sorts than any other kind. I can write them quicker than other sorts, and it let's me focus my time on the parts of the program that really matter, rather than shaving a few microseconds off of my sorting by using a different method.

(I would, of course, spend more time on the sort if I was actually sorting a huge list, or doing the sort a huge number of times. But even then I might wait until I've confirmed it's taking a sizable proportion of my program's time)