2

セットがあり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, *

各サブセットの各サブセット間で可能なすべての組み合わせを見つける必要があります。これにより、結果の各組み合わせには、リストから1つの要素が含まれます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. これまでに取得した「一意の」要素のリストを維持するサブセットからもう1つのサブサブセットを追加します2（サブセットに要素が含まれている場合、「一意の」リストのチェックはスキップされ*ます）。
  3. 2に達するまで繰り返しNます。

言い換えると、可能なすべての「チェーン」（の場合はペア、の場合N == 2はトリプルN==3）を生成する必要がありますが、各「チェーン」には、生成された各要素で何度も発生する可能性Lのあるワイルドカード要素を除いて、リストから1つの要素が含まれている必要があります。*鎖。

これを行う方法は知っていますがN == 2（単純なペア生成です）、の任意の値を処理するようにアルゴリズムを拡張する方法がわかりませんN。

ここでは、第2種のスターリング数が役立つかもしれませんが、目的の結果を得るためにそれらを適用する方法がわかりません。

注：ここで使用するデータ構造のタイプは、私にとって重要ではありません。

注：この質問は、以前の同様の質問から発展したものです。

4

1 に答える 1

0

これらは、おそらく正しい方向に導くことができるいくつかのポインタ（完全なコードではありません）です：

  1. ここでは高度なデータ構造は必要ないと思います（erlangリスト内包表記を利用してください）。また、erlangセットとリストモジュールを調べる必要があります。セットとサブセットのリストを扱っているので、それらは理想的なフィットのようです。
  2. リスト内包表記の問題を簡単に解決する方法は次のとおりです。[{X,Y} || X <- [[c],[d],[e,f]], Y <- [[a,b],[c,d]]].ここでは、{X、Y} 2タプルのリストを生成していますが、ユースケースでは、ここに実際のロジックを配置する必要があります（スターケースを含む）。
  3. さらに、リスト内包表記を使用すると、1つのジェネレーターの出力を後のジェネレーターの入力として使用できることに注意してください。[{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)).

上記のツールを使用すると、考えられるすべてのチェーンを簡単に生成でき、これらのチェーンが生成されるときにロジックを適用することもできます。

于 2012-02-11T00:42:16.443 に答える