Найти уникальные комбинации значений из массивов, отфильтровывая любые дублирующиеся пары - PullRequest
Новая
       10

Найти уникальные комбинации значений из массивов, отфильтровывая любые дублирующиеся пары

3 голосов
/ 01 февраля 2012

Используя php, я ищу, чтобы найти набор уникальных комбинаций заданной длины, убедившись, что в более чем одной комбинации нет двух одинаковых значений. Например, если я хочу найти все уникальные комбинации из 3 значений (откат к комбинациям из 2 значений, если 3 невозможно) с этим массивом: 

$array = array(
    array('1', '2'),
    array('3', '4'),
    array('5', '6'),
);

Один из возможных наборов комбинаций: 123, 456, 14, 15, 16, 24, 25, 26, 34, 35, 36. Обратите внимание, что каждый номер всегда объединяется один раз и только один раз с другим номером. Никакие пары повторяющихся номеров не отображаются в любой комбинации. Просто для ясности, хотя 123 и 135 будут уникальными комбинациями, будет возвращена только одна из них, поскольку пара 13 встречается в обеих. Основным критерием является то, что все числа в конечном итоге сгруппированы друг с другом, но только один раз.

В конечном продукте количество массивов и количество значений будет значительно больше, чем в: 

$array = array(
    array('1', '2', '3', '4', '5', '6', '7', '8'),
    array('9', '10', '11', '12', '13', '14', '15', '16'),
    array('17', '18', '19', '20', '21', '22', '23', '24'),
    array('25', '26', '27', '28', '29', '30', '31')
);

Любая помощь / код для достижения этой цели была бы наиболее ценной.

UPDATE:

Я выбрал метод грубой силы. Во-первых, я использую пакет груши Math_Combinatorics для создания комбинаций, начиная с указанной группировки максимального размера и заканчивая парами. Таким образом, я могу получить все возможные комбинации при переборе, чтобы удалить дубликаты кластеров внутри групп. Этот код работает, но чрезвычайно интенсивно использует память. Генерация всех комбинаций для массива из 32 значений в группах по 6 использует 1,5 ГБ памяти. Есть ли лучший алгоритм или подход, который позволит мне использовать большие массивы без исчерпания памяти? Вот текущее состояние кода: 

require_once 'Combinatorics.php';
$combinatorics = new Math_Combinatorics;
$array = range(1,20,1);
$maxgroup = (6);
$combinations  = $combinatorics->combinations($array, $maxgroup);
for($c=$maxgroup-1;$c>1;$c--)
{
    $comb = $combinatorics->combinations($array, $c);
    $combinations = array_merge($combinations, $comb);
    $comb =  null;
}
for($j=0;$j<sizeof($combinations);$j++)
{
    for($i=sizeof($combinations)-1;$i>=$j+1;$i--)
   {
        $diff = array_intersect($combinations[$j], $combinations[$i]);
        if(count($diff)>1)
        {
            unset($combinations[$i]);
        }
    }
    $combinations = array_values($combinations);
}
print_r($combinations);

1 Ответ

0 голосов
/ 01 февраля 2012

Поскольку структура просто скрывает имеющиеся номера, сначала следует развернуть вложенные массивы.Я буду добр и сделаю это для вас: 

$numbers = []
foreach ($arrar as $subarr) {
    foreach ($subarr as $num) {
        $numbers[] = $num;
    }
}

Я предполагаю, что на входе нет повторяющихся чисел.

Далее, вы хотите выполнить свой алгоритм длянайти уникальные комбинации.С массивом это маленькое, даже рекурсивное решение будет работать.Вам не нужно пробовать все комбинаторно-много комбинаций.

...