
May 18th, 2011, 10:04 AM
#1
[RESOLVED] Permutations with repeated elements
I'm trying to make sets of n ksided 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 Graycodelike 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.

May 18th, 2011, 10:46 AM
#2
Re: Permutations with repeated elements
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman

May 18th, 2011, 12:25 PM
#3
Re: Permutations with repeated elements
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.

May 18th, 2011, 06:12 PM
#4
Re: Permutations with repeated elements
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.
Last edited by kempofighter; May 18th, 2011 at 06:34 PM.

May 18th, 2011, 06:28 PM
#5
Re: Permutations with repeated elements
Originally Posted by 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.
And maybe because you're not timing an optimized build of your program, and instead timing a "debug" or nonoptimized 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

May 18th, 2011, 08:14 PM
#6
Re: Permutations with repeated elements
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!
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
