Combinations Algorithm

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
I'm looking for an efficient algorithm to take a set \(\displaystyle S=\{s_1,\ldots,s_n\} \) and return all possible subsets (minus \(\displaystyle \emptyset \)), where order doesn't matter.

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

-Thanks!
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
I'm looking for an efficient algorithm to take a set \(\displaystyle S=\{s_1,\ldots,s_n\} \) and return all possible subsets (minus \(\displaystyle \emptyset \)), where order doesn't matter.

Example: Given \(\displaystyle S=\{1,2,3\} \), the output would be \(\displaystyle \{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);
    }
}
 
  • Like
Reactions: [email protected]

[email protected]

MHF Hall of Honor
Sep 2008
1,163
429
Champaign, Illinois
I'm coding in Matlab. I can easily convert this code to Matlab, thanks!
 

awkward

MHF Hall of Honor
Mar 2008
934
409
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.