How to create all possible arrangement of 12 red and 12 blue ball in java

Question

I have 12 blue and 12 red balls and now want to create all possible arrangements of this. In java I want to create series of all possible arrangements like this

[1,1,2,1,2,1,2,2,1,1,2,1,2,1,1,2,1,2,1,1,2,2,2,2]

1 is for red and 2 is for blue. I want to create all such possible combination in form of arrarys.

Any ideas to do it efficiently?

check out http://stackoverflow.com/questions/5113707/every-possible-permutation-of-a-string-or-combination-including-repeated-charact — KarlM, Dec 23 '15 at 03:16
Two things: this is a permutation of a set of 24 elements, and the size of that set is 24! (24 *factorial*, or ~620 sextillion combinations). Depending on how you generate it, you may not have enough memory to pull that off. — Makoto, Dec 23 '15 at 03:19

score 1 · Answer 1 · answered Dec 23 '15 at 03:40

Try this.

static void perm(int red, int blue, int max, int i, int[] result) {
    if (i >= max) {
        System.out.println(Arrays.toString(result));
        return;
    }
    if (red > 0) {
        result[i] = 1;
        perm(red - 1, blue, max, i + 1, result);
    }
    if (blue > 0) {
        result[i] = 2;
        perm(red, blue - 1, max, i + 1, result);
    }
}

static void perm(int red, int blue) {
    perm(red, blue, red + blue, 0, new int[red + blue]);
}

public static void main(String[] args) {
    perm(12, 12);
}

your code is very efficient, but it lacks some explanation. – guillaume girod-vitouchkina Dec 23 '15 at 10:57 — guillaume girod-vitouchkina, Dec 23 '15 at 10:57

score 0 · Answer 2 · answered Dec 23 '15 at 10:41

It is a choose of 12 elements between 24: COMBINATIONS.

then you have exactly 2704156 results.

1 just use combinations:

You can use any lib to generate combinations. like mine: http://sourceforge.net/projects/gastor/files/org/gastor/open/algorithm/Combinatorics.java/download

You take a vector of 24 positions (0 to 23), and just pick 12

this gives you all possible chooses:

Vector<Integer> pos=new Vector<Integer>();
for (int i=0;i<24;i++)
    pos.add(i);

// Combinations 5 between 24
Vector<Vector<Integer>> combine=Combinatorics.combinaisons(pos, 5);

System.out.println("COMBINE "+combine.size());

for (int k=0;k<combine.size()<10;k++)
    System.out.println(combine.get(k)); 
    // You have the positions => convert to your format

Unfortunately, for 12 between 24, it is too much for the memory. Exercise: rewrite the algo with arrays, not vectors, and dont keep them.

2 other possibility, more practical in this case: get all subsets, and keep the good ones.

All subset gives you 2^24 possibilities=16777216 (not too many), and just keep the ones with 12 elements.

It will take more time with big numbers.

Iterate through every number from 0 to 16777215, and decompose in bits: you will have every subset like that:

{8, 18, 19, 20, 21} : one subset of 5 elements

You keep the subsets of 12 elements, and you have your positions.

public static BitSet bitsSet(long num)
{
BitSet bitSet = new BitSet();
for (int i = 0; i < 64; i++)
    if (((num >>> i) & 1) != 0)
            bitSet.set(i);
return bitSet;
}   

int total=24;
int how_many=12;

int count=0;

int max=(int) Math.pow(2.0,total);
for (int i=0;i<max;i++)
    {
    BitSet bitset=bitsSet(i);
    if (bitset.cardinality()==how_many)
        {
        // get the bits => and convert to your format
        System.out.println(bitset);
        count++;
        }
    }

System.out.println("COUNT:"+count);

How to create all possible arrangement of 12 red and 12 blue ball in java

2 Answers2