What't the best solution for creating subsets of a set of characters?

Question

I know 'best' is subjective, so according to you, what is the best solution for the following problem:

Given a string of length n (say "abc"), generate all proper subsets of the string. So, for our example, the output would be {}, {a}, {b}, {c}, {ab}, {bc}, {ac}. {abc}.

What do you think?

Answer 1

def subsets(s):
    r = []
    a = [False] * len(s)
    while True:
        r.append("".join([s[i] for i in range(len(s)) if a[i]]))
        j = 0
        while a[j]:
            a[j] = False
            j += 1
            if j >= len(s):
                return r
        a[j] = True

print subsets("abc")

Answer 2

You want the power set. It can be calculated recursively and inductively. ;-)

Answer 3

Pardon the pseudo code...

int i = 0;
Results.push({});

While(i > Inset.Length) {
   Foreach(Set s in Results) {
    If(s.Length == i) {
       Foreach(character c in inSet)
          Results.push(s+c);
    }
    i++;
}

Answer 4

The recursive approach -- the subsets of "abc" come in two types: those which are subsets of "bc", and those which are "a" plus a subset of "bc". So if you know the subsets of "bc", it's easy.

Alternatively, a string of length n has 2^n subsets. So write two nested loops: i counts from 0 to 2^n -1 (for the subsets), and j counts from 0 to n-1 (for characters in the ith subset). Output the jth character of the string if and only if the jth bit of i is 1.

(Well, you did say that "best" was subjective...)

Answer 5

Interpret a number in binary representation as indicating which elements are included in the subset. Let's assume that you have 3 elements in your set. Number 4 corresponds to 0100 in binary notation, so you will interpret this as a subset of size 1 that only includes 2nd element. This way, generating all subsets is counting up to (2^n)-1

    char str [] = "abc";
 int n = strlen(str); // n is number of elements in your set

 for(int i=0; i< (1 << n); i++) { // (1 << n) is equal to 2^n
  for(int j=0; j<n; j++) { // For each element in the set
   if((i & (1 << j)) > 0) { // Check if it's included in this subset. (1 << j) sets the jth bit
    cout << str[j];
   }
  }
  cout << endl;
 }