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

Question

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

Учитывая массив, такой как следующий

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

Я ищу метод для генерации всех возможных комбинаций, с минимальным количеством элементов, необходимых в каждой комбинации r. (например, если r = 5, он вернет все возможные комбинации, содержащие не менее 5 элементов)

0

arrays combinations 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 из 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));

2

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

0

Источник

Accepted Answer

сочетание может быть выражено как

^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! * (n-r)!)
$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,

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

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

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

2