CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: [RESOLVED] Permutations with repeated elements

1. Member
Join Date
Oct 2010
Posts
60

## [RESOLVED] Permutations with repeated elements

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.

2. ## Re: Permutations with repeated elements

std::next_permutation

Would that do?

3. Member
Join Date
Oct 2010
Posts
60

## 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.

4. Senior Member
Join Date
Aug 2005
Location
San Diego, CA
Posts
1,054

## 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.

5. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## 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 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:

Regards,

Paul McKenzie

6. Member
Join Date
Oct 2010
Posts
60

## 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!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•