0

Есть необходимость получить все возможные сочетания элементов одномерного массива.

$input = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

function getCombinations(array $data): array
{
    $results = array(array());
    foreach ($data as $element) {
        foreach ($results as $combination) {
            array_push($results, array_merge(array($element), $combination));
        }
    }

    return $results;
}

$combinations = getCombinations($input);
print_r($combinations);

Код есть в песочнице - тут

Однако при выполнении кода получаю ошибку о перезаполнении памяти

Allowed memory size of ХХХХХХХХХ bytes exhausted (tried to allocate ХХХХХХХ bytes)

Как можно задать глубину поиска комбинаций? Например, меня интересуют только парные комбинации (1+1). Можно ли как-то посчитать количество циклов, на котором нужно остановиться, зная количество элементов в исходном массиве и глубину?

Вывод:

Array
(
    [0] => Array
        (
        )

    [1] => Array
        (
            [0] => A
        )

    [2] => Array
        (
            [0] => B
        )

    [3] => Array
        (
            [0] => B
            [1] => A
        )

    [4] => Array
        (
            [0] => C
        )

    [5] => Array
        (
            [0] => C
            [1] => A
        )

    [6] => Array
        (
            [0] => C
            [1] => B
        )

    [7] => Array
        (
            [0] => C
            [1] => B
            [2] => A
        )

)
10
  • Вы получаете все подмножества из алфавита и у вас получается массив размером 2^26. Конечно память перезаполнена. Вы хотите вывести все сочетания элементов длины 2?
    – becouse
    Commented 13 дек. 2019 в 16:18
  • @becouse 2,3,4. 5 - вряд ли. На самом деле ещё больше, т.к. у меня элементов не 26, а около 35. Алфавит для примера.
    – Teretto
    Commented 13 дек. 2019 в 17:16
  • Вам их нужно сохранить или вывести на экран? Сохранить для размера больше 20 вы сможете только в файл. В лексикографическом порядке?
    – becouse
    Commented 14 дек. 2019 в 8:00
  • @becouse удобно в виде многомерного массива (как у меня в моем коде) - внтури массима подмассивы, в которых каждое значение - одно из сочетаний. Дополнил ответ. Важно понимать сочетние C-A и A-C, например, это одно и то же.
    – Teretto
    Commented 14 дек. 2019 в 8:37
  • Смотрите. Если взять 17 букв, то массив в памяти занимает 15Мб. Если вы возьмете еще 9 (для английского), то получите 512*15=7680Мб, т.е. 8 гигабайт, что конечно в память не влезет. Возможно вам подойдет решение с поиском сочетаний нужной длины. Прилагаю.
    – becouse
    Commented 14 дек. 2019 в 9:21

1 ответ 1

2

Вот программа, которая получает все сочетания элементов массива от длины $first, до длины $last.

$input = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];



function getCombinations($array, $data, $start, $end, $index, &$result) {

    if ($index==sizeof($data)) {
        $s="";
        foreach ($data as $elem){
            $s=$s.$elem;
        }
        array_push($result, $s);
    }
    else{
      if ($start<=$end){
          $data[$index]=$array[$start];

          getCombinations($array,$data,$start+1,$end,$index+1,$result);
          getCombinations($array,$data,$start+1,$end,$index,$result);
      }    
    }


    }
function getCombinationsOfSize($array, $size){
 $data=array_fill(0, $size, "");
 $result=array();
 getCombinations($array,$data,0,sizeof($array)-1,0,$result);
 return $result;    
}

function getAllCombinationsRange($array,$first,$last){
 $result=array();
  for ($k=$first;$k<=$last;$k++){
     $result=array_merge($result,getCombinationsOfSize($array, $k));
  }    
 return $result;
}



print_r(getAllCombinationsRange($input,1,5));
1
  • прошу прощения. нет возможности сейчас посмотреть. Чуть позже.
    – Teretto
    Commented 15 дек. 2019 в 13:15

Ваш ответ

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.