How can I do this in java?

Question

I must combine values in a set in this way:

Input:

{A,B,C,D}

Result:

{AB, ABC, AC, AD, ACD, ABD, ABCD, BC, BD, BCD, CD}

How can I do this?

You do that using `for` loops, `while` loops, or recursive functions. — Andreas, Oct 03 '15 at 11:51
Welcome to Stack Overflow! Please take the [tour], have a look around, and read through the [help], in particular [*How do I ask a good question?*](/help/how-to-ask) — T.J. Crowder, Oct 03 '15 at 11:51
pretend you have a 4 digit binary. find all numbers that have at least two 1s. So your result would be equivalent to {1100,1110,1010,1001,1111,0110,0101,0111,0011) — ergonaut, Oct 03 '15 at 11:51
Possible duplicate of [What algorithm can calculate the power set of a given set?](http://stackoverflow.com/questions/2779094/what-algorithm-can-calculate-the-power-set-of-a-given-set) — Tempestas Ludi, Oct 03 '15 at 11:54

score 0 · Answer 1 · 2015-10-04T08:08:50.237

There are several solutions depending upon the size of the input:
If the input-array is <= 64 and the input doesn't need to be sorted, we can represent each combination as a long, where each bit is 1, if the corresponding element is in the produced output:

void generateCombination(int[] inp){
    long upper_bound = (1 << inp.length);

    for(long rep = 0 ; rep < upper_bound ; rep++){
        for(int i = 0 ; i < inp.length ; i++)
            if(rep & (1 << i) != 0)
                System.out.print(inp[i]);

        System.out.print(",");
    }
}

If the output has to be sorted, we can easily solve this problem using a recursive solution:

void generateCombinations(int[] inp , int[] combination , int at_i , int at_c){
    for(int i = at_i + 1 ; i < inp.length ; ++i)
    {
        combination[at_c] = inp[i];
        System.out.println(Arrays.toString(combination));

        generateCombinations(inp , combination , i , at_c + 1);
    }

    combination[at_c] = 0;
}

//this call will produce all combinations sorted ascending
generateCombinations(inpt , new int[inp.length] , -1 , 0);

thanks, but now I want to compare the elements of combation. So if I've AB and ABC, I want to compare A with B and AB with C — user3195053, Oct 04 '15 at 07:39
@user3195053 this is ensured by the recursive solution. what exactly do you mean by that comparison? lexicographical order? — , Oct 04 '15 at 08:09
no isn't importand lexicographical order. I want to compare all the combinations possibile. For example, if I've a input like that Set:{ A : {1,2,3} , B : {1,2}, C : {1} } Result must be: A,B : {1,2} ; A,C : {1}; A,B,C: {1} — user3195053, Oct 04 '15 at 09:23

How can I do this in java?

1 Answers1