Thread: Function to generate permutations of sets and subsets

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.
aipermutations.cpp
aipermutations.h
permutationsuite.cpp