How to display the combination of some values in array?

Question

For example, I have an array ["Sam", "Mary", "John"].
I would like to display the combination of choose 2 out of 3.
The results should be:

[Sam, Mary]
[Sam, John]
[Mary, John]

I have researched a lot but still dun know how to do it.
Of course, this example only contain 3 people.
In fact, the number of total people will be larger, e.g. 15

Here is what I found:
Algorithm to return all combinations of k elements from n

What is a good way to implement choose notation in Java?

Some of them is only display the value of nCr, but not giving out the combination.

In your example, order matters but you say you want the combination (implying order doesn't). Which is it? — Daniel, Aug 07 '13 at 14:09
Do you always want to select pairs, or is the size of the combinations ever going to be at all variable? — Michelle, Aug 07 '13 at 14:09
The first link in your question ([Algorithm to return all combinations of k elements from n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n)) contains plenty of answers to your question. — Carsten, Aug 07 '13 at 14:10

score 2 · Answer 1 · answered Aug 07 '13 at 14:31

    public static int width;

    public static void main(String [] args){

        String[] array = {"one", "two", "three", "four", "five"};

        width = 3;

        List<String> list = new ArrayList<String>();

        for (int i = 0; i < array.length; i++){
            method(array, list, i, 1, "[" + array[i]);
        }

        System.out.println(list);
    }


    public static void method(String[] array, List<String> list, int i, int depth, String string){

        if (depth == width){
            list.add(string + "]");
            return;
        }

        for (int j = i+1; j < array.length; j++){
            method(array, list, j, depth+1, string + ", " + array[j]);
        }
    }

Can you give some explanation of recursion because I not really understand. — jjLin, Aug 07 '13 at 15:07
Check out this question: http://stackoverflow.com/questions/9199984/basic-java-recursion-method — Brinnis, Aug 07 '13 at 15:27

boxed__l · Answer 2 · 2013-08-07T15:11:44.120

1

Simple recursive function to print out combination(nCr) of a given string array (named array):

String[] array = {"Sam", "Mary", "John"};

public void function(int counter, String comb_Str, int r) {
        if (r == 0) {
            System.out.println(comb_Str);            
        } else {
            for (; counter < array.length; ++counter) {
                function(counter + 1, comb_Str + "  " + array[counter], r - 1);
            }
        }
    }

called using function(0, "", #r value#)

r value should be <= n value (array length)

edited Aug 07 '13 at 15:11

answered Aug 07 '13 at 14:29

boxed__l

1,334
1
10
24

I try to run but nothing printed. When it run the first for loop, it exits. – jjLin Aug 07 '13 at 15:02
use `function(0,"",2);` for your above example @jjLin – boxed__l Aug 07 '13 at 15:06
first parameter is not `n` but a counter/ used to keep track of the string in array – boxed__l Aug 07 '13 at 15:08

Briguy37 · Answer 3 · 2013-08-07T14:47:33.350

Here's some pseudocode to get you started with a recursive solution. Lists will be easier to work with than string arrays, as you can change their size easily. Also, once you get your combos, you can iterate over them to display them however you want. However, though it's a good problem to think about, the number of combos will get out of hand pretty quickly, so displaying them all to a user will become a bad idea if you are working with more than a handful of results...

/**
 * @param list The list to create all combos for
 * @param comboSize The size of the combo lists to build (e.g. 2 for 2 items combos)
 * @param startingIndex The starting index to consider (used mainly for recursion).  Set to 0 to consider all items.
 */
getAllCombos(list, comboSize, startingIndex){
    allCombos;

    itemsToConsider = list.length - startingIndex;
    if(itemsToConsider >= comboSize){
        allCombos = getAllCombos(list, comboSize, startingIndex + 1);

        entry = list[startingIndex];
        if(comboSize == 1){
            singleList;
            singleList.add(entry);
            allCombos.add(singleList);
        } else {
            subListCombos = getAllCombos(list, comboSize - 1, i+1);
            for(int i = 0; i < subListCombos.length; i++){
                subListCombo = subListCombos[i];
                subListCombo.add(entry);
                allCombos.add(subListCombo);
            }
        }
    }

    return allCombos;
}

score 0 · Answer 4 · answered Aug 07 '13 at 14:50

This probably isn't perfect, but it should get you on the right track. Create a function to get combinations for each element. Then you just have to loop through each element and call your function on each of them.

int num = 2; //Number of elements per combination

for(int i=0; i <= (array.length - num); i++) {
    String comb = "[" + array[i];
    comb += getComb(i,num);
    comb += "]";
    println(comb);
}

String getComb(int i, int num) {
    int counter = 1;
    String s = "";

    while(counter < num) {
        s += ", " + array[i+counter];
        counter++;
    }

    return s;
}

How to display the combination of some values in array?

4 Answers4