内存寻址方法，将内存(静态-硬件)分配给与从0到n-1的值的“nCk”组合对应的值。
我需要找到一种内存寻址方法，将内存(静态-硬件)分配给与从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’总是相等的。
回答 1
Stack Overflow用户
发布于 2014-01-21 00:47:52
--我对问题的理解
因此，正如我理解您的问题一样，用于检索数据的可能的“键”是在n个值中选择k值。
有：
- 从0到n-1
- 无重复值
- 只有键中的值才重要，而不是它们的顺序。
单命题
让我们以一个简单的命题作为参考点。
您可以考虑“键”中的值是必须在“n”位地址中设置为1的位：
- 从键到地址的转换似乎非常容易。
- 内存大小为2^n字(因此浪费了相当多的空间)
分而治之: n=16，k=2
让我们来看看这个特殊的例子: n=16，k=2。
对于前面的解决方案，我们使用2^16字的内存，而只有16*15/2 =120个可能的键。
在这种情况下，分而治之的战略可以是：
- 这两个值都位于可能值的第一部分(0到7)。
- 它们都位于可能值的第二部分(8到15)。
- 其中一个值在第一部分，另一个值在第二部分。
使用此初步测试，您可以在本例中使用：
- 一个8位地址存储器的情况1(参考。最初的简单解决方案，但使用n=8而不是16)
- 为案例2 (idem)提供一个8位地址存储器
- 一种特殊情况，第一部分有8种可能的选择，第二部分有另外8种，因此附加的8*8=64字存储器(6位地址，前3位对应于第一部分的0到7之间的值，而另外3位对应于从8到15的值的位置的0到7之间的值)。
2^8 + 2^8 + 64 = 576字
分而治之: n=16，k=3
让我们尝试对k:k=3的较大值进行同样的处理。
键的最小值在0到13之间(因为如果这个值是13，那么其他两个值将是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个值，因此它相当于决定哪些值是没有选择的，因此我们在内存优化方面的情况类似于"n=6，k=2“。
希望这能有所帮助。
https://stackoverflow.com/questions/21241921
复制相似问题
腾讯云开发者
