Function to generate permutations of sets and subsets

This is a discussion on Function to generate permutations of sets and subsets within the C++ Programming forums, part of the General Programming Boards category; I have a set and need to get all the permutations of that set and all permutations of all its ...

  1. #1
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115

    Function to generate permutations of sets and subsets

    I have a set and need to get all the permutations of that set and all permutations of all its subsets. STL has a nice clean function that does permutations, but alas, it does not generate permutations of subsets.
    For a concrete refresher on permutations: you can have permutations that take a set of, say, 6 elements and generate permutations that are sets of 6, but I need but I need to generate sets that are less than 6. STL's function doesn't do that. Is there one that does?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    What you're after then is all the permutations of the power set of a set.
    You could first generate the power set, then for each one of those, generate all permutations.
    A warning though, I would put a cap on the size of the initial set to accept. If the initial set contains say even 20 items then the code will probably take many years to finish.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    Ok, the power set. I'm not sure what you suggest is as simple as you think, because generating a power set is an exercise in permutations in itself.

  4. #4
    Registered User
    Join Date
    Apr 2010
    Posts
    82
    The power set of finite set V, has cardinality 2 ^ (cardinality of V), so make sure you heed iMalc's warning.

    Bear in mind that this includes the null set and V and itself. My guess is you want the non-trivial, proper subsets of your set?

    Code:
    suppose A = {2,4,7,13}
    
    Subsets of length n below, using indices 0-3 to describe the set's (array's) original elements:
    
    of length 0:
    {}  (not too interesting for permuting)
    of length 1:
    {0} {1} {2} {3} (not to interesting for permuting either)
    of length 2:
    {0,1} {0,2} {0,3} {1,2} , {1,3} , {2, 3}
    ... etc
    
    for our particular set A, subsets of length 2 translate to
    
    {2,4} {2, 7} {2, 13} {4, 7} {4, 13}, {7, 13}
    I'm not sure if this is the optimal way to approach it, or if the above is easily (non-uglily) implemented. One advantage I can think of with the above is that you won't double-count subsets by counting {2,4} and {4,2}. But I've not tried this problem before. Out of curisoity, what are you working on? Is this just a personal exercise? It's a cool question.
    Last edited by Ocifer; 08-01-2011 at 12:53 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Angus View Post
    Ok, the power set. I'm not sure what you suggest is as simple as you think, because generating a power set is an exercise in permutations in itself.
    Well more an exercise in combinations actually. They can be easily generated using a recursive function.
    Or, you can use the relation to binary to generate them, after reading about this on wikipedia to give you a hint.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Apr 2010
    Posts
    82
    Quote Originally Posted by iMalc View Post
    Well more an exercise in combinations actually. They can be easily generated using a recursive function.
    Or, you can use the relation to binary to generate them, after reading about this on wikipedia to give you a hint.
    My choice would be the binary way, actually upon reading this, cool stuff.

    To iMalc: Would this be the rough idea?

    Code:
    Pseudocode, will be using ^ as exponentiation:
    
    Given a set A = { a_1, a_2, ... , a_n } ,   first calculate 2^n
    
    for( i=0 ; i < 2^n ; i++ ){
      find binary string representing i;
      use binary string to build a subset with element inclusion decided by 1 or 0 
    }
    Last edited by Ocifer; 08-01-2011 at 01:19 PM.

  7. #7
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    It's a good bit more cool than I'd like it to be. It's part of an job application demo I'm supposed to make. What I'm supposed to do is take 6 random operands and try to make them equal another random number using whatever operators I can. Since a viable solution involves any subset of these operands, I've got this added headache of coming up w/all permutations of the power set.
    However, this is getting a lot hairier than it should, getting into generating power sets and then its permutations. I think I'm just going to have a brute force permutation class where all the combinations of the elements from the original set are tried, and any combination with a repeating element is thrown out. Thanks for your help.

  8. #8
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    It just occurred to me what Ocifer was saying. A very conceptually simple algorithm is within reach for this. To generate the power set you get k-permutations of n and then just keep decrementing k. Now this OP problem of k-permutations of n can be solved by using STL's permutation function and by generating unique, sorted subsets. That last part is where my brain ground to a halt, and it is done this way:
    1. Make a subset of the first k elements of the set. This will be like your master subset and each time you change it, you generate a new, unique subset.
    2. Go to the last element of the subset and increment that element (following the order of the original set, of course).
    3. Once you max out that last element, go back to 2. and do the same thing w/the previous element.

    Now correct me if I'm wrong, but all the subsets generated in 2. will be unique, won't they? Plugging them into next_permutation() should yield more unique subsets and all the unique subsets of size k.

    I think I'll make a class that does this and post it on CodeProject. Hopefully, some others will think it's cool, too. I'm sure someone will wind up using it, considering the miserable time I had trying to find a library that does this.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    That's the typical "odometer" algorithm -- you have to be a little careful with going back because you may have several slots "roll over" at the same time, plus each one rolls over at a different place (for say k=9, the last number can be 9, but the second-last number can only go to 8 (which forces the last digit to be 9)). Most discrete math texts have the algorithm, I think; I can certainly reach up to the shelf and grab one if you want.

  10. #10
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    Well if "odometer" is the right name, it seems poorly chosen, since odometers cover all combinations of a set. I'm not sure why you think there's a danger of roll over, since it seems fairly simple to avoid.
    Perhaps I should give my technical definition to "max out" which is "in a state wherein it cannot be incremented and still keep the elements in the subset unique". So in the case of the last element of the subset, it maxes out at the last element of the set, and for all the other elements, they max out when they run up against the value of the next element.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Well, you're probably doing it, just not stating it: once you increment a number you've got to reset the ones after it, so after 129 comes 134 (as opposed to 139). If you've got that, you're probably good.

  12. #12
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    ('Looks like this forum isn't going to let me express sets w/out code tags )
    Hmm... I think we need a concrete example.
    Say we have a set
    Code:
    { A, B, C, D, E, F }
    . Ordered subsets of 3 would be
    Code:
    { A, B, C }
    , then
    Code:
    { A, B, D }
    ,
    Code:
    { A, B, E }
    and
    Code:
    { A, B, F }
    . We've maxed out the 3rd element. All of those are subsets that would be plugged into STL's function to be shuffled around. Then you would do the same for the 2nd element and when it reached E, it's maxed out, being "up against" the F. Skipping ahead a few, finally, you've got
    Code:
    { D, E, F }
    . I don't see any resetting done here.
    Then you've been through all the ordered subsets, and, plugging those subsets into next_permutation(), you'd have all the 3-permutations of 6, and no duplicates.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Oh I see, you're doing subsets. I was doing permutations. Sorry for the mixup.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Actually, no wait, we were looking at the same thing: How do you ever get A, C, D? If I'm reading what you've written properly, you generate
    ABC
    ABD
    ABE
    ABF
    ACF
    ADF
    AEF
    BEF
    CEF
    DEF
    There are 6C3 = 20 sets we should be looking at, but you've only got 10.

  15. #15
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    You're right: I'm screwed.
    Perhaps the trick is not to go one element at a time, but every you increment an element, you first reset all elements to the left to their lowest values, and then work your way left, incrementing and maxing out. So this would have:
    ABC
    ABD
    ACD
    BCD
    ABE
    ACE
    BCE
    ADE
    BDE
    CDE
    and so on.
    What do you think:
    1. If you can't increment the current element goto 4.
    2. Increment the current element
    3. Reset all elements on the left to their lowest values
    4. Move left and goto 1.
    5. If you can increment something (maybe the nearest?) on the left goto 4.
    6. If you can't move right, you are done. Otherwise, move right and goto 1.

    I guess that would fix it, and since elements never overtake their neighbours on the left, there shouldn't be any duplicates.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. subsets filling the gaps question..
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 07-06-2009, 04:51 AM
  2. How to do array subsets?
    By gormster in forum C Programming
    Replies: 5
    Last Post: 11-14-2007, 05:50 AM
  3. Subsets of binary string
    By damonbrinkley in forum C Programming
    Replies: 4
    Last Post: 05-03-2005, 09:00 AM
  4. compute the subsets of a set
    By k_w_s_t_a_s in forum C Programming
    Replies: 4
    Last Post: 06-01-2003, 05:54 PM
  5. subsets
    By scottmanc in forum C++ Programming
    Replies: 7
    Last Post: 03-11-2003, 07:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21