需要一个算法来“均匀”遍历一组值的所有可能组合

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的数字，依此类推。

我真的很感激有人指引我正确的方向！非常感谢。

- Max Luchterhand

---

为什么使用这种特定的模式？在[0,0,0,0,0][0,0,0,0,1][0,0,0,1,0][0,0,0,1,1]...中，我觉得更自然的模式是什么？ - dawg

你是否必须按照那个顺序_生成_组合，或者可以将所有组合收集到列表中，然后按照特定的顺序进行排序？后者可能会更简单，但并非总是可行。 - tobias_k

@tobias_k 我不必生成它们，但我想学习如何生成它们。 - Max Luchterhand

我不清楚在[2,1,1,1,1]之后，序列会是什么样子，在[0,2,0,0,0]之后，以及在[2,2,2,2,1]之后。你能否给出一个仅有3个位置的数组的完整系列，并且数字最高只到2（而不是9）？这将给出27种可能性。它们的顺序是什么？ - trincot

具体例子。你的第一个尝试可能会是最常见的字母“e”。其次是“t”和“a”。但是“et”的出现频率约为“te”的10倍，“ea”在英语中很常见，而“ae”极为罕见。这让你有很好的猜测，最有可能是“a”和“t”中的前5位之一。你对那三个字母的猜测填充了大约30%的信息。此时，你已经获得了关于剩余信息的大量信息。 - btilly

Answer 1

您可以将其分解为两个子问题：

• 获取给定位数的数字0、1、2...的所有带替换组合
• 获取这些组合的所有（唯一）排列

您期望的排序仍然不同于它们通常生成的顺序（例如，在(0,0,2)之前是(0,1,1)，在(1,0,0)之前是(0,0,1)），但您只需要单独收集所有组合和所有排列并对它们进行排序，就至少需要比生成、收集和排序所有这些组合所需的内存少得多。

以下是Python示例，使用itertools库中这些函数的实现；key=lambda c: c[::-1]按顺序排序列表，但反转每个元素的顺序以获得您想要的顺序：

from itertools import combinations_with_replacement, permutations

places = 3
max_digit = 3

all_combs = list(combinations_with_replacement(range(0, max_digit+1), r=places))
for comb in sorted(all_combs, key=lambda c: c[::-1]):
    all_perms = set(permutations(comb))
    for perm in sorted(all_perms, key=lambda c: c[::-1]):
        print(perm)

以下是部分输出结果（总共64个元素）

(0, 0, 0)
(1, 0, 0)
(0, 1, 0)
...
(0, 1, 1)
(1, 1, 1)
(2, 0, 0)
(0, 2, 0)
...
(0, 1, 2)
(2, 1, 1)
...
(2, 2, 2)
(3, 0, 0)
(0, 3, 0)
...
(2, 3, 3)
(3, 3, 3)

---

有27个值最大为27的位置，即使使用组合排序也会生成太多的结果，因此这部分应该改用自定义算法。

• 跟踪每个数字出现的次数； 初始时全部为零
• 找到具有非零计数的最小数字，将该数字之后的数字计数增加，然后将剩余较小计数重新分配回最小数字（即零）

在Python中：

def generate_combinations(places, max_digit):
    # initially [places, 0, 0, ..., 0]
    counts = [places] + [0] * max_digit
    yield [i for i, c in enumerate(counts) for _ in range(c)]
    while True:
        # find lowest digit with a smaller digit with non-zero count
        k = next(i for i, c in enumerate(counts) if c > 0) + 1
        if k == max_digit + 1:
            break
        # add one more to that digit, and reset all below to start
        counts[k] += 1
        counts[0] = places - sum(counts[k:])
        for i in range(1, k):
            counts[i] = 0
        yield [i for i, c in enumerate(counts) for _ in range(c)]

对于第二部分，我们仍然可以使用标准的 permutations 生成器，尽管对于 27! 来说，在一个集合中收集太多排列是不可行的，但如果你期望结果在前几百个组合中出现，你可以跟踪已经看到的排列并跳过它们，并希望在该集合变得太大之前找到结果...

from itertools import permutations

for comb in generate_combinations(places=3, max_digit=3):
    for p in set(permutations(comb)):
        print(p)
    print()

- tobias_k

---

谢谢你的回答。请纠正我，但是在这种方法中，似乎我们首先生成所有可能的元素组合。我的元素数组长度为27，每个元素可以是27个不同的字符之一。我相信这会给我留下一个包含973469712824060个组合的列表，随后我将确定所有排列组合。这似乎不可行。特别是因为在我的情况下，我正在寻找某个组合/排列，最有可能在前100-200个中找到。 - Max Luchterhand

好的，你不是生成所有组合，而是“仅仅”生成数字组合。但是对于有27个位置且每个位置有27种可能元素的情况来说，还是太多了。但是分成子问题应该会有所帮助。更容易调整现有的带替换组合算法以产生所需的顺序。 - tobias_k

Answer 2

您已经说过，您可以通过枚举所有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函数是odometer的基本实现，除了保持当前顶位数字的计数外。gen_next函数使用它作为后端。它会过滤掉重复项，并在需要时增加阈值。（所有这些可能都可以更有效地完成。）

使用以下命令生成序列：

Generator gen = {0};

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

- M Oehm

---

不错，我一开始也有类似的想法。但是这仍然会在(1,0,0)之前生成(0,1,1)（我没有尝试过这个确切的代码，但我自己在Python中也有同样的问题），但这可能没关系。 - tobias_k

谢谢。我忽略了评论中所有冗长的解释，并使用“除非已确定所有可能的0和1的组合，否则不要引入大于1的数字”作为规范。可能还有改进的余地。 - M Oehm

谢谢，这看起来非常有前途。我会仔细研究并在明天尝试一下。 - Max Luchterhand