Получить все уникальные комбинации из массива для заданного количества элементов
Я хотел получить способ получить все комбинации для всех заданных чисел с заданной длиной массива.
В моем проекте размер массива обычно равен 7. Поэтому я пишу такой тестовый код, чтобы посмотреть, смогу ли я получить все необходимые комбинации. Важной частью является то, что каждый массив результатов должен быть уникальным, а максимальный размер массива должен быть 7.
<?php
$numbers = [1, 2, 3, 4, 5, 6, 7];
$arraysize = 7;
$subset = [];
$count = count($numbers);
for ($i = 0; $i < $count; $i++) {
$subset[] = $numbers[$i];
}
for ($i=0; $i < $count; $i++) {
for ($j=$i; $j < $count; $j++) {
$subset[] = $numbers[$i] . $numbers[$j];
}
}
for ($i=0; $i < $count; $i++) {
for ($j=$i; $j < $count; $j++) {
for ($k=$j; $k < $count; $k++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k];
}
}
}
for ($i=0; $i < $count; $i++) {
for ($j=$i; $j < $count; $j++) {
for ($k=$j; $k < $count; $k++) {
for ($l=$k; $l < $count; $l++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l];
}
}
}
}
for ($i=0; $i < $count; $i++) {
for ($j=$i; $j < $count; $j++) {
for ($k=$j; $k < $count; $k++) {
for ($l=$k; $l < $count; $l++) {
for ($m=$l; $m < $count; $m++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l] . $numbers[$m];
}
}
}
}
}
for ($i=0; $i < $count; $i++) {
for ($j=$i; $j < $count; $j++) {
for ($k=$j; $k < $count; $k++) {
for ($l=$k; $l < $count; $l++) {
for ($m=$l; $m < $count; $m++) {
for ($n=$m; $n < $count; $n++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l] . $numbers[$m] . $numbers[$n];
}
}
}
}
}
}
for ($i=0; $i < $count; $i++) {
for ($j=$i; $j < $count; $j++) {
for ($k=$j; $k < $count; $k++) {
for ($l=$k; $l < $count; $l++) {
for ($m=$l; $m < $count; $m++) {
for ($n=$m; $n < $count; $n++) {
for ($o=$n; $o < $count; $o++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l] . $numbers[$m] . $numbers[$n] . $numbers[$o];
}
}
}
}
}
}
}
echo "<pre>";
print_r($subset);
echo "</pre>";
?>
Когда я запускаю этот код, я получаю комбинации как я хотел (я делаю комбинации в виде строки, чтобы видеть результаты ясно, но обычно каждый элемент результата в $subset массив должен быть массивом)
С помощью этого кода я могу получить все уникальные комбинации.
Но, как вы можете видеть, этот код ужасен. Я пытался сделать это рекурсивной функцией, но мне не удалось. Может ли кто-нибудь указать мне правильное направление, чтобы получить такие же результаты, как этот? (каждый предмет в $subset массив обычно должен быть массивом, который содержит цифры)
Решение
Вы можете упростить эту логику (и сделать код менее уродливым), не прибегая к рекурсии, используя:
for ($i = 0; $i < $count; $i++) {
$subset[] = $numbers[$i];
for ($j=$i; $j < $count; $j++) {
$subset[] = $numbers[$i] . $numbers[$j];
for ($k=$j; $k < $count; $k++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k];
for ($l=$k; $l < $count; $l++) {
$subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l];
}
}
}
}
Другие решения
следующее будет работать во всех случаях, даже если в вашем массиве есть повторяющиеся числа
$array = array(1,2,3,4,5,6,7,8,9,10,11,12,13,14);
sort($array); //in case it 's not sorted
$array = array_slice($array,-7);
$num = count($array );
$total = pow(2, $num);
$result= array();
$element='';
for ($i = 0; $i < $total; $i++)
{
for ($j = 0; $j < $num; $j++)
{
if (pow(2, $j) & $i)
{
$element=$element.$array [$j];
}
}
$result[]=$element;
$element='';
}
print_r($result);
Эта реализация возвращает все комбинации всех элементов (77 = 823542 комбинации из 7 предметов):
function combine_all(array $numbers) {
$count = count($numbers);
$result = array_map('strval', $numbers);
for($i = 1; $i < $count; ++$i) {
$combinations = array_slice($result, pow($count, $i-1));
foreach($numbers as $number) {
foreach($combinations as $combination) {
$result[] = $number . ',' . $combination;
}
}
}
return $result;
}
При использовании print_r для вывода данных, он может работать очень медленно:
$array = array_fill(0, pow(7,7), '');
$t = microtime(true);
echo '<pre>';
print_r($array);
echo '</pre>';
echo microtime(true) - $t;
// 0.75329303741455$t = microtime(true);
echo '<pre>';
print_r( combine_all(array(1,2,3,4,5,6,7)) );
echo '</pre>';
echo microtime(true) - $t;
// 1.7037351131439$t = microtime(true);
combine_all(array(1,2,3,4,5,6,7));
echo microtime(true) - $t;
//0.75869607925415
Чтобы ограничить количество предметов, используйте array_slice функция:
combine_all(array_slice($numbers, 0, 7));
Если вы действительно хотите рекурсивную функцию, вы можете сделать что-то вроде этого:
function combine_all(array $numbers, $cnt=null, $baseCombination=null) {
if( $baseCombination === null ) {
$cnt = count($numbers);
}
if( $cnt > 0 ) {
$result = array();
foreach($numbers as $number) {
$combination = $number . ',' . $baseCombination;
$result[] = $combination;
$result = array_merge($result, combine_all($numbers, $cnt-1, $combination));
}
return $result;
}
return array();
}
Наконец-то я нашел способ добавить рекурсивную функцию для создания уникальных комбинаций из заданных чисел:
$numbers = [1, 2, 3, 4, 5, 6, 7];
function subsetSumRecursive($numbers, $arraySize, $level = 1, $i = 0, $addThis = [])
{
// If this is the last layer, use a different method to pass the number.
if ($level == $arraySize) {
$result = [];
for (; $i < count($numbers); $i++) {
$result[] = array_merge($addThis, array($numbers[$i]));
}
return $result;
}
$result = [];
$nextLevel = $level + 1;
for (; $i < count($numbers); $i++) {
// Add the data given from upper level to current iterated number and pass
// the new data to a deeper level.
$newAdd = array_merge($addThis, array($numbers[$i]));
$temp = subsetSumRecursive($numbers, $arraySize, $nextLevel, $i, $newAdd);
$result = array_merge($result, $temp);
}
return $result;
}
echo "<pre>";
print_r(subsetSumRecursive($numbers, 7));
echo "</pre>";