My question is almost the same that the one I asked few months ago :
2^N Combinaisons with Integers (Kernel), how to generate them?
Basically, I wanted to have the 2^N combinaisons inside a Kernel, but I generalized my version, and now it's even more complicated :
I don't want the sum (modulo 2) of every possible combinaisons of 2 elements anymore, but I need now the sum (modulo P) of every possible combinaisons of P elements :O.
N : the number of elements in kernel.
M : the length of an element in the kernel.
P : the dimension of my result.
int[][] Kernel:
....
i : 0 1 2 1 0 1 0 1 0 1 1 1 2 1 1 2 0 1 2 1 0 2 1 1 2 (length = M)
i+1 : 1 2 1 0 1 2 0 2 0 1 0 1 2 0 2 1 0 1 0 1 1 0 2 0 1 (length = M)
....
N : ....
with P = 3 (so value inside Kernel elements equals to {0,1,2}
My Goal (like the previous one with 2^N combinaisons) is to generate all the possibilities (all the P^N combinaisons) who will be like :
1 * Kernel[0]
2 * Kernel[0]
....
P * kernel[0]
......
1 * Kernel[0] + 1 * Kernel[1]
1 * Kernel[0] + 2 * Kernel[1]
......
1 * kernel[0] + (P-1) * Kernel[1]
......
1 * kernel[0] + 1 * Kernel[1] ....(P elements) + 1 * Kernel[P]
I for now, used the version given by @pbabcdefp by it works only for sum of 2 elements (modulo 2) and I don't know how to make it works for the sum of P elements (modulo P)
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;
}
As again with the previous version, don't mind the memory cost and don't mind the complexity of such array's generation, it's just for a theory case.
Thanks in advance for anyone who has an idea on how to generalize such combinaison.
Best regards,
Just in case: an Example
int[][] Kernel :
[0] : 0 1 2 0 2 1 2 0
[1] : 1 2 2 0 1 2 2 0
so we have : N equals to 2 ; M equals to 8 and P equals to 3 (values are included inside {0,1,2}
The result should be :
0 0 0 0 0 0 0 0 (the null element is always inside the result)
0 1 2 0 2 1 2 0 (1x [0] % 3)
1 2 2 0 1 2 2 0 (1x [1] % 3)
0 2 1 0 1 2 1 0 (2x [0] % 3)
2 1 1 0 2 1 1 0 (2x [1] % 3)
0 0 0 0 0 0 0 0 (3x [0] % 3)
0 0 0 0 0 0 0 0 (3x [1] % 3)
1 0 1 0 0 0 1 0 (1x [0] + 1x [1] % 3)
1 1 0 0 2 1 0 0 (2x [0] + 1x [1] % 3)
2 2 0 0 1 2 0 0 (1x [0] + 2x [1] % 3)
We used to have 2 elements inside the kernel, we know have P^2 so 3^2 = 9 elements in the new kernel, and we just generate them (except so calcul mistake :D sorry in advance but the calcul is written :D)
Mathematically, this corresponds to finding all linear combinations of the kernel vectors using all possible sets of coefficients that are n-tuples mod p. It amounts to a matrix multiplication mod p between a p^n x n coefficient matrix and a n x m kernel matrix.
The p^n x n matrix is just a row-wise list of all base-p numbers up to p^n-1.
I'm afraid I don't know Java that well, so here is the answer in C, which is probably close enough for you to copy and translate from.
#include <stdio.h>
#include <math.h>
int main() {
int p = 3; // base
int n = 2, m = 8;
int kernel[2][8] = {{0, 1, 2, 0, 2, 1, 2, 0},
{1, 2, 2, 0, 1, 2, 2, 0}};
int numRows = pow(p,n);
int coeffs[numRows][n];
int result[numRows][m];
//convert the row numbers from base-10 to base-p
int num, row, q, div, remainder;
for(row=0; row<numRows; row++) {
num = row;
for(q=n-1; q>=0; q--) {
div = (int)pow(p,q);
remainder = num % div;
coeffs[row][q] = (num-remainder)/div;
num = remainder;
}
}
// now do the matrix multiplication
int i,j,k;
for(i=0; i<numRows ; i++) {
for(j=0; j<m ; j++) {
result[i][j] = 0;
for(k=0; k<n; k++) {
result[i][j] += coeffs[i][k]*kernel[k][j];
}
result[i][j] %= p; // take result mod p
printf("%d ",result[i][j]);
}
printf("\n");
}
}
I get the following output:
0 0 0 0 0 0 0 0
0 1 2 0 2 1 2 0
0 2 1 0 1 2 1 0
1 2 2 0 1 2 2 0
1 0 1 0 0 0 1 0
1 1 0 0 2 1 0 0
2 1 1 0 2 1 1 0
2 2 0 0 1 2 0 0
2 0 2 0 0 0 2 0