从多个集合中获取特定元素组合的排名的算法

Question

我有一堆集合，比如 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 } 等。请问有人有算法吗？

Answer 1

将您的集合视为一个数字，其每个数字的可能值就是关联集合的大小。为了看到这一点，假设每个集合 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])

Answer 2

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

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 行。然后，我们必须跳过最右边位置的一轮才能到达 Y，依此类推。

编辑：该公式可以简化为

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

（并且它当然应该以这种方式计算）。顺便说一句，请注意整数溢出......