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

Question

SO,

Проблема

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

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

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

-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 -> [bar, baz, bee] 
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; 
} 

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

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

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

Вопрос

Мой вопрос о двух точках:

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

Answer 1

Прошу прощения за то, что вы не предоставляете 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.

Answer 2

Вот рекурсивное решение:

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

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