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

У меня есть набор 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.

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

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

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


set data-partitioning combinations erlang
person skanatek    schedule 02.02.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

  1. Я не думаю, что вам понадобятся здесь какие-то сложные структуры данных (используйте erlang понимание списков< /а>). Вы также должны изучить erlang наборы и списки. Поскольку вы имеете дело с наборами и списком подмножеств, они кажутся идеальными.
  2. Вот как вам будет легко решать проблемы со списками: [{X,Y} || X <- [[c],[d],[e,f]], Y <- [[a,b],[c,d]]]. Здесь я просто генерирую список из двух кортежей {X,Y}, но для вашего варианта использования вам придется поместить сюда реальную логику (включая ваш звездный случай)
  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)).

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

person Abhinav Singh    schedule 11.02.2012