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.

Answer 3

Here's a hint:

All-Subsets(X) = {union for all y in X: All-Subsets(X-y)} union {X}

Answer 4

import java.util.ArrayList;
import java.util.List;
public class AllPossibleCombinations {

public static void main(String[] args) {
    String[] a={"ted", "williams", "golden"};           
    List<List<String>> list = new AllPossibleElementCombinations().getAllCombinations(Arrays.asList(a));
    for (List<String> arr:list) {
        for(String s:arr){
            System.out.print(s);
        }
        System.out.println();
    }
}

public List<List<String>> getAllCombinations(List<String> elements) {
    List<List<String>> combinationList = new ArrayList<List<String>>();
    for ( long i = 1; i < Math.pow(2, elements.size()); i++ ) {
        List<String> list = new ArrayList<String>();
        for ( int j = 0; j < elements.size(); j++ ) {
            if ( (i & (long) Math.pow(2, j)) > 0 ) {
                list.add(elements.get(j));
            }
        }
        combinationList.add(list);
    }
    return combinationList;
}

}

output:

ted

williams

tedwilliams

golden

tedgolden

williamsgolden

tedwilliamsgolden

Answer 5

My optimized solution is based on the solution provided by Matthew McPeak. This version avoids unnecessary array copies.

public static <T> T[][] combinations(T[] a) {

    int len = a.length;
    if (len > 31)
        throw new IllegalArgumentException();

    int numCombinations = (1 << len) - 1;

    @SuppressWarnings("unchecked")
    T[][] combinations = (T[][]) java.lang.reflect.Array.newInstance(a.getClass(), numCombinations);

    // Start i at 1, so that we do not include the empty set in the results
    for (int i = 1; i <= numCombinations; i++) {

        @SuppressWarnings("unchecked")
        T[] combination = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
                Integer.bitCount(i));

        for (int j = 0, ofs = 0; j < len; j++)
            if ((i & (1 << j)) > 0)
                combination[ofs++] = a[j];

        combinations[i - 1] = combination;
    }

    return combinations;
}

Answer 6

package rnd;

import java.util.ArrayList;

public class Rnd {
    public static void main(String args[]) {
        String a[] = {"ted", "williams", "golden", "voice", "radio"};
        ArrayList<String> result =new ArrayList<>();
        for(int i =0 ;i< a.length; i++){
            String s = "";
            for(int j =i ; j < a.length; j++){
                s += a[j] + " " ;
                result.add(s);
            }
        }
    }
}

Answer 7

I know this question is old, but i didn't find an answer that fullfill my needs. So using the idea of power sets, and ordered permutations of the guava library, im able to obtain an array of all the combinations of elements inside my original array.

What i wanted was this:

If i have an array with three strings

ArrayList<String> tagsArray = new ArrayList<>(Array.asList("foo","bar","cas"));

I want to have all the posible combinations of the elements inside an array:

{"foo","bar","cas","foobar","foocas","barfoo","barcas","casfoo","casbar","foobarcas","casbarfoo","barcasfoo" . . . . . }

So for getting to this result i implemented the next code, using the google's guava lib:

  import static com.google.common.collect.Collections2.orderedPermutations;
  import static java.util.Arrays.asList;

  public void createTags(){

    Set<String> tags =  new HashSet<>();
    tags.addAll(tagsArray);
    Set<Set<String>> tagsSets = Sets.powerSet(tags);

    for (Set<String> sets : tagsSets) {
        List<String> myList = new ArrayList<>();
        myList.addAll(sets);
        if (!myList.isEmpty()) {
            for (List<String> perm : orderedPermutations(myList)) {
                System.out.println(perm);
                String myTag = Joiner.on("").join(perm);
                tagsForQuery.add(myTag);
            }
        }
    }

    for (String hashtag : tagsForQuery) {
        System.out.println(hashtag);
    }
}

I hope this help somebody, this wasn't for a homework, but for a android app.