Получить возможные комбинации массивов

ТАК,

Проблема

Из SQL я получаю массив со строками (плоский массив) – пусть это будет

 $ rgData = ['foo', 'bar', 'baz', 'bee', 'feo'];

Теперь я хочу получить возможные комбинации пар и триплетов этого массива (и, в общем случае, комбинации из 4 элементов e tc). Чтобы быть более конкретным: я имею в виду комбинации в математическом смысле (без дубликатов), т. Е. Те, которые считаются равными

введите описание изображения здесь

-so для массива выше, который будет равен 10 для обеих пар и триплетов.

Мой подход

Я начал с отображения возможных значений для введите описание изображения здесь для выбора выбранных элементов. Мое текущее решение – указать, если элемент выбран как «1», а «0» – в противном случае. Для образца выше, который будет:

 foo bar baz bee feo
  0 0 1 1 1 -> [baz, bee, feo]
  0 1 0 1 1 -> [bar, bee, feo]
  0 1 1 0 1 -> [bar, baz, feo]
  0 1 1 1 0 -> [бар, база, пчела]
  1 0 0 1 1 -> [foo, bee, feo]
  1 0 1 0 1 -> [foo, baz, feo]
  1 0 1 1 0 -> [foo, baz, bee]
  1 1 0 0 1 -> [foo, baz, feo]
  1 1 0 1 0 -> [foo, bar, bee]
  1 1 1 0 0 -> [foo, bar, baz]

И все, что мне нужно сделать, это как-то создать желаемый бит. Вот мой код в PHP:

function nextAssoc($sAssoc) { if(false !== ($iPos = strrpos($sAssoc, '01'))) { $sAssoc[$iPos] = '1'; $sAssoc[$iPos+1] = '0'; return substr($sAssoc, 0, $iPos+2). str_repeat('0', substr_count(substr($sAssoc, $iPos+2), '0')). str_repeat('1', substr_count(substr($sAssoc, $iPos+2), '1')); } return false; } function getAssoc(array $rgData, $iCount=2) { if(count($rgData)<$iCount) { return null; } $sAssoc = str_repeat('0', count($rgData)-$iCount).str_repeat('1', $iCount); $rgResult = []; do { $rgResult[]=array_intersect_key($rgData, array_filter(str_split($sAssoc))); } while($sAssoc=nextAssoc($sAssoc)); return $rgResult; }

-Я решил сохранить мои биты как обычную строку. Мой алгоритм для создания следующей ассоциации:

Попробуйте найти «01». Если не найден, то это 11..100..0 case (так что это максимум, больше не может быть найдено). Если найдено, перейдите на второй шаг
Перейдите в правую позицию «01» в строке. Переключите его в положение «10», а затем переместите все нули, которые более резкие, чем «позиция 01» – слева. Например, 01110 : самая правильная позиция «01» равна 0, поэтому сначала мы переключаем этот «01» на «10». Строка теперь равна 10110 . Теперь переходим в правую часть (она не содержит 10 частей, поэтому она начинается с 0 + 2 = 2-й символ) и перемещает все нули влево, т.е. 110 будет 011 . В результате мы имеем 10 + 011 = 10111 качестве следующей ассоциации для 01110 .

Я нашел подобную проблему здесь, но там OP хочет сочетания с дубликатами, в то время как я хочу их без дублирования.

Вопрос

Мой вопрос о двух моментах:

Для моего решения может быть еще один способ повысить производительность следующего бита?
Может быть, для этого есть более простые решения? Кажется, это стандартная проблема.

Мне жаль, что я не предлагаю PHP-решение, потому что я не программировал на PHP уже довольно долгое время, но позвольте мне показать вам быстрое решение Scala. Возможно, это вдохновит вас:

 val array = Vector("foo", "bar", "baz", "bee", "feo") for (i <- 0 until array.size; j <- i + 1 until array.size; k <- j + 1 until array.size) yield (array(i), array(j), array(k))

Результат:

 Vector((foo,bar,baz), (foo,bar,bee), (foo,bar,feo), (foo,baz,bee), (foo,baz,feo), (foo,bee,feo), (bar,baz,bee), (bar,baz,feo), (bar,bee,feo), (baz,bee,feo))

Универсальный код для генерации k-комбинаций:

 def combinations(array: Vector[String], k: Int, start: Int = 0): Iterable[List[String]] = { if (k == 1 || start == array.length) for (i <- start until array.length) yield List(array(i)) else for (i <- start until array.length; c <- combinations(array, k - 1, i + 1)) yield array(i) :: c }

Результаты:

 scala> combinations(Vector("a", "b", "c", "d", "e"), 1) res8: Iterable[List[String]] = Vector(List(a), List(b), List(c), List(d), List(e)) scala> combinations(Vector("a", "b", "c", "d", "e"), 2) res9: Iterable[List[String]] = Vector(List(a, b), List(a, c), List(a, d), List(a, e), List(b, c), List(b, d), List(b, e), List(c, d), List(c, e), List(d, e)) scala> combinations(Vector("a", "b", "c", "d", "e"), 3) res10: Iterable[List[String]] = Vector(List(a, b, c), List(a, b, d), List(a, b, e), List(a, c, d), List(a, c, e), List(a, d, e), List(b, c, d), List(b, c, e), List(b, d, e), List(c, d, e)) scala> combinations(Vector("a", "b", "c", "d", "e"), 4) res11: Iterable[List[String]] = Vector(List(a, b, c, d), List(a, b, c, e), List(a, b, d, e), List(a, c, d, e), List(b, c, d, e)) scala> combinations(Vector("a", "b", "c", "d", "e"), 5) res12: Iterable[List[String]] = Vector(List(a, b, c, d, e))

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

Рекурсивное решение:

 function subcombi($arr, $arr_size, $count) { $combi_arr = array(); if ($count > 1) { for ($i = $count - 1; $i < $arr_size; $i++) { $highest_index_elem_arr = array($i => $arr[$i]); foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { $combi_arr[] = $subcombi_arr + $highest_index_elem_arr; } } } else { for ($i = $count - 1; $i < $arr_size; $i++) { $combi_arr[] = array($i => $arr[$i]); } } return $combi_arr; } function combinations($arr, $count) { if ( !(0 <= $count && $count <= count($arr))) { return false; } return $count ? subcombi($arr, count($arr), $count) : array(); } $input_arr = array('foo', 'bar', 'baz', 'bee', 'feo'); $combi_arr = combinations($input_arr, 3); var_export($combi_arr); echo ";\n"; OUTPUT: array ( 0 => array ( 0 => 'foo', 1 => 'bar', 2 => 'baz', ), 1 => array ( 0 => 'foo', 1 => 'bar', 3 => 'bee', ), 2 => array ( 0 => 'foo', 2 => 'baz', 3 => 'bee', ), 3 => array ( 1 => 'bar', 2 => 'baz', 3 => 'bee', ), 4 => array ( 0 => 'foo', 1 => 'bar', 4 => 'feo', ), 5 => array ( 0 => 'foo', 2 => 'baz', 4 => 'feo', ), 6 => array ( 1 => 'bar', 2 => 'baz', 4 => 'feo', ), 7 => array ( 0 => 'foo', 3 => 'bee', 4 => 'feo', ), 8 => array ( 1 => 'bar', 3 => 'bee', 4 => 'feo', ), 9 => array ( 2 => 'baz', 3 => 'bee', 4 => 'feo', ), );

Рекурсия основана на том, что для получения всех комбинаций элементов k ( $count ) из n ( $arr_size ) для всех возможных вариантов наивысшего индекса на основе нуля i найдете все «подкомбинации» k-1 элементов из остальных элементов i с индексом ниже i .

Массив не array_slice d, когда он передается рекурсивным вызовам, чтобы воспользоваться механизмом «ленивой копии» PHP. Таким образом, не происходит реального копирования, так как массив не изменяется.

Сохранение индексов массивов приятно для целей отладки, но это необязательно. Удивительно, но простое удаление элементов $i => и замена массива + с помощью array_merge вызывает значительное замедление. Чтобы достичь немного лучшей скорости, чем исходная версия, вам нужно сделать следующее:

 function subcombi($arr, $arr_size, $count) { $combi_arr = array(); if ($count > 1) { for ($i = $count - 1; $i < $arr_size; $i++) { $highest_index_elem = $arr[$i]; foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { $subcombi_arr[] = $highest_index_elem; $combi_arr[] = $subcombi_arr; } } } else { for ($i = $count - 1; $i < $arr_size; $i++) { $combi_arr[] = array($arr[$i]); } } return $combi_arr; }

Что касается первой части вашего вопроса, вы должны избегать вычисления одного и того же количества более одного раза, и вам следует минимизировать вызовы функций. Например, вот так:

 function nextAssoc($sAssoc) { if (false !== ($iPos = strrpos($sAssoc, '01'))) { $sAssoc[$iPos] = '1'; $sAssoc[$iPos+1] = '0'; $tailPos = $iPos+2; $n0 = substr_count($sAssoc, '0', $tailPos); $n1 = strlen($sAssoc) - $tailPos - $n0; return substr($sAssoc, 0, $tailPos).str_repeat('0', $n0) .str_repeat('1', $n1); } return false; }

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