1

因此，我希望将集合的幂集映射到其每个元素的唯一编号（索引），然后将此编号与映射或列表中的非唯一值相关联。我希望这样做是为了不必显式存储所有子集，而只需存储与它们关联的唯一编号。如果存在一个从子集的元素中唯一地产生一个数字的线性时间（最好，但我想如果有必要我可以负担得起更高次的多项式）算法，那将是很棒的。从直觉上看，我认为这样的算法可能存在，对子集的元素使用一些求和或卷积函数。

在形式上，我有一个U = {1,2,3,...,n}需要所有子集的宇宙。有2^n这样的子集。我有一个从子集到数字的函数f映射，即。是一个非唯一的数字。Xyf(X)=yy

现在，我需要在我的程序中能够从一个子集X值移动到另一个子集Y值，其中Y = X - {k}一些k ϵ X. 因此，如果有一种算法可以Y从其元素中计算唯一标识符，那么我只需要删除k并使用的（剩余）元素X即可找到它，而不是通过存储的子集列表进行搜索，这需要搜索，比较 AND 存储每个子集的内存成本。

那么，有人知道这样的算法是否存在吗？

4

2 回答 2

3

根据定义，任何唯一标识符都需要与 set 中的元素一样多的位U。因此，如果其中的元素U是固定且有序的，您可以轻松地从任何子集的元素计算一个位向量Y（仅设置与集合中的元素对应的位Y）并将其转换为一个数字。当然，根据 的最大大小U，您可能需要一些无限精度的数据类型。

于 2013-07-04T13:13:10.143 回答
0

电源组可能是解决您的问题的关键。请参阅此处，可能需要进行一些修改，以支持 2^n

于 2013-07-04T13:14:48.003 回答