algorithm - 可变范围值数组的字典顺序

Question

我在最近一直试图解决的问题上取得了很大进展，但我可以就特定的排序问题使用一些建议。我试图找到一种方法来表示数字列表的字典顺序，每个数字都有自己的范围(在排序之前定义是一个问题)。

每个列表都有 7 个元素。每个元素的范围可以是 0 到 0-3 之间的任何值。也许一个具体的例子会有所帮助。

我有一个包含 7 个元素的数组 [2, 1, 0, 1, 3, 2, 3]。此列表抽象地表示了一些可能的列表，我想为其生成字典顺序。 (编辑:为了更清楚。每个数字的值代表该数字可以在可能列表集中的最大值。因此，示例中的第一个数字可以被认为是基数 4，第二个作为基数 2，第三个作为基数 1，等等)此列表的前几个元素如下:

1. [0, 0, 0, 0, 0, 0, 0]
2. [1, 0, 0, 0, 0, 0, 0]
3. [2, 0, 0, 0, 0, 0, 0]
4. [0, 1, 0, 0, 0, 0, 0]
5. [1, 1, 0, 0, 0, 0, 0]
6. [2, 1, 0, 0, 0, 0, 0]
7. [0, 0, 0, 1, 0, 0, 0]
8. [1, 0, 0, 1, 0, 0, 0]

希望模式清晰。然后我希望能够有效地调用函数 f(m) 返回此序列中的第 m 个值。我找到了 this感觉它真的很接近我正在寻找的文章(它提供了一种有效的方法来在具有固定值组合的集合中获得词典编排第 m 个位置)，但我无法弥合这两个想法之间的差距(尽管我已经在文章中重新创建了结果并且我相信我对它们有所了解)。

有人对如何创建函数 f(m) 有任何想法，该函数返回由类似于上例中提供的 7 元素列表定义的序列中的第 m 个值吗？

附言如果此问题已以其他形式重述但我没有找到，我深表歉意。我进行了大量搜索，但似乎没有什么可以完全映射到这一点上。欢迎提供链接、集思广益、一般性想法!

编辑 2:修复了我的示例中第一个元素是 3 而不是 2 的错误。

Answer 1

编辑:用更直接的转换替换了原来的答案。如果你真的想看到落后的解决方案，请检查早期的修订版。

请注意，您提供的初始数组与示例列表不匹配(数组的第一个元素应为 2)。我将在我的答案中使用更正后的数组。

给定一个输入数组[2, 1, 0, 1, 3, 2, 3]，每个位置可能元素的数量是，

[3,2,1,2,4,3,4]

给我们 3*2*1*2*4*3*4 = 576 种可能性。

要确定最左边(低位)元素列表的第 m^th 成员的值，其中 0 <= m < 576，我们需要找到 m/3 的余数，或 m mod 3。下一个元素是 (m div 3) mod 2，依此类推。那么在伪代码中:

increment all elements of A by 1

// we now have A = [3,2,1,2,4,3,4]
// m is given
// result is in R[7]
for i = 0 to 6
    R[i] = m mod A[i];
    m = m div A[i];
end

如果您将上面的示例列表调整为从 0 开始，您应该会得到相同的结果。下面是使用 A = [3,2,1,2,4,3,4] 和 m = 11 的示例计算:

11 mod 3 = 2 (11 div 3 = 3)
 3 mod 2 = 1 (3 div 2 = 1)
 1 mod 1 = 0 (1 div 1 = 1)
 1 mod 2 = 1 (1 div 2 = 0)
 0 mod 4 = 0
 0 mod 3 = 0
 0 mod 4 = 0

因此第 11 个列表元素(从零开始)是 [2,1,0,1,0,0,0]。