algorithm - 内存寻址方法为对应于 'nCk' 值组合的值分配内存(静态硬件)从 0 到 n-1

Question

我需要找到一种内存寻址方法来为对应于从 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' 总是偶数。

Answer 1

我对问题的理解

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

与:

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

简单命题

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

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

• 从 key 到地址的转换似乎很容易
• 内存大小为 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)
• 用于情况 2 的一个 8 位地址存储器(同上)
• 一种特殊情况，第一部分有 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

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

希望这对您有所帮助。