algorithm - 需要一种算法来 "evenly"迭代一组值的所有可能组合

Question

抱歉标题太可怕了，我真的很难为我正在寻找的东西找到合适的词。我认为我想做的其实很简单，但我仍然无法真正专注于创建算法。我敢打赌，如果我不缺乏算法术语的基本知识，我可以很容易地在网上找到解决方案。

假设我想遍历五个整数数组的所有组合，其中每个整数都是 0 到 9 之间的数字。当然，我可以从 0 递增到 99999。 [0, 0, 0, 0, 1], [0, 0, 0, 0, 2], ... [9, 9, 9, 9, 9]。

但是，我需要“均匀地”(不知道怎么调用它)增加各个元素。理想情况下，算法生成的数组序列应如下所示:

[0,0,0,0,0] [1,0,0,0,0] [0,1,0,0,0] [0,0,1,0,0] 
[0,0,0,1,0] [0,0,0,0,1] [1,1,0,0,0] [1,0,1,0,0] 
[1,0,0,1,0] [1,0,0,0,1] [1,1,0,1,0] [1,1,0,0,1]
[1,1,1,0,0] [1,1,1,1,0] [1,1,1,0,1] [1,1,1,1,1] 
[2,0,0,0,0] [2,1,0,0,0] [2,0,1,0,0] [2,0,0,1,0] 
[2,0,0,0,1] [2,1,1,0,0] [2,1,0,1,0] ..... 

我可能在上面的顺序中犯了一些错误，但也许你能猜到我想要接近的是什么。除非确定了 0 和 1 的所有可能组合，否则不要引入大于 1 的数字，除非已确定 0、1 和 2 的所有可能组合，否则不要引入大于 2 的数字，等等..

我真的很感激有人给我指出正确的方向!非常感谢

Answer 1

您已经说过，您可以通过枚举所有 n^k 个可能的序列来获得您正在寻找的组合，除了您不要按所需的顺序获取它们。

如果您使用里程表式枚举器，您可以按正确的顺序生成序列。首先，所有数字都必须为 0 或 1。当里程表回绕时(在 1111... 之后)，您将数字集递增到 [0, 1, 2]。将序列重置为 2000... 并继续迭代，但只发出其中至少有一个 2 的序列，因为您已经生成了所有 0 和 1 的序列。重复直到包装后超出最大阈值。

可以通过跟踪最高数字的计数来过滤掉其中没有当前最高数字的重复项。

这是一个使用硬枚举限制的 C 实现:

enum {
    SIZE = 3,
    TOP = 4
};

typedef struct Generator Generator;

struct Generator {
    unsigned top;           // current threshold
    unsigned val[SIZE];     // sequence array
    unsigned tops;          // count of "top" values
};



/*
 *      "raw" generator backend which produces all sequences
 *      and keeps track of how many top numbers there are
 */
int gen_next_raw(Generator *gen)
{
    int i = 0;
    
    do {
        if (gen->val[i] == gen->top) gen->tops--;
        gen->val[i]++;
        if (gen->val[i] == gen->top) gen->tops++;
        
        if (gen->val[i] <= gen->top) return 1;

        gen->val[i++] = 0;
    } while (i < SIZE);
   
    return 0;
}

/*
 *      actual generator, which filters out duplicates
 *      and increases the threshold if needed
 */
int gen_next(Generator *gen)
{
    while (gen_next_raw(gen)) {
        if (gen->tops) return 1;
    }
        
    gen->top++;
    
    if (gen->top > TOP) return 0;
    
    memset(gen->val, 0, sizeof(gen->val));
    gen->val[0] = gen->top;
    gen->tops = 1;    
    
    return 1;
}

gen_next_raw 函数是里程表的基本实现，增加了对当前最高数字的计数。 gen_next 函数使用它作为后端。它过滤掉重复项并根据需要增加阈值。 (所有这些都可以更有效地完成。)

生成序列:

Generator gen = {0};

while (gen_next(&gen)) {
    if (is_good(gen.val)) {
        puts("Bingo!");
        break;
    }        
}