0

我有一堆集合，比如 S1、S2、S3，......每个集合都有不同的元素。说 S1 = { A, B, C}, S2 = { X, Y }, S3 = { P, Q, R, T }

存在这些集合的组合 K = { S1, S2, S3 }。例如，这种组合的一个实例是 { A, X, P }。显然有 3 x 2 x 4 = 24 种可能的组合。我需要的是特定组合的“排名”，使用从左到右的简单有序枚举计算，反之亦然。

显然，我可以通过简单地枚举所有组合并将其与请求的组合进行比较，同时保留一个计数器来轻松计算，但我需要一个有效的算法，因为我的集合每个可以包含多达 20000 个元素，并且在某些情况下组合集合的数量大于 10。

顺便说一句，我知道组合的线程计算等级吗？这里是堆栈溢出。但是，不幸的是，它不适用于这里，因为我的组合是由针对不同位置的不同大小的集合组成的

我会很感激 C# 中的实现，但其他语言或伪代码也会非常有帮助。

任何建议，请

凯末尔

更新：@spinning_plane & @aasmund。谢谢你的回答。他们都为我提供了计算排名的相同公式。

但是，我也需要反过来。即获得给定等级的组合（从零开始）。例如，给定等级 0，结果将是 {A,X,P} ，对于 3 {A, X, R } 等。请有算法的人吗？

4

2 回答 2

4

将您的集合视为一个数字，其每个数字的可能值是关联集合的大小。为了看到这一点，假设每个集合 S1...S3 的大小相同，为简单起见假设为 2。要计算集合的等级，您只需将 K 解释为二进制数并将其转换为以 10 为底的等效值。rank(x) 只是集合中元素的基于 0 的索引。

rank(A)*2^0 + rank(X)*2^1 + rank(P)*2^2

现在将其推广到集合可以不同大小的情况，我们可以写出一个计算表达式

rank(A) + rank(X)*len(S1) + rank(P)*len(S2)*len(S1) ... etc.

在伪代码中

input = {'a','b','x'}
output = 0;
cumulative = 1;
for i in range(len(K)):
     output += cumulative*rank(input[i],K[i]) # this returns the index of input[i] in set K[i]
     cumulative*=len(K[i])
于 2011-05-27T16:31:32.797 回答
3

这是完整的“排名序列”的样子吗？

0: {A, X, P}
1: {A, X, Q}
2: {A, X, R}
3: {A, X, S}
4: {A, Y, P}
5: {A, Y, Q}
...

如果是这样，让集合从右到左编号为S1 , S2 , ..., Sn，并让所选元素在它们自己的集合中的等级（例如 A=0, B=1, C=2）为r1，r2， ...，rn。那么公式应该是

rn * |S(n-1)| * ... * |S2| * |S1| + ... + r3 * |S2| * |S1| + r2 * |S1| + r1

为什么？假设我们选择{C, Y, Q}. 它们在各自集合中的从零开始的等级分别为 2、1 和 2。因为最左边的排名是 2，这意味着为了到达排名序列的那一部分，我们需要让最右边和中间的位置执行两个完整的“轮”，总共（在这种情况下）r2 * |S2| * |S1| = 2 * 2 * 4 = 16行。然后，我们必须跳过最右边位置的 1 轮才能到达 Y，依此类推。

编辑：公式可以简化为

(((...) * |S3| + r3) * |S2| + r2) * |S1| + r1

（当然应该以这种方式计算）。顺便提一下整数溢出...

于 2011-05-27T16:30:03.160 回答