[RESOLVED] Permutations with repeated elements
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: [RESOLVED] Permutations with repeated elements

  1. #1
    Join Date
    Oct 2010
    Location
    St Paul, MN
    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. #2
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Permutations with repeated elements

    std::next_permutation

    Would that do?
    "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

  3. #3
    Join Date
    Oct 2010
    Location
    St Paul, MN
    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. #4
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Question 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. #5
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Permutations with repeated elements

    Quote Originally Posted by henryswanson View Post
    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

  6. #6
    Join Date
    Oct 2010
    Location
    St Paul, MN
    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!

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center