首页 > 代码库 > 不定长数组取值交叉遍历组合生成算法

不定长数组取值交叉遍历组合生成算法

2024-07-30 01:31:16   221人阅读

代码如下：
#include <stdio.h>


int factor[3][4] =
{
    {0, 1, 2, 3}, 
    {0, 1}, 
    {0, 1, 2}, 
};


int lengths[3] = {4, 2, 3}; 


void recurisionAccess(int factor[3][4], int lengths[3], int colum, int row)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int len = 0;
    int len_num = 0;
    int totalLength = 1;
    
    for (i=0; i<colum; i++)
    {   
        totalLength *= lengths[i];
    }   
   
    for (i=0; i<totalLength; i++)
    {   
        k = i;
        len_num = 0;
        for (j=0; j<colum; j++)
        {
            len = lengths[len_num];
            /* first do % with len, then do / with len, next time do it again on 


new len */
            printf("%d ", factor[j][k%len]);
            k = k / len;
            len_num++;
        }
        printf("\n");
    }
}


int main()
{
    recurisionAccess(factor, lengths, 3 ,4);
    return 0;
}




循环次数从底到上为3 x 2 x 4 = 24
我们可以认为循环中 i 的值一个由3位混合进制的数，每一位使用不同的进制，进制自底向上

分别为2,3,4。每一位上的值代表着在对应的那一行的一个位置。


例如十进制的789，7实际上是百位上的余值，它在该位的意义是7x10x10,8的意义为8x10，9为


最低位余值，没有10可以乘了。
所以[2][1][3]，混合进制，进制分别为【3，2，4】。[2][1][3]在每一位上的值，实际上是本


位的余值，是低位们相乘的值。


即，
15 => [1][1][3]，即1x2x4 + 1x4  + 3 => 15
23 => [2][1][3]，即2x2x4 + 1x4  + 3 => 23


对于23，即[2][1][3]，我们理解为最低位是4进制，次低位为2进制，最高位为3进制。

所以按照如下方式取得每一位的值



1.第1行是最低位，4进制，先同4 取余获得余值3，即位置值为：3
再除以4越过该位：[2][1][3] 变为 [2][1]。


2.第2行是次低位，2进制，先同2 取余获得余值1，即位置值为：1
再除以2越过该位：[2][1] 变为 [2]。


3.第3行是最高位，3进制，先同3 取余获得余值2，即位置值为：2
再除以3越过该位：[2] 变为 空。


这样3个位置值都获取到了。即我们不把23单纯当做23，而是将它看做[2][1][3]，从而通过以
上的方式获取到各个行中的位置也就是3，1，2。


总结：
将位置3x2x4的24种组合理解为[0-2] [0-1] [0-3]的三个方框的组合方式，把每个方框看成一
位的话，那个方框就使用了一个固定的进制，所以0 -- 23 之间的值都可以用三个位表示，
每一位就代表在每个方框中的取值，也即在二维数组中的位置。
而0 -- 23这24个值恰好覆盖了三个方框所有种组合，所以用这种多进制组合位的方式可以实现多组值得交叉遍历。

不定长数组取值交叉遍历组合生成算法


联系
我们