Все комбинации элементов r из заданного массива php

Комбинация может быть выражена как

ⁿ C _r = n! / (r! – (n – r)!)

Сначала мы определяем $n как число элементов в массиве. И $r – минимальное количество элементов в каждой комбинации.

 $a = ['1', '2', '3', '4', '5', '6', '7']; // the array of elements we are interested in // Determine the `n` and `r` in nCr = n! / (r! * (nr)!) $r = 5; $n = count($a); 

Затем мы определяем $max как максимальное число, которое может быть представлено двоичными цифрами $n . То есть, если $n = 3 , то $max = (111) ₂ = 7 . Для этого сначала создадим пустую строку $maxBinary и добавим к ней $n число 1 с. Затем мы преобразуем его в десятичную и сохраним в $max .

 $maxBinary = ""; for ($i = 0; $i < $n; $i++) { $maxBinary .= "1"; } $max = bindec($maxBinary); // convert it into a decimal value, so that we can use it in the following for loop 

Затем мы перечислим каждое двоичное число от 0 до $max и сохраним те, у которых больше, чем $r число в 1 с.

 $allBinary = array(); // the array of binary numbers for ($i = 0; $i <= $max; $i++) { if (substr_count(decbin($i), "1") >= $r) // we count the number of ones to determine if they are >= $r { // we make the length of the binary numbers equal to the number of elements in the array, // so that it is easy to select elements from the array, based on which of the digits are 1. // we do this by padding zeros to the left. $temp = str_pad(decbin($i), $n, "0", STR_PAD_LEFT); $allBinary[] = $temp; } } 

Затем мы используем тот же трюк, что и выше, для выбора элементов для нашей комбинации. Я считаю, что комментарии достаточно объясняют.

 $combs = array(); // the array for all the combinations. $row = array(); // the array of binary digits in one element of the $allBinary array. foreach ($allBinary as $key => $one) { $combs[$key] = ""; $row = str_split($one); // we store the digits of the binary number individually foreach ($row as $indx => $digit) { if ($digit == '1') // if the digit is 1, then the corresponding element in the array is part of this combination. { $combs[$key] .= $a[$indx]; // add the array element at the corresponding index to the combination } } } 

И это все. Вы сделали!

Теперь, если у вас есть что-то вроде

 echo count($combs); 

то это даст вам 29 .

Дополнительные замечания:

Я прочитал это только после того, как увидел ваш вопрос, и как новичок я нашел это полезным:

• Википедия – http://en.wikipedia.org/wiki/Combination
• Рекурсия PHP для получения всех возможностей строк
• Алгоритм возврата всех комбинаций k элементов из n

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

• http://php.net/manual/en/function.decbin.php
• http://php.net/manual/en/function.bindec.php
• http://php.net/manual/en/function.str-pad.php

Комбинации k из n элементов могут быть определены рекурсивно, используя следующую функцию:

 function combinationsOf($k, $xs){ if ($k === 0) return array(array()); if (count($xs) === 0) return array(); $x = $xs[0]; $xs1 = array_slice($xs,1,count($xs)-1); $res1 = combinationsOf($k-1,$xs1); for ($i = 0; $i < count($res1); $i++) { array_splice($res1[$i], 0, 0, $x); } $res2 = combinationsOf($k,$xs1); return array_merge($res1, $res2); } 

Вышеизложенное основано на рекурсивном определении, что для выбора k out n элементов можно зафиксировать элемент x в списке, и есть комбинации C(k-1, xs\{x}) которые содержат x (т.е. res1 ), и C(k,xs\{xs}) которые не содержат x (т.е. res2 в коде).

Полный пример:

 $array = array('1', '2', '3', '4', '5', '6', '7'); function combinationsOf($k, $xs){ if ($k === 0) return array(array()); if (count($xs) === 0) return array(); $x = $xs[0]; $xs1 = array_slice($xs,1,count($xs)-1); $res1 = combinationsOf($k-1,$xs1); for ($i = 0; $i < count($res1); $i++) { array_splice($res1[$i], 0, 0, $x); } $res2 = combinationsOf($k,$xs1); return array_merge($res1, $res2); } print_r ($array); print_r(combinationsOf(5,$array)); //print_r(combinationsOf(5,$array)+combinationsOf(6,$array)+combinationsOf(7,$array)); 

  function arrToBit(Array $element) { $bit = ''; foreach ($element as $e) { $bit .= '1'; } $length = count($element); $num = bindec($bit); $back = []; while ($num) { $back[] = str_pad(decbin($num), $length, '0', STR_PAD_LEFT); $num--; } //$back[] = str_pad(decbin(0), $length, '0', STR_PAD_LEFT); return $back; } function bitToArr(Array $element, $bit) { $num = count($element); $back = []; for ($i = 0; $i < $num; $i++) { if (substr($bit, $i, 1) == '1') { $back[] = $element[$i]; } } return $back; } $tags = ['a', 'b', 'c']; $bits = arrToBit($tags); $combination = []; foreach ($bits as $b) { $combination[] = bitToArr($tags, $b); } var_dump($combination);