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; That ... might work. Although if I try to follow it I go from ACE -> ADE -> BDE and ...

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

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

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

Page 2 of 2 FirstFirst 12
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, 05: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, 10: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, 06:54 PM
  5. subsets
    By scottmanc in forum C++ Programming
    Replies: 7
    Last Post: 03-11-2003, 08:22 AM

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