Нужна подсказка по комбинаторике!

avpikalev · Сообщение **avpikalev** » 07 апр 2009, 11:32

Люди! Кто-нибудь сталкивался c подобной задачей?
Есть наборы взаимозаменяемых вариантов, например:
1. A,AB,CDE
2. X,YZ
3. G,F,FH

Из них генерируются сочетания (берется по 1 варианту из каждого набора):
AXG
AXF
AXFH
AYZG
AYZF
..
CDEYZFH

B условии дан список получившихся строк, надо восстановить
исходные наборы вариантов
1. A,AB,CDE
2. X,YZ
3. G,F,FH

Нет у кого ссылок на материалы? Или есть алгоритм, решающий данную задачу? Подскажите пожалуйста..

Георгий

Если я возьму такой вариант только c первого набора

AABCDE

это допускается?

avpikalev · Сообщение **avpikalev** » 07 апр 2009, 12:01

Нет, берутся последовательно один вариант из 1-го, один вариант из 2-го, один вариант из 3 набора

jarik · Сообщение **jarik** » 07 апр 2009, 12:12

Количество элементов первой последовательности умножить на количество элементов второй последовательности и умножить на количество элементов третьей последовательности... $n(A)\cdot n(B)\cdot n(C)$

Таланов

avpikalev писал(а):Source of the post
B условии дан список получившихся строк, надо восстановить
исходные наборы вариантов

После этих слов должен следовать список, по которому восстанавливаются исходные наборы вариантов. Где он? Или решение нужно найти в общем виде?

avpikalev · Сообщение **avpikalev** » 07 апр 2009, 12:33

B общем виде... Недавно на контесте по программированию была такая идея... Вот сейчас бьемся. Давался как раз такой пример

Есть набор сгенерированных строк
AXG
AXF
AXFH
AYZG
AYZF
..
CDEYZFH
(всевозможные варианты)

Нужна идея, как найти закономерность и восстановить наборы, из которых эти строки генерились

yourdomain.com