始めるために、何を話しているのかを確認しましょう。 順序セットとしてシーケンスを示します：
{a, b, c, d...}
2つのシーケンスS1とS2
{a, b, c, d...}
デカルト積は、すべての可能な順序ペアのシーケンスであり、最初の要素はS1から、2番目はS2からです。 したがって、たとえば、2つのシーケンス
{a, b}
と
{x, y, z}
がある場合、デカルト積は
{{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}}
簡単にするために、S1とS2が同じタイプの要素で構成されていると仮定します。 もちろん、一連の文字列と一連の数字の文字列のデカルト積を一連の文字列（string、int）として定義できますが、特にC＃型システムは任意の長さのタプルでは最適に機能しないため、後で一般化することは困難です。
LINQには、デカルト積の計算専用の演算子があります。「メソッド構文」では
SelectMany
、「クエリ構文」では2つの「from」式を持つクエリです。
var s1 = new [ ] { a, b } ; <br/>
var s2 = new [ ] { x, y, z } ; <br/>
var product = <br/>
from first in s1 <br/>
from second in s2 <br/>
select new [ ] { first, second } ;
もちろん、デカルト積を3つ以上のシーケンスに一般化できます。 nシーケンスのデカルト積
{S1, S2, ... , Sn}
は、S1からの最初の要素、S2からの2番目の要素などを持つすべての可能なn要素シーケンスのシーケンスです。
この定義には自明なケースがありません：ゼロシーケンスのデカルト積は何ですか？ 次に、単一の要素を含むシーケンスで構成します。空のシーケンス、つまり
{ { } }
です。
これにより、1つのシーケンスのデカルト積の論理的な定義が得られることに注意してください。 単一のシーケンス（たとえば
{{a, b}}
）を含むシーケンスのデカルト積は、すべての可能な単一要素シーケンスのシーケンスであり、最初の（そして唯一の）要素は
{a, b}
です。 したがって、デカルト積
{{a, b}}
は
{{a}, {b}}
です。
LINQを使用すると、 最初に作業する量がわかっている場合 、任意の数のシーケンスのデカルト積を非常に簡単に作成できます 。
var product = <br/>
from first in s1 <br/>
from second in s2 <br/>
from third in s3 <br/>
select new [ ] { first, second, third } ;
しかし、コードを書く段階で、いくつのシーケンスを持っているかわからない場合はどうでしょうか？ つまり、関数本体の記述方法：
public static IEnumerable < IEnumerable < T >> CartesianProduct < T > ( this IEnumerable < IEnumerable < T >> sequences )
さて、誘導を使用する理由があります。 このアイデアは、再帰的に定義されたデータ構造を操作するときにほとんど失敗しません。
sequences
にゼロ
sequences
が含まれている場合、ジョブは完了します。
{ { } }
返すだけです。
たとえば、再び
{a, b}
と
{x, y, z}
という2つのシーケンスのデカルト積を見つける方法は？ 最初のシーケンスのデカルト積をカウントすることから始めます。 帰納的仮説として、何らかの方法でこれを行ったということで、
{{a}, {b}}
の答えがわかるようにします。
{{a}, {b}}
を
{x, y, z}
と組み合わせて、共通の製品を取得する方法は？
インスピレーションを求めて、2つのシーケンスのデカルト積の元の定義に戻りましょう。 デカルト積
{{a}, {b}}
および
{x, y, z}
は、無差別な
{{{a}, x}, {{a}, y}, {{a}, z}, {{b}, x}, {{b}, y}, {{b},z}}
、これらは取得したいものに魅力的に近いものです。
{{a}, {b}}
と
{x, y, z}
を含むシーケンスを作成してデカルト積
{{a}, {b}}
と
{x, y, z}
を見つけるだけではなく、いいえ、代わりに
x
を
{a}
追加してデカルト積を計算する必要があります
{a}
{a, x}
{a}
を取得
{a, x}
！ つまり、
{a}
と
{x}
連結します。
コードの観点から：
{{a}, {b}}
と言う古いデカルト積を考えてみましょう。 シーケンス
{x, y, z}
に接続したい：
var newProduct = <br/>
from old in oldProduct <br/>
from item in sequence <br/>
select old. Concat ( new [ ] { item } } ;
そして今、私たちは誘導移行を成功させました。
oldProduct
がデカルト積の場合、別のシーケンスとの組み合わせを計算して、新しいデカルト積を取得できます。
すべての消防士について：この方法は誘導の基礎で機能しますか？ はい デカルト積
{ { } }
とシーケンス
{{a}, {b}}
を組み合わせたい場合、
{ }
を
{a}
、
{ }
を
{b}
に接着して
{b}
、
{b}
を取得します。
すべてまとめてみましょう。
static IEnumerable < IEnumerable < T >> CartesianProduct < T > ( this IEnumerable < IEnumerable < T >> sequences ) <br/>
{ <br/>
// : <br/>
IEnumerable < IEnumerable < T >> result = new [ ] { Enumerable. Empty < T > ( ) } ; <br/>
foreach ( var sequence in sequences ) <br/>
{ <br/>
var s = sequence ; // <br/>
// : SelectMany, <br/>
result = <br/>
from seq in result <br/>
from item in s <br/>
select seq. Concat ( new [ ] { item } ) ; <br/>
} <br/>
return result ; <br/>
}
正常に機能しますが、必要に応じてもう少し美しくすることもできます。 基本的にここではバッテリーを使用しています。 整数のリストを合計するなど、簡単な例を考えてみましょう。 これを行う1つの方法は、「最初はバッテリーをゼロにする」と言うことです。 古いバッテリーに現在の要素を追加することにより、古いバッテリーから新しいバッテリーが取得されます。 バッテリーの開始値があり、何らかの方法でシーケンスの古い要素と現在の要素から新しい値を取得できる場合は、便利な
Aggregate
メソッドを使用できます。 バッテリーの開始値と、最後の値と現在のアイテムを取得し、バッテリーの新しい値を返す関数を取得します。 メソッドの出力は、バッテリーの合計値です。
この場合、バッテリーとして空の作業を開始し、そのたびに、現在のシーケンスを前のプロダクトの製品と組み合わせて「追加」します。 アルゴリズムの各ステップで、アキュムレータはすでに表示されているシーケンスのデカルト積に等しくなります。
static IEnumerable < IEnumerable < T >> CartesianProduct < T > ( this IEnumerable < IEnumerable < T >> sequences ) <br/>
{ <br/>
IEnumerable < IEnumerable < T >> emptyProduct = new [ ] { Enumerable. Empty < T > ( ) } ; <br/>
return sequences. Aggregate ( <br/>
emptyProduct, <br/>
( accumulator, sequence ) => <br/>
from accseq in accumulator <br/>
from item in sequence <br/>
select accseq. Concat ( new [ ] { item } ) ) ; <br/>
}
そして最後に、理解する人のためのいくつかの言葉。 LINQクエリの結果は、結果を直接ではなく、オンデマンドで結果を提供するクエリです 。 このバッテリーを作成するとき、実際にはデカルト積を計算しません。 起動時にデカルト積を生成する大規模で複雑なクエリを作成しています。 リクエストは精力的に作成されていますが、遅延して実行されます。
翻訳者から
エリックは、彼が使用したイディオムの特定の名前、つまり畳み込みを自分の投稿で回った。 ただし、Habrahabrには既にこのトピックに関する投稿がありました。 興味のある方は、 「F＃のカタモフィズム」の優れた翻訳を見つけることができます。
F＃で同じ問題を解決できますが、アルゴリズムは同じです。 LINQの代わりに、関数型言語の伝統的な特徴である優れた機能の1つであるリスト内包表記は、コードにうまく適合します。 優れたパフォーマンスを実現するには、演算子
(::)
を使用して、リストからアイテムを先頭に貼り付けるだけの価値があります。 この場合、デカルト積の古典的な外観を実現するには、作業を開始する前に元のシーケンスを反転する必要があります。
合計すると、畳み込み、パイプライン、およびリスト式により、このような美しいコードが得られます。
let product seqs =
List.rev seqs
|> List.fold
( fun acc cur ->
[ for seq in acc do
for item in cur do
yield item::seq]) [[]]