找到所有可能的N套子集與Erlang之間的配對

Question

我有一套S。它包含N子集（其中又包含不同長度的一些子子集）：

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

我也有一個列表，包含在一套S「獨一無二」的元素L：

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的任意值。

也許Stirling numbers of the second kind可以幫助這裏，但我不知道如何應用它們來獲得所需的結果。

注意：這裏使用的數據結構的類型對我來說並不重要。

注意：這個問題已經從我以前的similar問題發展而來。

Answer 1

這些都是一些指針（不是一個完整的代碼），可以帶你到正確的方向可能是：

1. 我不認爲你會需要一些高級數據結構在這裏（利用二郎list comprehensions的） 。您還必須探索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)).

有了上面的工具，你可以很容易地生成所有可能的鏈條，也執行你的邏輯，這些鏈獲取生成。