algorithm - 如何找到从 k 个子集中选择一个的组合数

Question

考虑我们已经设置了 S:

S = {1,2,3,4,5,6}

和 S 的 3 个(比如 k 个)子集:

S_1 = {1,2,3}

S_2 = {2,3,4,5}

S_3 = {1,3,6}

从每个子集中选择一个元素的案例总数是多少？

不能从不同的子集中选取相同的元素，并且不考虑顺序。

例如，

S_1 = {2}，S_2 = {3}，S_3 = {6}

和

S_1' = {3}，S_2' = {2}，S_3' = {6}

视为相同。和

S_1' = {3}，S_2' = {3}，S_3' = {1}

无效，因为 S_1' 和 S_2' 选择相同的元素。

我怎样才能制定这个？

Answer 1

这个问题类似于计算perfect matchings的数量。在 bipartite graph .

要以这种方式对其进行建模，请构建一个二部图，其中 A = { 1, ..., k }, B 是原始集合 S，并且当 y 是该集合的成员时，存在从 x ∈ A 到 y ∈ B 的边S_x。

完美匹配对应于将 A 的每个元素与 B 的不同元素匹配的边子集；对于每个集合 S_x，这个匹配选择一个不同的元素 y ∈ S_x。也就是说，多个不同的匹配可能匹配来自 B 的相同 k 个元素，这意味着由于您的问题中未考虑顺序而导致过度计数(即，出于您的目的，从 A 映射到那些 k 个元素的边并不重要)。尽管如此，问题非常相似，很可能每个都可以减少到另一个。

根据 this answer on math.SE没有已知的有效算法来计算完美匹配，因此对于这个类似的问题，可能也没有已知的有效算法。这表明你不太可能比 backtracking search 做得更好。某种。