英文:
Information theory problem, sets of numbers
问题
我只有32位的空间来存储一组物品的组合。约束条件是一个组合可以有0到7个物品。有64种唯一的物品。一个物品不能在一个组合中多次出现。
如何将这些物品的集合映射到32位整数？
英文:
I only have 32 bits of space to store a combination of items. The constraints are that a combination can have anywhere from 0 to 7 items. There are 64 unique items. An item cannot appear multiple times in a combination.
How do I map these sets of items to 32-bit integers?
答案1
得分: 0
我要假设你所说的"combination"指的是一个集合。集合的顺序并不重要。如果顺序很重要，那么可能性就无法适应32位。
对于包含0到7个元素的集合，共有64个可能的元素，我们可以计算0到7个元素的二项式和(binomial(64, i)，其中i在0到7之间)，这总共有704,494,193种可能性。这甚至可以用30位表示（2^30 = 1,073,741,824）。
只需定义一个方案，为每种可能性分配唯一的编号并存储该编号。例如，为零元素分配0，为一个元素分配1到64，为两个元素分配65到2080，依此类推。
英文:
I have to assume that by a "combination" you mean a set. The ordering of a set does not matter. If the ordering matters, then the possibilities cannot fit in 32 bits.
For set of 0 to 7 elements, where there are 64 possible elements, we have that there are the sum of binomial(64,i) for i in 0..7 possibilities, which is 704,494,193. That would even fit in 30 bits (2<sup>30</sup> = 1,073,741,824).
Simply define a scheme that numbers each possibility uniquely and store that number. E.g. assign 0 for zero elements, 1..64 for one element, 65..2080 for two elements, and so on.
答案2
得分: 0
nth_combination 源自 itertools recipes（本页底部），它将从 32 位数字转换为特定组合，但是 itertools recipes 页面上未包含逆函数。下面概述的 combination_index 函数接受组合并返回该组合的索引。
这两个函数可以作为基础用于计算幂集的索引。这解决了原始问题，允许 r 的范围从 0 到 7。索引需要按前面组合的总组合数进行偏移。对于 r = 7，索引偏移将添加每个先前组合，即 math.comb(64, 0) + math.comb(64, 1) + math.comb(64, 2) + math.comb(64, 3) + math.comb(64, 4) + math.comb(64, 5) + math.comb(64, 6)。
import math
import itertools
# 这是 nth_combination 函数的逆函数
# 即 combination_index("abcd", nth_combination("abcd", 2, 3)) 返回 3
def combination_index(iterable, combination):
# 组合必须按与可迭代对象相同的顺序排序
# r 必须小于或等于 n
pool = tuple(iterable)
n = len(pool)
r = len(combination)
result = 0
index = 0
for i, item in enumerate(pool):
if (item != combination[index]):
result += math.comb(n - i - 1, r - index - 1)
else:
index += 1
if (index >= len(combination)):
break
return result
英文:
nth_combination comes from the itertools recipes (at the bottom of this page). It converts from the 32 bit number to a specific combination however, the inverse function is not included on the itertools recipes page. combination_index outlined below takes in the combination and returns the index of that combination.
These two functions can be used as a base to calculate an index into the power set. Which solves the original question, allowing r to range from 0 to 7. The index needs to be shifted by the total combinations of the previous combinations. The index shifting for r = 7 would add each of the previous combinations aka math.comb(64, 0) + math.comb(64, 1) + math.comb(64, 2) + math.comb(64, 3) + math.comb(64, 4) + math.comb(64, 5) + math.comb(64, 6).
import math
import itertools
# this is the inverse of the nth_combination function
# aka. combination_index("abcd", nth_combination("abcd", 2, 3)) returns 3
def combination_index(iterable, combination):
# combination must be sorted in the same order as the iterable
# r must be less than or equal to n
pool = tuple(iterable)
n = len(pool)
r = len(combination)
result = 0
index = 0
for i, item in enumerate(pool):
if (item != combination[index]):
result += math.comb(n - i - 1, r - index - 1)
else:
index += 1
if (index >= len(combination)):
break
return result
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论