algorithm - 编码具有重复值的排列

Question

我正在尝试在三个位置生成 A、B、C、D、E 的所有组合:

A,A,A
A,A,B
C,A,E
C,B,A
C,B,B
etc...

我已经了解了阶乘数系统和组合数系统，但我仍然无法找到正确的实现方式。通常在过去我使用递归来解决这个问题，但在这种情况下我不想生成整个列表来找到一个值，所以我需要一种编码。

理想情况下，我有一个用于组合的整数编码，因此我可以简单地调用一个带有迭代整数的函数来生成正确的排列。

还有这叫做什么，我如何才能更多地了解方法的变化？我见过的一些类似解决方案仅生成非重复组合(ABC、ABD)，其他解决方案不重用值。

根据我过去的递归方法，我的猜测是 permutation(0) 会导致 aaa 而 permutation(100) 会导致adw.

Answer 1

您寻找的特定组合似乎只是“每个位置上的 A、B、C、D、E 中的任何一个”。在这种情况下，它们非常类似于“五元”(基数 5)positional numeral system :你有三个数字，每个数字可以独立地为 0 (A)、1 (B)、2 (C)、3 (D) 或 4 (E)。将它们编码为整数也是如此:只需将它们编号为 0 到 5³-1。

对于数字 k，“组合”是“(k div 5²) mod 5, (k div 5¹) mod 5, (k div 5 ⁰) mod 5，ABCDE分别编码为01234。

对于“xyz”这样的“组合”，首先将字母ABCDE映射到数字01234为x、y、z，然后编码数为x* 5² + y*5¹ + z*5⁰。