Results 1 to 4 of 4

Math Help - Combinations Algorithm

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Combinations Algorithm

    I'm looking for an efficient algorithm to take a set  S=\{s_1,\ldots,s_n\} and return all possible subsets (minus  \emptyset ), where order doesn't matter.

    Example: Given  S=\{1,2,3\} , the output would be  \{1,2,3\},\;\{1,2\},\;\{1,3\},\;\{2,3\},\;\{1\},\;  \{2\},\;\{3\} .

    -Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chiph588@ View Post
    I'm looking for an efficient algorithm to take a set  S=\{s_1,\ldots,s_n\} and return all possible subsets (minus  \emptyset ), where order doesn't matter.

    Example: Given  S=\{1,2,3\} , the output would be  \{1,2,3\},\;\{1,2\},\;\{1,3\},\;\{2,3\},\;\{1\},\;  \{2\},\;\{3\} .

    -Thanks!
    The first thing that comes to mind is recursion, in particular depth first search. Are you working in a specific programming language? The basic idea is to start with an empty list and then for each element recusively do: add the element to the list, or don't.

    Looks like this in java

    Code:
    import java.util.ArrayList;
    
    public class Subsets {
        static ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
        static int[] S = {1,2,3};
       
        public static void main(String[] args) {
            getSubsets(0, new ArrayList<Integer>());
            System.out.println(subsets);
        }
       
        static void getSubsets(int x, ArrayList<Integer> list) {
            if (x==S.length) {
                if (!list.isEmpty()) subsets.add(list);
                return;
            }
            ArrayList<Integer> option1 = new ArrayList<Integer>(list);
            getSubsets(x+1, option1);
            ArrayList<Integer> option2 = new ArrayList<Integer>(list);
            option2.add(S[x]);
            getSubsets(x+1, option2);
        }
    }
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    I'm coding in Matlab. I can easily convert this code to Matlab, thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Another option is to realize that there are 2^n - 1 nonempty subsets, so there is a natural bijection between the subsets and the integers 1 through 2^n - 1. Just count from 1 to 2^n - 1 and convert each number to binary. Say an element is in the subset if its corresponding bit is 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 23rd 2009, 10:43 AM
  2. Algorithm
    Posted in the Discrete Math Forum
    Replies: 20
    Last Post: April 26th 2008, 11:26 AM
  3. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 01:02 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 2nd 2006, 12:16 AM
  5. Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 24th 2006, 12:40 AM

Search Tags


/mathhelpforum @mathhelpforum