P^N 与整数（内核）的组合，如何生成它们？

Question

我的问题和我几个月前问的几乎一样：

2^N Combinaisons with Integers (Kernel), how to generate them?

基本上，我想在内核中进行 2^N 次组合，但我概括了我的版本，现在它更复杂了：

我不再需要 2 个元素的所有可能组合的总和（模 2），但我现在需要 P 元素的所有可能组合的总和（模 P）: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}

我的目标（就像之前的 2^N 组合一样）是生成所有可能性（所有 P^N 组合），他们将像：

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]

我现在使用@pbabcdefp 给出的版本它仅适用于 2 个元素的总和（模 2），我不知道如何使其适用于 P 元素的总和（模 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;
}

和之前的版本一样，不介意内存开销，也不介意这种数组生成的复杂性，这只是一个理论案例。

提前感谢任何对如何概括这种组合有想法的人。

此致，

以防万一：示例

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)

我们曾经在内核中有 2 个元素，我们知道新内核中有 P^2 所以 3^2 = 9 个元素，我们只是生成它们（除了计算错误 :D 提前抱歉，但计算是这样写的 :D)

Answer 1

从数学上讲，这对应于使用 n 元组 mod p 的所有可能系数集来查找核向量的所有线性组合。它相当于 p^n x n 系数矩阵和 n x m 核矩阵之间的矩阵乘法 mod p。

p^n x n 矩阵只是所有基数 p 直到 p^n-1.

的逐行列表

恐怕我不太了解Java，所以这是 C 语言的答案，它可能足够接近，您可以从中复制和翻译。

#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");
  }

}

我得到以下输出：

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

P^N 与整数（内核）的组合，如何生成它们？

P^N Combinaisons with Integers (Kernel), how to generate them?

java

math

complexity-theory

mathematical-optimization

algebra