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?
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"
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.
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?
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.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}
Last edited by Ocifer; 08-01-2011 at 12:53 PM.
Well more an exercise in combinations actually. They can be easily generated using a recursive function.Originally Posted by Angus
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"
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.
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.
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:
- 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.
- Go to the last element of the subset and increment that element (following the order of the original set, of course).
- 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.
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.
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.
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.
('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. Ordered subsets of 3 would beCode:{ A, B, C, D, E, F }, thenCode:{ A, B, C },Code:{ A, B, D }andCode:{ A, B, E }. 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 gotCode:{ A, B, F }. I don't see any resetting done here.Code:{ D, E, F }
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.
Oh I see, you're doing subsets. I was doing permutations. Sorry for the mixup.
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.
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:
- If you can't increment the current element goto 4.
- Increment the current element
- Reset all elements on the left to their lowest values
- Move left and goto 1.
- If you can increment something (maybe the nearest?) on the left goto 4.
- 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.
