如果你知道任何与数值方法相关的方法，请在此处发布！
背景
我有一个包含每个集合值的数组values，每个值的索引对应于该值绑定到的集合，因此我将集合表示为整数，其中元素表示位位置，例如：一个具有其元素为一的集合表示为...001，其中1是LSB。
因此，集合仅是索引，从不存储，它是即时生成的密钥，导致数组中代表集合值的索引。
我的目标是给定一个集合，是否有任何成对不相交子集的总和大于该集合的值。例如，如果集合0111的值为3，其中两个子集的值分别为0100=2和0011=2，则更有利于进行此分割。我会为集合的所有子集执行此操作。
给定三个代理和排序是集合编号表示。
val[8] = {0,1,2,4,3,2,4,2} the values is not important, only how they are ordered
0 0 0 0 1 1 1 1 MSB bit representation of the index
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 LSB
最佳拆分111的方式是011和100,总和为7。因此要获取只包含第一个元素的集合(即001)的值,可以将val[1]赋值给它，要获取包含元素1和3(101)的集合的值,则可以将val[5]赋值给它。
当按基数进行分组时，val数组的顺序是如何排序的。
val[8] = {0,1,2,3,4,2,4,2}
0 0 0 1 0 1 1 1 MSB bit representation of the index
0 0 1 0 1 0 1 1
0 1 0 0 1 1 0 1 LSB
在这里，您需要将索引翻译为数组中的正确二进制位，所以对于只有第三个元素（100）的集合，它看起来像这样：val[translate(4)]。考虑到数组大小> 2^25个元素。
请参阅Improving random memory access when random access is needed以获得更多澄清。
然而，这会导致内存中高度随机访问的顺序，即使我按基数分组它们。当前按基数分组，并生成索引比按表示集合的数字排序要慢。
我使用常量内存中的帕斯卡三角形来生成按基数分组的集合的索引，如Determin the lexicographic distance between two integers中的答案所述。
当基数为四个代理时，集合值组成的位置
n index 1 2 4 8 3 5 6 9 10 12 7 11 13 14 15
-----------------------------------------------------
MSB 0 0 0 1 | 0 0 0 1 1 1 | 0 1 1 1 | 1
0 0 1 0 | 0 1 1 0 0 1 | 1 0 1 1 | 1
0 1 0 0 | 1 0 1 0 1 0 | 1 1 0 1 | 1
LSB 1 0 0 0 | 1 1 0 1 0 0 | 1 1 1 0 | 1
一个索引表示它在无序的基数中的索引位置。这只是为了显示每个集合的值所在的位置。
整数集合表示值数组中的索引，可以通过直接索引（我目前正在执行的操作，提供随机访问）或通过将集合转换为索引来实现。
想法
我想到了自下而上生成集合的方法，而不是将集合分成子集。例如，我会从集合 {0100,0011},{0010,0101},{0001,0110} 来生成 0111，而不是将其分割为所有成对不相交的子集。
如何以及为什么它应该工作
假设我们想要评估具有基数3的集合的所有分裂，即集合 7,11,13,14。由于分裂基数为3的集合的唯一方式是将其分裂为基数为1和2的集合，因此我们需要评估基数为1和2的所有不相交子集的总和是否大于这些集合的并集。
所需符号（可能有点缺陷）：
|C|=n,∀ a,b : a ∪ b = C , a ∩ b ={Ø}, |a|+|b| = n
因此，通过使用对每个线程进行合并的内存访问来读取值，对于所有形成基数为n的集合的子集，请检查其值是否大于形成的集合。如果是，则更新该值。
简单的例子，如果 n=2，则应读取所有基数为1的值，并执行这些集合的所有组合并相应地更新。这个例子很容易，因为所有集合互不重叠：
pseudo code for 4 threads, input card1 is pointer to array of sets |s| =1
__shared__ int value[4];
tid = threadIdx.x;
value[tid] = card1[tid]; // coalesced memory access
int thvalue = value[tid]; // holds the value for the thread, to avoid bank conflict
int rvalue[blockDim.x/2]= 0; //holds the sum
int i = blockDim.x;
int x = 0;
//reduction loop that dont generate duplicate sets
for(;i>0;i>>=1) {
if(tid < i) {
x++;
rvalue[x-1] = value[(tid+x)%blockDim.x] + thvalue;
}
}
for(i = 0; i < x; i++) {
int index = getindex(tid,i,1); //gets the index for the set it generated, 1 represent the cardinality
if(output[index] < rvalue[i])
output[index] = rvalue[i];
}
缩减循环的迭代
Thread set specific for thread first iteration second iteration
0 0001 0001 + 0010 0001 + 0100
1 0010 0010 + 0100 0010 + 1000
2 0100 0100 + 1000 none
3 1000 1000 + 0001 none
正如你所看到的，它已经获取了所有形成基数为2的集合子集的值。
问题在于，生成基数大于2的集合更加棘手，因为并非所有集合都是不相交的。例如0001和0011不相交。
请记住，我没有在任何地方存储集合，只有集合的值。
最终
考虑到这一点，如何创建一种算法，从不相交的子集中读取内存联合，并生成所有集合。没有检查子集是否不相交，它应该是完全确定性的。
赏金
该算法应该用明显的步骤描述文本或伪代码。
它应该通过示例证明它的有效性。请注意，这个算法可以达到n^32个集合，因此需要很好的可扩展性。
该算法可以分为两个或多个实例，例如一个偶数和一个奇数。
如果您认为您已经有了一个即使有很多这样的指令也可以，请尝试发表，我会非常感激任何信息。
如果以另一种方式排序，但仍然按照我所描述的方式工作，则请发布它，任何帮助都很有用
如果有任何不清楚的地方，请询问。
简洁解释
我有一个带有值的数组Z，索引i(例如Z[i])表示一个整数集合，根据Z的排序方式，值按基数分组，并按二进制词典排序排列-> 集合值所在的位置1,2,4,3,5,6,7 <- 因此我使用一个函数(我已经实现了这个函数)，将索引转换为正确的索引。例如，集合3->索引4。
通过将集合按基数分组的方式，我想确定是否任何两个不相交的集合的值大于它们形成的集合。
例如|a| = 3，|b|+|c| =3，b ∩ c ={Ø}，|b| =1因此读取类型为b和c的X数量的值，查找所有不相交子集的b和c类型(基数为3的集合)并获取它们的和。继续直到所有集合都被“生成”。
0111的值为3）。随机访问、基数等是否都属于另一个问题的一部分？（也就是说，对于这个问题，您只需要一个算法，假设位字符串的值具有足够短的时间查找（显然，您最好能解决两个问题））。 - Bernhard Barker