Как получить все уникальные пары из массива?

Question

[ak_wi]

Есть массив, содержащий внутри себя массивы со строками. Например:

$array = [
    ['Синий', 'Алый', 'Коричневый'],
    ['Дерево', 'Сталь', 'Железо'],
    ['Корабль', 'Самолет', 'Поезд'],
...
];

Как получить все уникальные сочетания значений из массивов внутри него?

Например: Синий - Дерево - Корабль, Синий - Дерево - Самолет и т.п.

Думаю понятно, что пары внутри массивов не нужны, типа синий-алый - дерево и т.п.

Comments

[Дмитрий]

А как Вы пытались решить задачу?

[ak_wi]

Решение в лоб было таким:

function foo($first, $second, $third) {
    $pairs = [];

    foreach ($first as $key => $item) {
        foreach ($second as $s_item) {
            foreach ($third as $value) {
                $pairs[] = $item . ' -- ' .  $s_item . ' -- ' . $value;
            }
        }
    }

    return $pairs;
}

Но оно не подходит, если кол-во массивов в изначальном равно N, т.е. может быть больше 3-х

[Максим Федоров]

ak_wi, попробуйте рекурсией или через цикл for

Answer 1

[0xD34F]

$numArr = count($array);
$numElems = count($array[0]);

$combinations = [];
$numCombinations = pow($numElems, $numArr);

for ($i = 0; $i < $numCombinations; $i++) {
  $combination = [];

  for ($j = 0; $j < $numArr; $j++) {
    $arrIndex = $j;
    $elIndex = $i / pow($numElems, $j) % $numElems;
    $combination[] = $array[$arrIndex][$elIndex];
  }

  $combinations[] = $combination;
}

Comments

[Владимир Олохтонов]

Такой подход работает только для случая когда все массивы одинаковой длины, для обобщения на произвольные размеры нужно брать произведение длин массивов вместо степени :)

[ak_wi]

Владимир Олохтонов, спасибо за комментарий. Получается, что в идеале решение должно быть вот таким:

/**
 * Получить произведение длинн массивов
 * @param $array
 * @return float|int
 */
function getProductOfSubArrCount($array) {
    $arrayCount = [];
    foreach ($array as $subArr) {
        $arrayCount[] = count($subArr);
    }
    return array_product($arrayCount);
}

$numArr = count($array);
$numElems = count($array[0]);

$combinations = [];
$numCombinations = getProductOfSubArrCount($array);

for ($i = 0; $i < $numCombinations; $i++) {
    $combination = [];

    for ($j = 0; $j < $numArr; $j++) {
        $arrIndex = $j;
        $elIndex = $i / pow($numElems, $j) % $numElems;
        $combination[] = $array[$arrIndex][$elIndex];
    }

    $combinations[] = $combination;
}

[Владимир Олохтонов]

ak_wi, кажется вот здесь тоже должно быть частичное произведение размеров: $elIndex = $i / pow($numElems, $j) % $numElems;

Но я могу ошибаться, поскольку не знаю PHP.

[ak_wi]

pow($numElems, $j) - это возведение основания numElems в показатель степени j

При замене на произведение длин массивов выдает некорректные результаты

[Владимир Олохтонов]

Вот код на питоне, который делает то о чём я говорил, если что-то будет непонятно - спрашивайте, я постараюсь объяснть :)

import functools


def make_help_tables(arr):
    sizes = [len(s) for s in arr]
    dividers = [1] 
    for size in sizes:
        dividers.append(dividers[-1] * size)
    return sizes, dividers


def product(arr):         
    if not arr:                                 
        return
    
    arr_size = len(arr)
    sizes, dividers = make_help_tables(arr)
    total_variants = functools.reduce(lambda x, y: x * y, sizes) 
    
    for variant in range(total_variants):
        indexes = [(variant // dividers[i]) % sizes[i] for i in range(arr_size)]
        yield indexes, [arr[i][idx] for i, idx in enumerate(indexes)]


m = [['A', 'B'], [1, 2, 3], ['Привет!']]
for indexes, combination in product(m):
    print('{} -> {}'.format(indexes, combination))

[0, 0, 0] -> ['A', 1, 'Привет!']
[1, 0, 0] -> ['B', 1, 'Привет!']
[0, 1, 0] -> ['A', 2, 'Привет!']
[1, 1, 0] -> ['B', 2, 'Привет!']
[0, 2, 0] -> ['A', 3, 'Привет!']
[1, 2, 0] -> ['B', 3, 'Привет!']

Вот мои заметки в процессе поиска решения:

Для начала попробуем реализовать схему "переполнения разрядов", как в системе счисления, но с учётом разной "ёмкости" разрядов.

Массивы [[1, 2], [а, б, в]]

Всего вариантов 2 * 3 = 6

Варианты (индексы):
1) [0, 0]                                                                                   (0 // 3) % 2 = 0; (0 // 1) % 3 = 0
2) [0, 1]                                                                                   (1 // 3) % 2 = 0; (1 // 1) % 3 = 1
3) [0, 2] <-- переполнение последнего разряда                   (2 // 3) % 2 = 0; (2 // 1) % 3 = 2
4) [1, 0] <-- перенос в старший разряд                                 (3 // 3) % 2 = 1; (3 // 1) % 3 = 0
5) [1, 1]                                                                                   (4 // 3) % 2 = 1; (4 // 1) % 3 = 1
6) [1, 2]                                                                                   (5 // 3) % 2 = 1; (5 // 1) % 3 = 2

Что нам нужно для подсчёта?
1) Размеры массивов (для вычетов по модулю)
2) Список произведений размеров массивов (в обратном порядке)



Попробуем теперь разобраться как перейти к прямому порядку переполнения вместо обратного.

Массивы [[1, 2], [3, 4, 5], [6]]

Всего вариантов 2 * 3 * 1 = 6

Варианты (индексы):
1) [0, 0, 0]	(0 // 1) % 2 = 0; (0 // (1 * 2)) % 3 = 0; (0 // 1 * 2 * 3) % 1 = 0
2) [1, 0, 0]	(1 // 1) % 2 = 1; (1 // (1 * 2)) % 3 = 0; (1 // 1 * 2 * 3) % 1 = 0
3) [0, 1, 0]	(2 // 1) % 2 = 0; (2 // (1 * 2)) % 3 = 1; (2 // 1 * 2 * 3) % 1 = 0
4) [1, 1, 0]	(3 // 1) % 2 = 1; (3 // (1 * 2)) % 3 = 1; (3 // 1 * 2 * 3) % 1 = 0
5) [0, 2, 0]	(4 // 1) % 2 = 0; (4 // (1 * 2)) % 3 = 2; (4 // 1 * 2 * 3) % 1 = 0
6) [1, 2, 0]	(5 // 1) % 2 = 1; (5 // (1 * 2)) % 3 = 2; (5 // 1 * 2 * 3) % 1 = 0

В итоге таблица делителей формируется следующим образом:
1 для первого массива
1 * 2 для второго (поскольку размер первого равен 1)
1 * 2 * 3 для первого (размер второго, умноженный на накопленный делитель)

А вот реализация, аналог которой используется в python itertools.product (только без накопления результатов в памяти), она ещё и быстрее почти в 10 раз:

def product(pools):
    result = [[]]
    for pool in pools:
        result = [x + [y] for x in result for y in pool]
        
    for prod in result:
        yield prod

Answer 2

[oleg_ods]

Разбить на три массива в каждом из которых 1 характеристика(цвет, материал, транспорт), а дальше с помощью 3-х вложенных циклов формировать строку.

Comments

[ak_wi]

а если массивов N количество?)