[RESOLVED] Permutations with repeated elements

[henryswanson]

I'm trying to make sets of n k-sided dice, using each number from 1 to n*k once. n and k are known at compile time. So, I thought of making an array with ints recording which die the number belongs to (then adding 1 to get rid of the 0). It'd look kinda like this: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4], for n=4, k=3. Those would be dice with {1,2,3},{4,5,6},{7,8,9},{10,11,12}.
So, to get all possible combinations of dice, I just need to get all permutations of this array. What would be a good algorithm to iterate through all of them? The permutations don't need to be in any specific order and I don't need to store a list of all of them (wayy too much memory). I thought of using Gray-code-like swapping, but I got too many repetitions to be useful.
Lastly, and I'm not sure how feasible this is, but combinations like [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4] and [2, 2, 2, 3, 3, 3, 1, 1, 1, 4, 4, 4] should not both be part of the iterations, since renumbering the dice would give a repeat. Also, if there is a better way to do this, I can just get rid of the whole array part.

[JohnW@Wessex]

std::next_permutation

Would that do?

[henryswanson]

I've tried using that, but it's far too slow. I think that might be because it produces things in a strict order. Also, it produces n! more permutations than I need, and since n is going to be around 5, that's a pretty big cost.

[kempofighter]

I'm not sure how else you could do a generic permutation algorithm without storing off previous sets. the STL is simply going to return the next biggest or previous smallest value.

123 will always yield 123, 132, 213, etc. If I start with 132, the next will always be 213. I can't think of how else you could do permutations with a generic algorithm but then again I'm not a math major either. EDIT:If you start with the lexicographically smallest combination then you can easily calculate the number of combinations and execute nextPermutation that many times. Then you don't have to worry about generating those extra arrays that are simply the reverse of a previous arrangement. It doesn't look like you are dealing with astronomical numbers here so I'm confused about why you are so concerned with speed.

[Paul McKenzie]

I've tried using that, but it's far too slow. I think that might be because it produces things in a strict order.

And maybe because you're not timing an optimized build of your program, and instead timing a "debug" or non-optimized version of the program.

Secondly, a simple question -- did the next_permutation() work? If it did, and the speed is acceptable, what is the issue? In your example, 5! == 120, IMO hardly anything to worry about.

If you're looking for combinations and not permutations, then see my contribution to the thread below:

http://www.codeguru.com/forum/showthread.php?t=241675

Regards,

Paul McKenzie

[henryswanson]

Oh, right. I keep forgetting about the debug version not being as fast as release. That really sped it up. And yeah, next_permutation() does work. Thanks!