多套施工

Question

我有四套：

A={a,b,c}, B={d,e}, C={c,d}, D={a,b,c,e}

我要搜索给我的集合序列：a b c d

例子：序列A A A C可以给我a b c d因为"a"是A的一个元素，"b"是A的一个元素，"c"是 A 的一个元素，"d" 是 C 的一个元素。

对于 : D A C B 等也是如此

我想要一个算法来枚举所有可能的序列，或者一个数学方法来找到这些序列。

Answer 1

你真的应该想出一些你自己的代码，然后就它的问题提出具体问题。但这很有趣，所以我会分享一些想法。

你想要a b c d.

a can come from A, D
b can come from A, D
c can come from A, C, D
d can come from B, C

所以问题简化为找到所有 2*2*3*2=24 种方法来组合这些选项。

一种方法是带回溯的递归。从左到右构建它，当你有一个完整的集合时输出。就像 8 皇后问题，但由于一切都是独立的，所以要简单得多。

另一种方法是对整数进行计数并将它们映射到混合基系统中。第一个数字以 2 为基数，然后是 2、3、2。所以 0 变成 AAAB，1 变成 AAAC，2 变成 AACB，等等。23 是 DDDC，24 需要五位数，所以你到此为止。