std.algorithm.setops

Это подмодуль std.algorithm. Он содержит универсальные алгоритмы, реализующие операции над множествами.

Функции multiwayMerge, multiwayUnion, setDifference, setIntersection, setSymmetricDifference ожидают в качестве входных данных диапазон отсортированных диапазонов.

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

Лицензия:

Лицензия Boost 1.0.

Авторы:

Андрей Александреску

Источник

std/algorithm/setops.d

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

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

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

Лениво вычисляет декартово произведение двух или более диапазонов. Произведение — это диапазон кортежей элементов из каждого соответствующего диапазона.

Условия для случая с двумя диапазонами следующие:

Если оба диапазона конечны, то один должен быть (по крайней мере) прямым диапазоном, а другой — диапазоном ввода.

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

Если оба диапазона бесконечны, то оба должны быть прямыми диапазонами.

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

Параметры:

R1 range1	Первый диапазон
R2 range2	Второй диапазон
RR ranges	Два или более конечных прямых диапазонов
RR otherRanges	Ноль или более конечных прямых диапазонов

Возвращает:

Прямой диапазон std.typecons.Tuple, представляющий элементы декартова произведения заданных диапазонов.

Примеры:

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

auto N = sequence!"n"(0);         // the range of natural numbers
auto N2 = cartesianProduct(N, N); // the range of all pairs of natural numbers

// Various arbitrary number pairs can be found in the range in finite time.
assert(canFind(N2, tuple(0, 0)));
assert(canFind(N2, tuple(123, 321)));
assert(canFind(N2, tuple(11, 35)));
assert(canFind(N2, tuple(279, 172)));

Примеры:

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])));
}

Примеры:

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 элементы.

Параметры:

less	Предикат, по которому отсортированы диапазоны.
RangeOfRanges ror	Диапазон прямых диапазонов, отсортированных по less.
Range tgt	Целевой диапазон для копирования общих элементов.
SortOutput sorted	Нужно ли сортировать скопированные элементы. Функция largestPartialIntersection полезна, например, для поиска в обратном индексе документов, наиболее вероятно содержащих некоторые интересующие термины. Сложность поиска составляет Ο(n * log(tgt.length)), где n — сумма длин всех входных диапазонов. Этот подход быстрее, чем сохранение ассоциативного массива частот и выбор верхних элементов, и также требует меньше памяти (largestPartialIntersection строит свой результат напрямую в tgt и не требует дополнительной памяти). Если хотя бы один из диапазонов является мультимножеством, то учитываются все вхождения дублирующего элемента. Результат эквивалентен слиянию всех диапазонов и выбору наиболее частых tgt.length элементов.

Предупреждение

Так как largestPartialIntersection не выделяет дополнительной памяти, он оставит ror изменённым. Иными словами, largestPartialIntersection берёт на себя управление ror и произвольно меняет местами и перемещает элементы внутри него. Если вам нужно, чтобы ror сохранил своё содержимое после вызова, вы можете передать дубликат в largestPartialIntersection (и, возможно, кэшировать дубликат между вызовами).

Примеры:

import std.typecons : tuple, Tuple;

// Figure which number can be found in most arrays of the set of
// arrays below.
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto b = new Tuple!(double, uint)[1];
// it will modify the input range, hence we need to create a duplicate
largestPartialIntersection(a.dup, b);
// First member is the item, second is the occurrence count
writeln(b[0]); // tuple(7.0, 4u)
// 7.0 occurs in 4 out of 5 inputs, more than any other number

// If more of the top-frequent numbers are needed, just create a larger
// tgt range
auto c = new Tuple!(double, uint)[2];
largestPartialIntersection(a, c);
writeln(c[0]); // tuple(1.0, 3u)
// 1.0 occurs in 3 inputs

// multiset
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 occurs 5 times
writeln(y[0]); // tuple(7.0, 5u)
// 1.0 occurs 6 times
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, но сопоставляет вес каждому отличному элементу в пересечении.

Если хотя бы один из диапазонов является мультимножеством, то все вхождения дублирующего элемента учитываются. Результат эквивалентен объединению всех входных диапазонов и выбору элементов с наибольшим tgt.length, ранжированием по весу.

Параметры:

less	Предикат, по которому отсортированы диапазоны.
RangeOfRanges ror	Диапазон прямых диапазонов, отсортированных по less.
Range tgt	Целевой диапазон для копирования общих элементов.
WeightsAA weights	Ассоциативный массив, сопоставляющий элементы с весами.
SortOutput sorted	Нужно ли сортировать скопированные элементы.

Примеры:

import std.typecons : tuple, Tuple;

// Figure which number can be found in most arrays of the set of
// arrays below, with specific per-element weights
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);
// First member is the item, second is the occurrence count
writeln(b[0]); // tuple(4.0, 2u)
// 4.0 occurs 2 times -> 4.6 (2 * 2.3)
// 7.0 occurs 3 times -> 4.4 (3 * 1.1)

// multiset
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 occurs 5 times -> 1.2 * 5 = 6

struct MultiwayMerge(alias less, RangeOfRanges);

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

Объединяет несколько множеств. Входные множества передаются как диапазон диапазонов, и предполагается, что каждый из них отсортирован по less. Вычисления выполняются лениво, один элемент объединения за раз. Сложность одной операции popFront составляет Ο(log(ror.length)). Однако длина ror уменьшается по мере исчерпания диапазонов в нём, поэтому сложность полного прохода через MultiwayMerge зависит от распределения длин диапазонов, содержащихся в ror. Если все диапазоны имеют одинаковую длину n (худший случай), сложность полного прохода через MultiwayMerge составляет Ο(n * ror.length * log(ror.length)), т.е., log(ror.length) раз хуже, чем просто последовательный проход по всем диапазонам. Выходной диапазон отсортирован (неустойчиво) по less.

Длина результирующего диапазона равна сумме длин всех входных диапазонов. Это означает, что все элементы (включая дубликаты) передаются в результирующий диапазон.

Для обратной совместимости multiwayMerge доступен под именем nWayUnion и MultiwayMerge под именем NWayUnion . Будущий код должен использовать multiwayMerge и MultiwayMerge как nWayUnion и NWayUnion будут устаревшими.

Параметры:

less	Предикат, по которому отсортированы заданные диапазоны.
RangeOfRanges ror	Диапазон диапазонов, отсортированных по less для вычисления объединения.

Возвращает:

Диапазон объединения диапазонов в ror.

Предупреждение

Так как MultiwayMerge не выделяет дополнительной памяти, он оставит ror изменённым. Иными словами, MultiwayMerge берёт на себя управление ror и произвольно меняет местами и перемещает элементы внутри него. Если вам нужно, чтобы ror сохранил своё содержимое после вызова, вы можете передать дубликат в MultiwayMerge (и, возможно, кэшировать дубликат между вызовами).

См. также:

std.algorithm.sorting.merge для аналогичной функции, принимающей статическое количество диапазонов, возможно, разных типов.

Примеры:

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 =
[
    // range with duplicates
    [ 1, 1, 4, 7, 8 ],
    [ 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
// duplicates are propagated to the resulting range
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. Вычисления выполняются лениво, один элемент объединения за раз. multiwayUnion(ror) функционально эквивалентно multiwayMerge(ror).uniq.

"Выход multiwayUnion не содержит дубликатов, даже если входные данные содержат дубликаты."

Параметры:

less	Предикат, по которому отсортированы диапазоны.
RangeOfRanges ror	Диапазон диапазонов, отсортированных по less для вычисления пересечения.

Возвращает:

Диапазон объединения диапазонов в ror. См. также: multiwayMerge

Примеры:

import std.algorithm.comparison : equal;

// sets
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];

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

// multisets
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 в противном случае.

Параметры:

less	Предикат, по которому отсортированы заданные диапазоны.
R1 r1	Первый диапазон.
R2 r2	Диапазон, который вычитается из r1.

Возвращает:

Диапазон разности r1 и r2.

См. также:

setSymmetricDifference

Примеры:

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

//sets
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))));

// multisets
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)
Constraints: if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

Лениво вычисляет пересечение двух или более входных диапазонов ranges. Диапазоны предполагаются отсортированными по less. Типы элементов диапазонов должны иметь общий тип.

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

Параметры:

less	Предикат, по которому отсортированы заданные диапазоны.
Rs ranges	Диапазоны для вычисления пересечения.

Возвращает:

Диапазон, содержащий пересечение заданных диапазонов.

Примеры:

import std.algorithm.comparison : equal;

// sets
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]));

// multisets
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. Типы элементов двух диапазонов должны иметь общий тип.

Если оба диапазона являются множествами (без дублируемых элементов), результирующий диапазон также будет множеством. Если хотя бы один из диапазонов является мультимножеством, количество появлений элемента x в результирующем диапазоне равно abs(a-b), где a — количество появлений x в r1, b — количество появлений x в r2, а abs — абсолютное значение.

Если оба аргумента представляют собой диапазоны L-значений одного типа, то SetSymmetricDifference также будет диапазоном L-значений этого типа.

Параметры:

less	Предикат, по которому отсортированы заданные диапазоны.
R1 r1	Первый диапазон.
R2 r2	Второй диапазон.

Возвращает:

Диапазон симметрической разности между r1 и r2.

См. также:

setDifference

Примеры:

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

// sets
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))));

//mutisets
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();