Thread: Function to generate permutations of sets and subsets

  1. #16
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    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):
    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])

  2. #17
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Montreal, Canada

    Finished a class

    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.

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, 06: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, 08:22 AM