Найти все возможные пары между подмножествами N множеств с помощью Erlang

Question

У меня есть набор S.Он содержит N подмножеств (которые, в свою очередь, содержат некоторые подмножества различной длины):

1. [[a,b],[c,d],[*]]
2. [[c],[d],[e,f],[*]]
3. [[d,e],[f],[f,*]]
N. ...

У меня также есть список L «уникальных» элементов, которые содержатся в наборе S:

a, b, c, d, e, f, *

Мне нужно найти все возможные комбинации между каждым поднабором из каждого поднабора, чтобы каждая результирующая комбинация имела ровно один элемент из списка L, но любое количество вхожденийэлемент [*] (это подстановочный элемент).

Таким образом, результат работы необходимой функции с указанным выше набором S должен быть ( не точен на 100% ):

- [a,b],[c],[d,e],[f];
- [a,b],[c],[*],[d,e],[f];
- [a,b],[c],[d,e],[f],[*];
- [a,b],[c],[d,e],[f,*],[*];

Итак, в основном мне нужен алгоритм, который выполняет следующее:

1. берет подмножество из подмножества 1,
2. и добавляет одинбольше подмножества из подмножества 2, поддерживающего список «уникальных» элементов, полученных до сих пор (проверка списка «уникальных» пропускается, если подмножество содержит элемент *);
3. Повторяйте 2 до достижения N.

Другими словами, мне нужно сгенерировать все возможные «цепочки» (это пары, если N == 2, и тройки, если N==3), но каждая «цепочка» должна содержать ровно один элемент из списка L за исключением элемента подстановки *, который может встречаться много раз в каждой сгенерированной цепочке.

Я знаю, как это сделать с N == 2 (это простая генерация пар), но я не знаю, какулучшить алгоритм для работы с произвольными значениями для N.

Может быть Числа Стирлинга второго рода могут помочь здесь, но я не знаю, как применять их, чтобы получить желаемоерезультат.

Примечание: тип используемой здесь структуры данных для меня не важен.

Примечание. Этот вопрос возник из моего предыдущего похоже вопрос.

Answer 1

Это некоторые указатели (не полный код), которые могут привести вас в правильном направлении:

1. Я не думаю, что вам понадобятся некоторые продвинутые структуры данных здесь (используйте erlang список пониманий ). Вы также должны изучить модуль erlang sets и lists . Поскольку вы имеете дело с наборами и списком подмножеств, они кажутся идеально подходящими.
2. Вот как вещи с пониманием списков легко решаются для вас: [{X,Y} || X <- [[c],[d],[e,f]], Y <- [[a,b],[c,d]]]. Здесь я просто генерирую список из {X, Y} 2-кортежей, но для вашего случая использования вам придется поместить здесь настоящую логику ( включая ваше звездное дело)
3. Кроме того, обратите внимание, что при использовании списочных представлений вы можете использовать выходные данные одного генератора в качестве входных данных для более позднего генератора, например, [{X,Y} || X1 <- [[c],[d],[e,f]], X <- X1, Y1 <- [[a,b],[c,d]], Y <- Y1].
4. Также для удаления дубликатов из списка вещей L = ["a", "b", "a"]., вы можете в любое время просто сделать sets:to_list(sets:from_list(L)).

С помощью вышеперечисленных инструментов вы можете легко генерировать все возможные цепочки, а также применять свою логику по мере генерации этих цепочек.