2

我一直在尝试解决这个问题一段时间，但一直未能找到一个好的解决方案。开始：

给定多个集合：

set1: A, T
set2: C
set3: A, C, G
set4: T
set5: G

我想从集合列表中生成所有可能的序列。在这个例子中，序列的长度是 5，但它可以是大约 20 左右的任何长度。对于位置 1，可能的候选者分别是“A”和“T”，对于位置 2，唯一的选项是“C”，所以在。

上面例子的答案是：

ACATG, ACCTG, ACGTG, TCATG, TCCTG, TCGTG

我在 ruby​​ 中执行此操作，并且我将不同的集合作为主数组中的数组：

[[A, T], [C], [A, C, G], [T], [G]]

起初我认为递归解决方案是最好的，但我无法弄清楚如何正确设置它。

我的第二个想法是创建另一个相同大小的数组，每个数组都有一个索引。因此 00000 将对应于“ACATG”上方的第一个序列，而 10200 将对应于“TCGTG”。从 00000 开始，我会将最后一个索引增加 1，并将其与相关集合的长度取模（set1 为 2，set2 为 1），如果计数器环绕，我会将其归零并将前一个索引增加一个。

但是我对这个解决方案的思考越多，对于这个非常小的问题来说似乎太复杂了。必须有一个我缺少的更直接的解决方案。谁能帮帮我？

/缺口

4

1 回答 1

4

Ruby 1.8.7 中的 Array 类有一个 Array#product 方法，它返回相关数组的笛卡尔积。

irb(main):001:0> ['A', 'T'].product(['C'], ['A', 'C', 'G'], ['T'], ['G'])
=> [["A", "C", "A", "T", "G"], ["A", "C", "C", "T", "G"], ["A", "C", "G", "T", "G"],     ["T", "C", "A", "T", "G"], ["T", "C", "C", "T", "G"], ["T", "C", "G", "T", "G"]]
于 2009-11-24T16:19:21.043 回答