所以，我有这样的情况，我希望将集合的幂集映射到它的每个元素的唯一数字(索引)，然后将这个数字关联到映射或列表中的非唯一值。我想要这样做是为了不必显式存储所有子集，而只存储与它们关联的唯一编号。如果存在线性时间(最好，但我想如果有必要我可以负担得起更高阶的多项式)算法可以从子集的元素中唯一地产生一个数字，那将是很棒的。凭直觉，我认为可以存在这样的算法，对子集的元素使用一些求和或卷积函数。
在形式上，我有一个宇宙 U = {1,2,3,...,n} 我需要它的所有子集。有 2^n 个这样的子集。我有一个函数 f 从子集 X 映射到数字 y，即 f(X)=y . y 是一个非唯一的数字。
现在，我需要在我的程序中能够从一个子集 X 值移动到另一个子集 Y 值，其中 Y = X - {k } 对于一些 k ϵ X。因此，如果有一种算法可以从其元素中计算出 Y 的唯一标识符，那么我只需要删除 k 并使用 的(剩余)元素>X 来找到它，而不是搜索存储的子集列表，这需要搜索、比较和存储每个子集的内存成本。
那么，有人知道这样的算法是否存在吗？
最佳答案
根据定义，任何唯一标识符需要的位数与集合 U 中的元素一样多。因此，如果 U 中的元素是固定且有序的，您可以轻松地从任何子集 Y 的元素中计算出位向量(仅对应于集合 Y 已设置)并将其转换为数字。当然，根据 U 的最大大小，您可能需要一些无限精度的数据类型。
关于algorithm - 将(子)集编码为唯一数字的快速算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17470942/