Создайте все возможные последовательности dna из нескольких заданных наборов

Question

Я пытался обмануть голову вокруг этого некоторое время, но не смог найти подходящее решение. Здесь идет:

Учитывая количество наборов:

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

Я делаю это в рубин и у меня есть различные наборы как массивы в основной массив :

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

Сначала я подумал, что рекурсивное решение было бы лучше, но я не смог понять, как правильно настроить его.

Моей второй идеей было создание другого массива того же размера с индексом для каждого набора. Таким образом, 00000 будет соответствовать первой последовательности выше «ACATG» и 10200 будет соответствовать «TCGTG». Начиная с 00000 я бы увеличил последний индекс на единицу и по модулю с длиной заданного набора (2 для set1, 1 для set2 выше), и если счетчик, обернутый вокруг, я бы обнулял его и увеличивал предыдущий по одному.

Но чем больше я думал об этом решении, он казался слишком сложным для этой очень маленькой проблемы. Должно быть более прямолинейное решение, которое мне не хватает. Может ли кто-нибудь помочь мне?

/Ник

Answer 1

Массив класса в Ruby-1.8.7 есть метод продукта Массив #, который возвращает декартово произведение массивов в вопросе.

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"]]