algorithm - 在不生成整个集合的情况下迭代元素的每个组合

Question

我需要遍历所有可能的元素组合(重复)，最多 n 个元素。

我已经找到了解决这个问题的多种方法。但是所有这些都是递归地生成每个可能组合的集合，然后对其进行迭代。虽然这可行，但对于大型元素集合和组合大小，它会导致大量内存使用，因此我正在寻找一种解决方案，让我可以根据前一个组合计算下一个组合，知道元素数量和组合的最大大小。

这甚至可能吗？是否有任何特定的算法可以在这里工作？

Answer 1

生成组合，以便对每个组合进行排序。 (这是假设元素本身可以很容易地按顺序排列。只要是总顺序，精确的顺序关系并不重要。)

从最小元素的 n 次重复组成的组合开始。从任何给定组合生成下一个组合:

1. 向后扫描，直到找到一个不是最大元素的元素。如果找不到，那你就完了。

2. 用该元素的下一个较大元素替换该元素和所有后续元素。

如果您想要所有长度的组合，最大为 n，请为每个长度最大为 n 运行该算法。或者从一个包含空槽的向量开始，并在理解空槽之后的“下一个较大元素”是最小元素的情况下使用上述算法。

示例:长度为 3 的 3 个值:

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3