2 ^ N Combining with integers (Kernel), how to generate them?

Question

(Merry Christmas by the way ^^)

Here is my problem (in JAVA), but it is definitely an algorithmic problem, and I don’t know how to solve it: / So, with an example (for information only, all my calculations are in binary format, so 1 + 1 = 0)

let the variable names:

N : the number of elements in kernel. M : the length of an element in the kernel. int[][] Kernel: .... i : 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 (length = M) i+1 : 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 (length = M) .... N : .... 

My goal with these things is to generate all possible combinations (so there are 2 ^ N elements) and I want to generate them. By generation, I mean exactly this:

  Result[0] = 0 0 0 0 0 0 0 0 0 0 0 0 0 Result[1] = Kernel[0] Result[2] = Kernel[1] .... Result[i] = Kernel[i-1] Result[N-1] = Kernel[N-2] Result[N] = Kernel[0] + Kernel[1] Result[N+1] = Kernel[0] + Kernel[2] Result[N+i] = Kernel[0] + Kernel[i] Result[2N-1] = Kernel[0] + Kernel[N-1] .... Result[I] = Kernel[0] + Kernel[1] + Kernel[2] Result[I+1] = Kernel[0] + Kernel[1] + Kernel[i] Result[I+J] = Kernel[0] + Kernel[1] + Kernel[N-1] .... Result[2^N+1] = Kernel[0] + Kernel[1] + ... + Kernel[i] + ... + Kernel[N-1] 

Here is what I already managed to do, but it is not completed, and I do not know how to generalize the calculation to work with any N ...

 public static int[][] combinaisons(int[][] kernel) { /* if the kernel is empty, there is no possible combinaison */ if(kernel.length == 0) return kernel; /* We allocate the good number of space... */ int[][] result = new int[(int) (Math.pow(2, noyau.length)+1)][]; /* Every element in result has the same length as in kernel elements. */ for(int i = 0; i < resultat.length; i++) { result[i] = new int[kernel[0].length]; } /* The first element of result has to be only 0 0 0 0 0 0 0 */ for(int j = 0; j < kernel[0].length; j++) { result[0][j] = 0; } /* We rewrite the element of kernel because they are a part of the solution... */ for(int i = 0; i < kernel.length; i++) { for(int j = 0; j < kernel[i].length; j++) { result[i+1][j] = kernel[i][j]; } } /* I managed to do it when it the sum of only 2 elements, but it has to be with 3, 4 ... N-1 :/ */ for(int i = 0; i < kernel.length; i++) { for(int j = 0; j < kernel[i].length; j++) { for(int k = i+1; k < kernel.length; k++) { result[k*kernel.length+i][j] = (kernel[i][j]+kernel[k][j])%2; } } } return result; } 

---

Edit:

Example, let give this:

  N = 2 M = 4 Kernel: 0 1 1 0 1 0 0 1 In result I want: 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 (the sum of the 2 elements in Kernel) 

So this is a simple example (in particular, values, if you want more, just ask :))

Even if the array at the end seems VERY HUGE :) that is exactly what I want to create (without worrying about memory, this will probably be good)

Answer 1

I use boolean[][] instead of int[][] . 0 means false , 1 means true .

 public static boolean[][] combinations(boolean kernel[][]) { int n = kernel.length; int m = kernel[0].length; int p = 1 << n; boolean[][] temp = new boolean[p][m]; for (int i = 0; i < p; i++) for (int j = 0; j < n; j++) if (((1 << j) & i) != 0) for (int k = 0; k < m; k++) temp[i][k] ^= kernel[j][k]; return temp; }