Комбинаторное итерирование

Вернуться к главной странице

Инструменты для комбинаторного итерирования: декартово произведение, перестановки, сочетания, сочетания с повторениями, булеан (множество всех подмножеств).

---

Product

Декартово произведение коллекций.

Выходные кортежи — массивы-списки (индексы с нуля, в порядке входных коллекций); исходные ключи отбрасываются. Порядок соответствует itertools.product из Python (лексикографический, с сохранением порядка входов): самая правая коллекция «пробегает» быстрее всех.

Входные коллекции должны быть конечными. Они потребляются один раз (материализуются внутри), поэтому генераторы поддерживаются, но повторно итерироваться не могут.

Особые случаи:

• product() без аргументов возвращает один пустой кортеж: [[]]
• если любая входная коллекция пуста, результат пуст

Combinatorics::product(iterable ...$iterables): \Generator

use IterTools\Combinatorics;

$numbers = [1, 2];
$letters = ['a', 'b'];

foreach (Combinatorics::product($numbers, $letters) as $tuple) {
    print_r($tuple);
}
// [1, 'a']
// [1, 'b']
// [2, 'a']
// [2, 'b']

Permutations

Перестановки элементов коллекции.

Выходные кортежи — массивы-списки (индексы с нуля, в порядке входной коллекции); исходные ключи отбрасываются. Порядок соответствует itertools.permutations из Python (лексикографический по позиции во входе, а не по значению): одинаковые значения различаются по позиции, поэтому permutations([1, 1]) даёт [[1, 1], [1, 1]].

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

Особые случаи:

• $r = 0 даёт один пустой кортеж: [[]]
• если $r больше count($data), результат пуст
• $r = null означает перестановки полной длины (эквивалентно $r = count($data))
• пустой вход с $r = null (или $r = 0) даёт один пустой кортеж: [[]]

Выбрасывает \InvalidArgumentException, если $r отрицательное.

Combinatorics::permutations(iterable $data, ?int $r = null): \Generator

use IterTools\Combinatorics;

$data = [1, 2, 3];

foreach (Combinatorics::permutations($data) as $tuple) {
    print_r($tuple);
}
// [1, 2, 3]
// [1, 3, 2]
// [2, 1, 3]
// [2, 3, 1]
// [3, 1, 2]
// [3, 2, 1]

Combinations

Сочетания (без повторений) элементов коллекции.

Выходные кортежи — это list-массивы (с 0-индексацией, в порядке входа); ключи исходной коллекции игнорируются. Порядок выхода соответствует Python's itertools.combinations (лексикографический по позиции во входе, не по значению): дублирующиеся значения считаются уникальными по позиции: combinations([1, 1], 2) даёт [[1, 1]].

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

Особые случаи:

• $r = 0 даёт один пустой кортеж: [[]]
• если $r больше count($data), результат пуст
• $r = count($data) даёт ровно один кортеж, содержащий все элементы входа

Выбрасывает \InvalidArgumentException, если $r отрицательное.

Combinatorics::combinations(iterable $data, int $r): \Generator

use IterTools\Combinatorics;

$data = [1, 2, 3, 4];

foreach (Combinatorics::combinations($data, 2) as $tuple) {
    print_r($tuple);
}
// [1, 2]
// [1, 3]
// [1, 4]
// [2, 3]
// [2, 4]
// [3, 4]

Combinations With Replacement

Сочетания с повторениями элементов коллекции.

Выходные кортежи — это list-массивы (с 0-индексацией, в порядке входа); ключи исходной коллекции игнорируются. Порядок выхода соответствует Python's itertools.combinations_with_replacement (лексикографический по позиции во входе, не по значению): дублирующиеся значения считаются уникальными по позиции и могут давать дублирующиеся выходные кортежи: combinationsWithReplacement([1, 1], 2) даёт [[1, 1], [1, 1], [1, 1]].

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

В отличие от combinations(), $r может превышать count($data) — элементы повторяются.

Особые случаи:

• $r = 0 даёт один пустой кортеж: [[]]
• пустой вход с $r > 0 даёт пустой результат
• пустой вход с $r = 0 даёт один пустой кортеж: [[]]

Выбрасывает \InvalidArgumentException, если $r отрицательное.

Combinatorics::combinationsWithReplacement(iterable $data, int $r): \Generator

use IterTools\Combinatorics;

$data = [1, 2, 3];

foreach (Combinatorics::combinationsWithReplacement($data, 2) as $tuple) {
    print_r($tuple);
}
// [1, 1]
// [1, 2]
// [1, 3]
// [2, 2]
// [2, 3]
// [3, 3]

Powerset

Все подмножества коллекции, упорядоченные по длине, а внутри каждой длины — по позиции во входе.

Выходные подмножества — это list-массивы (с 0-индексацией, в порядке входа); ключи исходной коллекции игнорируются. Подмножества отдаются в порядке возрастания длины; внутри каждой длины порядок совпадает с Combinatorics::combinations (лексикографический по позиции во входе, не по значению), поэтому дублирующиеся значения считаются уникальными по позиции: powerset([1, 1]) даёт [[], [1], [1], [1, 1]].

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

Внимание: булеан из n элементов содержит 2**n подмножеств — расход растёт экспоненциально. Вход из 20 элементов даёт более миллиона подмножеств; вход из 30 элементов — более миллиарда.

Особые случаи:

• пустой вход даёт одно пустое подмножество: [[]]

Combinatorics::powerset(iterable $data): \Generator

use IterTools\Combinatorics;

$data = [1, 2, 3];

foreach (Combinatorics::powerset($data) as $subset) {
    print_r($subset);
}
// []
// [1]
// [2]
// [3]
// [1, 2]
// [1, 3]
// [2, 3]
// [1, 2, 3]

use IterTools\Combinatorics;

// Перебрать все комбинации фича-флагов для параметризованных тестов.
$flags = ['darkMode', 'beta', 'analytics'];

foreach (Combinatorics::powerset($flags) as $enabled) {
    print_r($enabled);
}
// []
// ['darkMode']
// ['beta']
// ['analytics']
// ['darkMode', 'beta']
// ['darkMode', 'analytics']
// ['beta', 'analytics']
// ['darkMode', 'beta', 'analytics']

См. также Stream::powerset.