std.algorithm.setops

auto cartesianProduct(R1, R2)(R1 range1, R2 range2)
if (!allSatisfy!(isForwardRange, R1, R2) || anySatisfy!(isInfinite, R1, R2));

auto cartesianProduct(RR...)(RR ranges)
if (ranges.length >= 2 && allSatisfy!(isForwardRange, RR) && !anySatisfy!(isInfinite, RR));

auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges)
if (!allSatisfy!(isForwardRange, R1, R2, RR) || anySatisfy!(isInfinite, R1, R2, RR));

2つ以上の範囲のデカルト積を簡単に計算する。積は それぞれの範囲からの要素のタプルの範囲である。

つの範囲の場合の条件は以下の通りである:

両方の範囲が有限である場合、一方は(少なくとも)前方範囲でなければならない。 でなければならない。 もう一方は入力範囲でなければならない。

一方の範囲が無限で、もう一方が有限の場合、有限の範囲は前進範囲でなければならない。 を順方向範囲とし、無限範囲を入力範囲とすることができる。

両方のレンジが無限であれば、両方とも順方向レンジでなければならない。

レンジが2つ以上ある場合、上記の条件は隣接する各レンジに適用される。 に適用される。

Parameters:

R1 range1	第一レンジ
R2 range2	第2レンジ
RR ranges	2つ以上の非無限前方範囲
RR otherRanges	0個以上の非無限前進範囲

Returns:

前方範囲 std.typecons.Tupleの要素を表す 与えられた範囲のデカルト積の要素を表す。

Examples:

import std.algorithm.searching : canFind;
import std.range;
import std.typecons : tuple;

auto N = sequence!"n"(0);         // 自然数全体の範囲
auto N2 = cartesianProduct(N, N); // 自然数すべてのペアの範囲

// さまざまな任意の数値の組み合わせは、有限時間内にその範囲内で見つけることができる。
assert(canFind(N2, tuple(0, 0)));
assert(canFind(N2, tuple(123, 321)));
assert(canFind(N2, tuple(11, 35)));
assert(canFind(N2, tuple(279, 172)));

Examples:

import std.algorithm.searching : canFind;
import std.typecons : tuple;

auto B = [ 1, 2, 3 ];
auto C = [ 4, 5, 6 ];
auto BC = cartesianProduct(B, C);

foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6],
             [2, 6], [3, 6]])
{
    assert(canFind(BC, tuple(n[0], n[1])));
}

Examples:

import std.algorithm.comparison : equal;
import std.typecons : tuple;

auto A = [ 1, 2, 3 ];
auto B = [ 'a', 'b', 'c' ];
auto C = [ "x", "y", "z" ];
auto ABC = cartesianProduct(A, B, C);

assert(ABC.equal([
    tuple(1, 'a', "x"), tuple(1, 'a', "y"), tuple(1, 'a', "z"),
    tuple(1, 'b', "x"), tuple(1, 'b', "y"), tuple(1, 'b', "z"),
    tuple(1, 'c', "x"), tuple(1, 'c', "y"), tuple(1, 'c', "z"),
    tuple(2, 'a', "x"), tuple(2, 'a', "y"), tuple(2, 'a', "z"),
    tuple(2, 'b', "x"), tuple(2, 'b', "y"), tuple(2, 'b', "z"),
    tuple(2, 'c', "x"), tuple(2, 'c', "y"), tuple(2, 'c', "z"),
    tuple(3, 'a', "x"), tuple(3, 'a', "y"), tuple(3, 'a', "z"),
    tuple(3, 'b', "x"), tuple(3, 'b', "y"), tuple(3, 'b', "z"),
    tuple(3, 'c', "x"), tuple(3, 'c', "y"), tuple(3, 'c', "z")
]));

void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = No.sortOutput);

ソートされた前方の範囲が与えられる rorにコピーする。 tgtにコピーする。 にコピーする。のすべての範囲は rorのすべての範囲はless でソートされていると仮定する。最も頻度の高い tgt.length要素が返される。

Parameters:

less	範囲がソートされる述語。
RangeOfRanges ror	less によってソートされた前方範囲の範囲。
Range tgt	共通要素をコピーする対象範囲。
SortOutput sorted	コピーされる要素がソート順であるかどうか。 関数" を使う。 largestPartialIntersectionは次のような場合に便利である。 この関数は、例えば、転置インデックスを検索して、ある用語を含む可能性が最も高い文書を探すのに便利である。 などに便利である。検索の複雑さは はΟ(n * log(tgt.length))である。n はすべての入力範囲の長さの合計である。 である。この方法は、出現頻度の連想配列を保持し の連想配列を保持し、その上位項目を選択するよりも高速である。 メモリも少なくてすむ(largestPartialIntersectionで直接 の結果を直接 tgtに直接構築され、余分なメモリを必要としない)。 範囲の少なくとも1つが多重集合の場合、重複する要素がすべて考慮される。 がすべて考慮される。結果は 結果は、すべての範囲をマージし、最も頻度の高い tgt.length要素を選ぶことと同じである。

警告 なぜなら largestPartialIntersectionは余分なメモリを割り当てないので 余分なメモリを確保しないため rorを変更したままにする。すなわち、largestPartialIntersection は rorを所有し の所有権を引き受ける。呼び出し後もror の内容を保持したい場合は、 に に複製を渡したいかもしれない。 largestPartialIntersection(に複製を渡したいかもしれない。 に複製を渡したいかもしれない。)

Examples:

import std.typecons : tuple, Tuple;

// 以下の配列セットのほとんどの配列にどの数値が含まれているかを
// 計算する。
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto b = new Tuple!(double, uint)[1];
// 入力範囲が変更されるため、複製を作成する必要がある
largestPartialIntersection(a.dup, b);
// 最初のメンバーは項目、2番目は出現回数である
writeln(b[0]); // tuple(7.0, 4u)
// 7.0は5つの入力のうち4つで発生しており、他のどの数値よりも多い

// より多くの頻出数字が必要な場合は、より大きなターゲット範囲を
// 作成するだけだ
auto c = new Tuple!(double, uint)[2];
largestPartialIntersection(a, c);
writeln(c[0]); // tuple(1.0, 3u)
// 1.0は3つの入力で発生する

// 複数セット
double[][] x =
[
    [1, 1, 1, 1, 4, 7, 8],
    [1, 7],
    [1, 7, 8],
    [4, 7],
    [7]
];
auto y = new Tuple!(double, uint)[2];
largestPartialIntersection(x.dup, y);
// 7.0は5回発生する
writeln(y[0]); // tuple(7.0, 5u)
// 1.0は6回発生する
writeln(y[1]); // tuple(1.0, 6u)

void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = No.sortOutput);

largestPartialIntersection と似ているが、交差点に含まれる各個別な要素に重みをつける。 に関連付けられている。

範囲の少なくとも1つが多重集合である場合、重複する要素のすべての出現が考慮される。 がすべて考慮される。結果 は、すべての入力範囲をマージし、最も高い tgt.lengthを選ぶことと等価である。

Parameters:

less	範囲がソートされる述語。
RangeOfRanges ror	前方範囲の範囲 less でソートされる。
Range tgt	共通要素をコピーする対象範囲。
WeightsAA weights	要素を重みにマッピングする連想配列。
SortOutput sorted	コピーされる要素がソート順であるかどうか。

Examples:

import std.typecons : tuple, Tuple;

// 以下の配列の集合のほとんどに含まれるのはどの番号か、
// 要素ごとの重み付きで示す
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto b = new Tuple!(double, uint)[1];
double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
largestPartialIntersectionWeighted(a, b, weights);
// 最初のメンバーは項目、2番目は出現回数である
writeln(b[0]); // tuple(4.0, 2u)
// 4.0は2回発生する -> 4.6 (2 * 2.3)
// 7.0は3回発生する -> 4.4 (3 * 1.1)

// 複数セット
double[][] x =
[
    [ 1, 1, 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto y = new Tuple!(double, uint)[1];
largestPartialIntersectionWeighted(x, y, weights);
writeln(y[0]); // tuple(1.0, 5u)
// 1.0は5回発生する -> 1.2 * 5 = 6

struct MultiwayMerge(alias less, RangeOfRanges);

MultiwayMerge!(less, RangeOfRanges) multiwayMerge(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);

複数のセットをマージする。入力セットは lessでソートされていると仮定される。計算は、一度に1つの共用体要素ずつ、遅延的に行われる。1回の 1回のpopFront 操作の複雑さはΟ(log(ror.length))である。しかし rorの長さは、範囲 MultiwayMerge に含まれる範囲の長さの分布に依存する。 に含まれる範囲の長さの分布に依存する。 ror.すべての範囲の長さが同じである場合(最悪のシナリオn (最悪のシナリオ)の場合、MultiwayMerge を完全に通過する複雑さはΟ(n * ror.length * log(ror.length))、つまり、log(ror.length) は、すべての範囲を順番に通過するよりも悪くなる。 になる。出力は、less によって(不安定に)ソートされる。

結果の範囲の長さは、入力として渡された範囲のすべての長さの合計である。 の長さの合計である。これは、すべての要素(重複 を含む)すべての要素が結果の範囲に転送されることを意味する。

後方互換性のために multiwayMergeは nWayUnion という名前で利用できる。 MultiwayMergeNWayUnion の名前で利用できる。 今後のコードでは multiwayMergeと MultiwayMergeを使うべきである。nWayUnion を使うべきであり、NWayUnion は非推奨となる。

Parameters:

less	与えられた範囲をソートする述語。
RangeOfRanges ror	less でソートされた範囲の共用体を計算する。

Returns:

の範囲の共用体の範囲。 ror.

警告 なぜなら MultiwayMergeは余分なメモリを割り当てないため を変更したままにする。 rorを変更したままにする。すなわち MultiwayMergeの所有権を持つ の rorを所有し、その要素を裁量で交換したり前進させたりする。もし もし ror呼び出し後もその内容を保持したい場合は、次のようにする。 に複製を渡したいかもしれない。 MultiwayMerge(に複製を渡したいかもしれない。 に複製を渡したいかもしれない(そして、呼び出しの間に複製をキャッシュしたいかもしれない)。

See Also:

std.algorithm.sorting.mergeという類似関数がある。 は、静的な数の異なる型のレンジを取る。

Examples:

import std.algorithm.comparison : equal;

double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto witness = [
    1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
];
assert(equal(multiwayMerge(a), witness));

double[][] b =
[
    // 重複を含む範囲
    [ 1, 1, 4, 7, 8 ],
    [ 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
// 複製が結果の範囲に伝搬される
assert(equal(multiwayMerge(b), witness));

static bool compFront(.ElementType!RangeOfRanges a, .ElementType!RangeOfRanges b);

this(RangeOfRanges ror);

@property bool empty();

@property ref auto front();

void popFront();

auto multiwayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);

複数の範囲の共用体を計算する。入力の 入力範囲は lessでソートされていると仮定される。計算は、一度に1つの共用体要素ずつ、遅延的に行われる。 multiwayUnion(ror)と関数的には等価である。 multiwayMerge(ror).uniq.

"multiwayUnionの出力は、入力に重複があっても重複しない。"

Parameters:

less	与えられた範囲をソートした述語。
RangeOfRanges ror	less 、交点を計算するためにソートされた範囲の範囲。

Returns:

の範囲の共用体。 ror.

も参照のこと: multiwayMerge

Examples:

import std.algorithm.comparison : equal;

// セット
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];

auto witness = [1, 4, 7, 8];
assert(equal(multiwayUnion(a), witness));

// 複数セット
double[][] b =
[
    [ 1, 1, 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 7, 8],
    [ 4 ],
    [ 7 ],
];
assert(equal(multiwayUnion(b), witness));

double[][] c =
[
    [9, 8, 8, 8, 7, 6],
    [9, 8, 6],
    [9, 8, 5]
];
auto witness2 = [9, 8, 7, 6, 5];
assert(equal(multiwayUnion!"a > b"(c), witness2));

struct SetDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);

SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);

の差を計算する。 r1と r2.つの範囲 はless でソートされていると仮定する。つの範囲の要素の型は共通でなければならない。 の要素型は共通でなければならない。

多集合の場合、要素a がx の中に r1に、y に r2の出現回数を考える。 結果の範囲におけるa の出現回数は、x > yの場合はx-y 、そうでない場合は0となる。

Parameters:

less	与えられた範囲を述語でソートする。
R1 r1	最初の範囲。
R2 r2	から引く範囲。 r1.

Returns:

と r1と r2.

See Also:

setSymmetricDifference

Examples:

import std.algorithm.comparison : equal;
import std.range.primitives : isForwardRange;

// セット
int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
assert(equal(setDifference(a, b), [5, 9]));
static assert(isForwardRange!(typeof(setDifference(a, b))));

// 複数セット
int[] x = [1, 1, 1, 2, 3];
int[] y = [1, 1, 2, 4, 5];
auto r = setDifference(x, y);
assert(equal(r, [1, 3]));
assert(setDifference(r, x).empty);

this(R1 r1, R2 r2);

void popFront();

@property ref auto front();

@property typeof(this) save();

@property bool empty();

struct SetIntersection(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges)
if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

2つ以上の入力範囲の交点を計算する。 入力範囲 ranges.範囲はless でソートされていると仮定する。範囲の要素 型は共通でなければならない。

多集合の場合、与えられた要素の出現数が最小の範囲が、その要素の出現数を伝播する。 である。 を結果の範囲に伝搬する。

Parameters:

less	与えられた範囲を述語でソートする。
Rs ranges	交点を計算する範囲。

Returns:

与えられた範囲の交点を含む範囲。

Examples:

import std.algorithm.comparison : equal;

// セット
int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
int[] c = [ 0, 1, 4, 5, 7, 8 ];
assert(equal(setIntersection(a, a), a));
assert(equal(setIntersection(a, b), [1, 2, 4, 7]));
assert(equal(setIntersection(a, b, c), [1, 4, 7]));

// 複数セット
int[] d = [ 1, 1, 2, 2, 7, 7 ];
int[] e = [ 1, 1, 1, 7];
assert(equal(setIntersection(a, d), [1, 2, 7]));
assert(equal(setIntersection(d, e), [1, 1, 7]));

this(Rs input);

@property bool empty();

void popFront();

@property ElementType front();

@property SetIntersection save();

struct SetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);

SetSymmetricDifference!(less, R1, R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);

の対称差を計算する。 r1と r2, の対称差を計算する。 r1およびr2 の対称的な差を計算する。つの範囲はless でソートされていると仮定される。 lessによってソートされる。でソートされる。 の要素型は共通でなければならない。

両方の範囲が(重複要素を含まない)集合である場合、結果として得られる は集合になる。範囲の少なくとも1つが多重集合の場合、結果の範囲は集合になる、 結果の範囲における要素x の出現回数は次のようになる。abs(a-b) ここで、a は、x における の出現数である。 r1b は におけるx の出現数である。 r2で、abs は絶対値である。

両引数が同じ型のL値の範囲である場合、次のようになる。 SetSymmetricDifferenceのL値の範囲となる。 の範囲にもなる。

Parameters:

less	与えられた範囲を述語でソートする。
R1 r1	最初の範囲。
R2 r2	2番目の範囲。

Returns:

と r1と r2.

See Also:

setDifference

Examples:

import std.algorithm.comparison : equal;
import std.range.primitives : isForwardRange;

// セット
int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][]));
static assert(isForwardRange!(typeof(setSymmetricDifference(a, b))));

// 複数セット
int[] c = [1, 1, 1, 1, 2, 2, 2, 4, 5, 6];
int[] d = [1, 1, 2, 2, 2, 2, 4, 7, 9];
assert(equal(setSymmetricDifference(c, d), setSymmetricDifference(d, c)));
assert(equal(setSymmetricDifference(c, d), [1, 1, 2, 5, 6, 7, 9]));

this(R1 r1, R2 r2);

void popFront();

@property ref auto front();

@property typeof(this) save();

ref auto opSlice();

@property bool empty();