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?

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.

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?

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.

Quote:

---

Originally Posted by Angus

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.

Quote:

---

Originally Posted by iMalc

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
}

---

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:

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.

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 :mad:)
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.

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:

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.

That ... might work. Although if I try to follow it I go from ACE -> ADE -> BDE and I don't quite get to BCE, but I might have done something wrong.

Just to be lazy, I grabbed Johnsonbaugh off the shelf. His pseudocode is a little more verbose than I remember it being (but I suppose that's okay), and you're working on a mirror image of it. His version (from page 244 of Discrete Mathematics):

Code:

---

combination(r, n) {
    for i = 1 to r
        s[i] = i
    print(s[1], ..., s[r]);
    for i = 2 to C(n,r) {
        m = r
        max_val = n
        while (s[m] == max_val) {
            // find the rightmost element not at its maximum value
            m = m-1
            max_val = max_val - 1
        }
        //the rightmost element is incremented
        s[m] = s[m] + 1
        // the rest of the elements are the successors of s[m]
        for j = m+1 to r
            s[j] = s[j-1] + 1
        print(s[1], ..., s[r])
    }
}

---

Actually, it looks like 4. would have prevented 5. and 6. from ever being executed. Perhaps it would work if I just changed that to "If you can, move left and goto 1".

In any case, I've come up w/a real class. This one just presumes that your set will be composed of integers from 0 to n - 1. I'll work on a template later that can work w/sets of any type. What do you think? I've also made what I think is a portable test suite for it.
Attachment 10779
Attachment 10780
Attachment 10781