0

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

每个列表有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 个值。我发现这篇文章感觉它非常接近我正在寻找的内容（它提供了一种有效的方法来获得具有固定值组合的集合中的词典第 m 位），但我无法弥合两者之间的差距两个想法（尽管我在文章中重新创建了结果，我相信我对它们有所了解）。

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

PS如果这个问题已经以其他形式重述并且我没有找到它，我深表歉意。我已经进行了大量搜索，但似乎没有什么能完全反映这一点。欢迎链接，头脑风暴，一般想法！

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

4

1 回答 1

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个成员的值（其中 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]。

于 2012-11-16T22:00:46.203 回答