获取条件松散的一组元素的第 N 个组合

Question

鉴于：

大小为 M 的符号列表
组合尺寸L
符号可以在组合中出现任意次数
必须考虑符号任意组合的所有排列

示例：对于符号列表 (a, b, c) 和 L=4，所有组合 (a, a, a, a)、(a, b, a, c)、(a, c, b, b) 等都是有效的。由于找不到更好的术语，我称之为 "loose combinations".

组合的特定顺序并不重要。给定组合索引 N，该算法应该 return 满足条件的可能组合集中的唯一组合。我的猜测是，最自然的顺序是，如果我们将组合视为基数 M 和长度 L 的数字，那么正常的数字顺序将适用，但这并不是严格必须遵循的。

找到第N个组合的算法是什么？

我自己也不确定如何找到答案，并且一直在寻找其他地方是否有针对这组特定条件的答案，但没有找到。我发现的所有问题都对 (a, a, b, b) 等重复元素的组合和重新排列顺序的组合不感兴趣，例如 (a, a, b, c) 和 (a, b, c, a) 或 (a, c, a, b) 被视为相同的组合.

Answer 1

如您所知，您本质上对枚举以 M 为基数的长度不超过 L 的数字感兴趣。因此，解决方案可能如下所示：

定义一个双射 {0, …, M-1} -> 符号，即枚举你的符号。
对于任何非负整数 N < M^L，确定其基数 M 表示。
- 通过重复取模 M 并四舍五入除以 M 即可轻松完成。
- 不失一般性，根据需要添加前导零，长度为 M。
使用你的双射将这个数字列表 0 到 M-1 转换为松散的符号组合。

所以，让我们详细介绍一下这部分：

Easily done by repeated modulo M and rounded down division by M.

伪代码：

int a[L];
for int i from 0 to L-1 do
    a[i] = N % M; // Should go from 0 to M-1
    N = N / M; // Rounded down, of course
done

获取条件松散的一组元素的第 N 个组合

Get Nth combination of a set of elements with loose conditions

math

permutation

combinatorics