2

我需要找到一种内存寻址方法来为对应于从 0 到 n-1 的值的“nCk”组合的值分配内存（静态硬件）。

假设“n”为 6，“k”为 4，我需要存储与组合对应的值（8 位或 16 位）：

(1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,4,5) (1,2,4,6) (1,2,5,6) (1,3,4,5) (1,3,4,6) (1,3,5,6) (1,4,5,6) (2,3,4,5) (2,3,4,6) (2,3,5,6) (2,4,5,6) (3,4,5,6)

一旦我有了“k”（这里是 4 个）数字，我应该能够直接访问与“k”元组对应的元素。

k 元组的任何较低索引都将小于较高索引，并且没有一个索引是相等的。

是否可以生成寻址方案来存储和检索此类数据而无需搜索？这需要在生成地址时以最少的计算量和可能的最小内存量来完成。（我认为无论采用何种方法都会浪费一些内存。）

我想到了针对不同索引使用不同常量的线性哈希，但这会导致大量内存丢失或计算常量的高计算复杂度。

关于这个问题的任何建议都会有很大帮助。

例子：

（组合->内存中对应的值）

([(1,2,3,4)->14], [(1,2,3,5)->3], [(1,2,3,6)->-4], [(1,2,4,5)->7], [(1,2,4,6)->22], [(1,2,5,6)->-11], [(1,3,4,5)->5], [(1,3,4,6)->3], [(1,3,5,6)->-1], [(1,4,5,6)->9], [(2,3,4,5)->35], [(2,3,4,6)->4], [(2,3,5,6)->7], [(2,4,5,6)->-2], [(3,4,5,6)->6])

如果我对上述模块的输入是 (2,3,5,6)，我应该能够直接得到值 (7)。

编辑：'n' 和 'k' 总是偶数。

4

1 回答 1

1

我对问题的理解

因此，据我了解您的问题，用于检索数据的可能“键”是从 n 个值中选择 k 个值。

和 ：

  • n 从 0 到 n-1
  • 没有重复值
  • 只有键中存在的值很重要，而不是它们的顺序

简单的命题

让我们从一个简单的命题作为参考点开始。

您可以认为“密钥”中存在的值是必须在“n”位地址中设置为 1 的位：

  • 从键到地址的转换似乎很容易
  • 内存大小为 2^n 个字（因此浪费了相当多的空间）

分而治之：n=16，k=2

让我们来看看这个特殊情况：n=16，k=2。

在前面的解决方案中，我们使用了 2^16 个单词的内存，而只有 16*15/2 = 120 个可能的键。

对于这种情况，分而治之的策略可以是：

  1. 这两个值都在可能值的第一部分（0 到 7）
  2. 要么它们都在可能值的第二部分（8 到 15）
  3. 任何一个值都在第一部分，而另一个值在第二部分。

使用此初步测试，您可以在这种情况下使用：

  • 一个用于案例 1 的 8 位地址存储器（参见初始简单解决方案，但 n=8 而不是 16）
  • 一个 8 位地址存储器，用于案例 2（同上）
  • 一种特殊情况，第一部分有 8 个可能的选择，第二部分有 8 个其他选择，因此额外的 8*8=64 字内存（6 位地址，前 3 位对应于第一个 0 到 7 之间的值部分，其他 3 个是 0 到 7 之间的值，对应于从 8 到 15 的值的位置）。

2^8 + 2^8 + 64 = 576 个字

分而治之：n=16，k=3

让我们尝试用更大的 k 值做同样的事情：k = 3

键的最小值在 0 和 13 之间（因为如果这是 13，那么其他 2 个值将是 14 和 15）。可以很容易地找到第一个设置位。

所以我们可以将问题减少到 14 个子问题（所有子问题都是 k=2，所以我们可以使用之前研究的案例来优化每个子问题的内存使用）：

  • k=2，n=15（1 到 15 之间）
  • k=2，n=14（2 到 15 之间）
  • k=2，n=13（3 到 15 之间）
  • ...
  • k=2，n=4（12 到 15 之间）
  • k=2，n=3（13 到 15 之间）
  • k=2, n=2（在 14 到 15 之间，所以只有一种可能的情况）

我没有做数学计算，但这可能比最初的简单解决方案提供更好的内存使用率。

“对称”：n=6，k=4

这si在6个中选择了4个值，所以相当于决定了没有选择的2个值是什么，所以我们在内存优化方面类似于“n = 6，k = 2”的情况。

希望这可以帮助。

于 2014-01-21T00:47:52.777 回答