All possible combinations of an array

Question

I have an string array

{"ted", "williams", "golden", "voice", "radio"}

and I want all possible combinations of these keywords in the following form:

{"ted",
 "williams",
 "golden", 
 "voice", 
 "radio",
 "ted williams", 
 "ted golden", 
 "ted voice", 
 "ted radio", 
 "williams golden",
 "williams voice", 
 "williams radio", 
 "golden voice", 
 "golden radio", 
 "voice radio",
 "ted williams golden", 
 "ted williams voice", 
 "ted williams radio", 
 .... }

I've been going for hours with no effective result (side effect of high-level programming ??).

I know the solution should be obvious but I'm stuck, honestly ! Solutions in Java/C# are accepted.

EDIT:

1. It's not a homework
2. "ted williams" and "williams ted" are considered the same, so I want "ted williams" only

EDIT 2: after reviewing the link in the answer, it turns out that Guava users can have the powerset method in com.google.common.collect.Sets

Answer 1

EDIT: As FearUs pointed out, a better solution is to use Guava's Sets.powerset(Set set).

EDIT 2: Updated links.

---

Quick and dirty translation of this solution:

public static void main(String[] args) {

    List<List<String>> powerSet = new LinkedList<List<String>>();

    for (int i = 1; i <= args.length; i++)
        powerSet.addAll(combination(Arrays.asList(args), i));

    System.out.println(powerSet);
}

public static <T> List<List<T>> combination(List<T> values, int size) {

    if (0 == size) {
        return Collections.singletonList(Collections.<T> emptyList());
    }

    if (values.isEmpty()) {
        return Collections.emptyList();
    }

    List<List<T>> combination = new LinkedList<List<T>>();

    T actual = values.iterator().next();

    List<T> subSet = new LinkedList<T>(values);
    subSet.remove(actual);

    List<List<T>> subSetCombination = combination(subSet, size - 1);

    for (List<T> set : subSetCombination) {
        List<T> newSet = new LinkedList<T>(set);
        newSet.add(0, actual);
        combination.add(newSet);
    }

    combination.addAll(combination(subSet, size));

    return combination;
}

Test:

$ java PowerSet ted williams golden
[[ted], [williams], [golden], [ted, williams], [ted, golden], [williams, golden], [ted, williams, golden]]
$

Answer 2

I just faced this problem and wasn't really happy with the StackExchange answers posted, so here's my answer. This returns all combinations from an array of Port objects. I'll leave it to the reader to adapt to whatever class you're using (or make it generic).

This version does not use recursion.

public static Port[][] combinations ( Port[] ports ) {
    
    List<Port[]> combinationList = new ArrayList<Port[]>();
    // Start i at 1, so that we do not include the empty set in the results
    for ( long i = 1; i < Math.pow(2, ports.length); i++ ) {
        List<Port> portList = new ArrayList<Port>();
        for ( int j = 0; j < ports.length; j++ ) {
            if ( (i & (long) Math.pow(2, j)) > 0 ) {
                // Include j in set
                portList.add(ports[j]);
            }
        }
        combinationList.add(portList.toArray(new Port[0]));
    }
    return combinationList.toArray(new Port[0][0]);
}

See solution by @Aison on this page for a more optimized version.