c - 二维数组的每条可能路径?(交叉产品)
问题描述
假设我有这个数组
int diml = 3;
int dims = 3;
int time [diml][dims] ={
(10, 3, 5),
( 4, 7, 2),
( 2, 8, 1)
};
我怎样才能得到每个组合,如:
(10, 3, 5)
(10, 3, 2)
(10, 3, 1)
(10, 7, 5)
(10, 7, 2)
(10, 7, 1)
...
(2, 8, 5)
(2, 8, 2)
(2, 8, 1)
*这是否可能不将所有组合保存在一个新数组中,而只是一个可以在每个循环中存储当前组合的一维本地数组?
*我更喜欢循环而不是递归。在每个周期结束时,我需要模式(如 10、3、2),以便我可以详细说明。
*二维数组的维度是 MxN(3x3 只是一个例子)。
*接受二叉树的解决方案(但我也想保存索引)。
我应该在 C 中执行此操作。我在 StackOverflow 中找到了类似的解决方案,但它们按列工作,并将数据保存在 2D 数组中,但这不是我需要的。
提前致谢!(:
解决方案
对于此示例代码,构建了第一个代码,以便更容易理解示例 2。示例 1 仅针对 3x3 矩阵构建。示例 2 的构建使其可以容纳最多 8 列的矩阵。我没有使用 malloc 或返回一个数组。它将为您打印出所有可能的组合。它不处理返回数据,但将其合并到代码中并不难。
对于计算所有可能组合的方法,我将以 3x3 矩阵为例。
在 3x3 矩阵中,有 3 行和 3 列。我将每一列视为一组我可以选择的数字,并将行视为我可以从中选择的数字。所以在那个例子中,我可以选择 012 作为我的第一组、第二组和第三组号码。
所以为了得到所有可能的组合,我有 3 个数组,[0] [1] [2]。它们都从 0 开始。我首先保存 0 0 0 的可能组合。然后将数组 2 增加 1。然后我会得到 0 0 1。然后我保存该组合。我将继续这样做,并将 [2] 数组之一 == 2。我将其变为 0 并将 1 添加到其左侧的数组中。所以它变成 0 1 0。当我到达一个循环,其中我的数组的值为 0 2 2,之后的循环,我将得到 1 0 0。我将继续这样做,直到所有值都变为零,然后我我完成了。
对于数据的存储方式,我将它们不断地存储在一个数组中。正确读回该值。例如,在 2x5 矩阵中。每个组合将有 5 个数字。因此,第一个组合是前五个索引,下一个组合是那个之后的下五个数字。
要计算在计算组合之前需要多少数组长度,您可以将计算基于行和列。把它想象成彩票。如果有 3 列,就像您可以选择 3 个数字一样。每列有 3 行,这意味着每次您选择一个数字时,都有 3 个可能的数字可供选择。对于您来说,中奖的机会是 1:3 x 1:3 x 1:3 或 1:27,因为如果选择这样的 3 个数字 (123 123 123) 并以正确的顺序匹配它们,则有 27 种可能性。因此,对于 3x3 矩阵,它是 3x3x3, 4x4 = 4x4x4x4, 1x3 = 1, 3x1 = 3, 2x5 = 2x2x2x2x2 = 32。
因此,可能组合的数量是“行数”的“列数”次方。
大小是可能组合的数量乘以每个组合的数量。其中将是“可能性乘以列数 = 所需的数组大小。
示例 1:
#include <stdio.h>
void printMatrixCombo(int row, int col, int matrix[row][col]);
int main(){
const int m1 = 3;
const int m2 = 3;
int matrix[m1][m2] = {
{10, 3, 5},
{4, 7, 2},
{2, 8, 1}
};
printMatrixCombo(m1, m2, matrix);
return 0;
}
// Only use this for a 3x3
void printMatrixCombo(int row, int col, int matrix[row][col]){
int oi = 0;
int output[81] = {0};
for (int group1 = 0; group1 < 3; group1++){
for (int group2 = 0; group2 < 3; group2++ ){
for (int group3 = 0; group3 < 3; group3++ ){
output[oi++] = matrix[group1][0];
output[oi++] = matrix[group2][1];
output[oi++] = matrix[group3][2];
}
}
}
printf("There were %d combination in the matrix of %d x %d\n", oi / col, row, col );
for ( int i = 0; i < oi ; ){
printf("(");
for ( int j = 0; j < col; j++ ){
printf("%d", output[i+j]);
if ( j != col - 1 ) printf(", ");
}
printf(")\n");
i = i + col;
}
}
示例 2:
#include <stdio.h>
void printMatrixCombo(int row, int col, int matrix[row][col]);
int main(){
const int row = 4;
const int col = 4;
/*// 3x3
int matrix[row][col] = {
{10, 3, 5},
{4, 7, 2},
{2, 8, 1}
};//*/
// 4 x 4
int matrix[row][col] = {
{10, 3, 5, 7},
{4, 7, 2, 3},
{2, 8, 1, 9},
{9, 4, 8, 11}
};//*/
/*// 5 x 5
int matrix[row][col] = {
{10, 3, 5, 7, 25},
{4, 7, 2, 87, 42},
{2, 8, 1, 85, 39},
{9, 4, 8, 94, 57},
{10, 3, 5, 7, 93},
};//*/
/*// 2 x 2
int matrix[row][col] = {
{10, 3},
{4, 7},
};//*/
/*// 1 x 1
int matrix[row][col] = {
{10},
};//*/
/* // 3 x 1
int matrix[row][col] = {
{10},
{4},
{1}
}; //*/
/*// 1 x 3
int matrix[row][col] = {
{10, 4, 1},
};// */
printMatrixCombo(row, col, matrix);
return 0;
}
void printMatrixCombo(int row, int col, int matrix[row][col]){
int oi = 0;
int allZ = 0;
// This is the maximum for a 5x5
// Change to fit usage case
int output[15625] = {0};
int colCount[8] = {0};
int lastCol = col - 1;
int lastRow = row - 1;
while (1){
for ( int i = 0; i < col; i++ )
output[oi++] = matrix[colCount[i]][i];
if ( colCount[lastCol] == lastRow ){
colCount[lastCol] = 0;
for (int i = lastCol - 1; i > -1; i--){
if ( colCount[i] == lastRow ){
colCount[i] = 0;
} else {
colCount[i]++;
break;
}
}
} else {
colCount[lastCol]++;
}
allZ = 1;
for ( int i = 0; i < col; i++ ){
if ( colCount[i] != 0 ){
allZ = 0;
break;
}
}
if (allZ == 1) break;
}
printf("There were %d combination in the matrix of %d x %d\n", oi / col, row, col );
printf("Array's length(indexes) is %d\n", oi );
for ( int i = 0; i < oi ; ){
printf("(");
for ( int j = 0; j < col; j++ ){
printf("%d", output[i+j]);
if ( j != col - 1 ) printf(", ");
}
printf(")\n");
i = i + col;
}
}
推荐阅读
- android - 如何在 imageview Click 事件上打开 Facebook 应用程序?
- django - 我需要外键查询集的帮助
- batch-file - 批处理文件:根据输入的字符数删除文件名前缀
- google-bigquery - google bigQuery 实时与 ga 报告不匹配
- mongodb - Mongo - Exec错误:OperationFailed:排序操作使用的RAM超过最大33554432字节
- sql - 需要从sql中的同一字段中查找数据
- php - PHP从jQuery发送空时未接收POST数组
- swift - 不应该关闭(nsviewcontroller 方法来关闭视图控制器)是类方法吗?
- audiokit - 使用音量低于 0.00001 的 AKMixer 没有输出
- excel - PS脚本从excel中获取数据然后删除共享文件夹的权限