Let’s say I’ve a string “12345” I should obtain all subsequence combinations of this string such as:

- –> 1 2 3 4 5
- –> 12 13 14 15 23 24 25 34 35 45
- –> 123 124 125 234 235 345
- –> 1234 1235 1245 1345 2345
- –> 12345

Please note that I grouped them in different number of chars but not changed their order. I need a method/function does that.

## Answer

You want a powerset. Here are all the questions on StackOverflow that mention powersets or power sets.

Here is a basic implementation in python:

def powerset(s): n = len(s) masks = [1<<j for j in xrange(n)] for i in xrange(2**n): yield [s[j] for j in range(n) if (masks[j] & i)] if __name__ == '__main__': for elem in powerset([1,2,3,4,5]): print elem

And here is its output:

[] [1] [2] [1, 2] [3] [1, 3] [2, 3] [1, 2, 3] [4] [1, 4] [2, 4] [1, 2, 4] [3, 4] [1, 3, 4] [2, 3, 4] [1, 2, 3, 4] [5] [1, 5] [2, 5] [1, 2, 5] [3, 5] [1, 3, 5] [2, 3, 5] [1, 2, 3, 5] [4, 5] [1, 4, 5] [2, 4, 5] [1, 2, 4, 5] [3, 4, 5] [1, 3, 4, 5] [2, 3, 4, 5] [1, 2, 3, 4, 5]

Notice that its first result is the empty set. Change the iteration from this `for i in xrange(2**n):`

to this `for i in xrange(1, 2**n):`

if you want to skip an empty set.

Here is the code adapted to produce string output:

def powerset(s): n = len(s) masks = [1<<j for j in xrange(n)] for i in xrange(2**n): yield "".join([str(s[j]) for j in range(n) if (masks[j] & i)])

Edit 2009-10-24

Okay, I see you are partial to an implementation in Java. I don’t know Java, so I’ll meet you halfway and give you code in C#:

static public IEnumerable<IList<T>> powerset<T>(IList<T> s) { int n = s.Count; int[] masks = new int[n]; for (int i = 0; i < n; i++) masks[i] = (1 << i); for (int i = 0; i < (1 << n); i++) { List<T> newList = new List<T>(n); for (int j = 0; j < n; j++) if ((masks[j] & i) != 0) newList.Add(s[j]); yield return newList; } }