c - 排列的矩阵和子矩阵

Question

我需要一个包含 N 个元素的所有排列的矩阵。事实上，它的维度将是 N x N!该矩阵的一个特殊属性是每个子矩阵的维度为 K x K! (K < N) 必须是 K 个元素的所有排列的矩阵。显然有很多有效的解决方案，但我对最简单(但有效)的普通 C 风格算法感兴趣，它只生成一个这种矩阵(没有 STL 和其他高级库)。

为了澄清问题，这里是生成矩阵的形式。第二列以一个“2”开头，第三列以两个“3”开头，第i列以(i-1)开头!元素“我”。对排列顺序没有其他要求，只需要简化算法即可。

1 2 3 4 5 ...
2 1 3 4 5 ...
* * * 4 5 ...
* * * 4 5 ...
* * * 4 5 ...
* * * 4 5 ...
* * * * 5 ...
...

Answer 1

我希望我理解了问题 ;-) - 解决方案是基于对 KxK 的观察!锚定在 a[1,1] 的子矩阵可以通过 a) 将 K+1 添加到 K!行，b) 复制前 K!重复行，即 K 次，进入行 K+1..(K+1)!，同时替换每组 K!将值 1..K 行 K+1 并将 K 存储到列 K+1。

#include <stdio.h>
#define N 6
#define NF (1*2*3*4*5*6)

int p[NF][N];

int main( int argc, char* args[] ){
  int n, i, k, iCol, iRow;
  int row = 0;

  for( n = 0; n < N; n++ ){
    if( n == 0 ){
      p[row][n] = n+1;
      row++;
    } else {
      // add new value n+1 to all existing rows
      for( i = 0; i < row; i++ ){
        p[i][n] = n+1;
      }
      // for all numbers 1..n
      int nextRow = row;
      for( k = 1; k <= n; k++ ){
        // pass through all rows so far
        for( iRow = 0; iRow < row; iRow++ ){
          // copy row
          for( iCol = 0; iCol < n; iCol++ ){ 
            int h = p[iRow][iCol];
            p[nextRow][iCol] = h == k ? n+1 : h;
          }
          p[nextRow][n] = k;
          nextRow++;
        }
      }
      row = nextRow;
    }
  }
  for( iRow = 0; iRow < NF; iRow++ ){
    for( iCol = 0; iCol < N; iCol++ ){
      printf( "%3d", p[iRow][iCol] );
    }
    printf( "\n" );
  }
}