Как получить всевозможные комбинации массива PHP?

Question

[Александр Панков]

Есть массив [1, 2, 3, 4, 5]
Нужно написать такую функцию на PHP, чтобы она получала всевозможные комбинации массива без учета перестановок, те комбинация "41" и "14" считалась как одно и то же и в результирующий массив не входила.

Те ответ должен быть такой (набор массивов)

• 1
  
• 1 2
  
• 1 2 3
  
• 1 2 3 4
  
• 1 2 3 4 5
  
• 1 3
  
• 1 3 4
  
• 1 3 4 5
  
• 1 4
  
• 1 4 5
  
• 1 5
  
• 2
  
• 2 3
  
• 2 3 4
  
• 2 3 4 5
  
• 2 4
  
• 2 4 5
  
• 2 5
  
• 3
  
• 3 4
  
• 3 4 5
  
• 3 5
  
• 4
  
• 4 5
  

Я постарался написать так, но не работает

function getPermutations(array $values)
{
    $temp[] = $values;
    foreach ($values as $i) {
        foreach ($values as $j) {
            $temp[] = array_unique([$i, $j]);
        }
    }
    foreach ($temp as $i => $k) {
        sort($k);
        $temp[$i] = $k;
    }
    $array = array_unique($temp, SORT_REGULAR);
    return array_values($array);
}

Comments

[Adamos]

Нужно написать такую функцию на PHP, чтобы она получала всевозможные комбинации массива, без учета перестановок, те 41 и 14 это считалось как одно и то же и в результирующий массив не входила

Может, сначала доучить тему "сложносочиненные предложения"? Вы даже задачу умудрились описать так, как будто ее Чужой пересказал Хищнику.

Answer 1

[Wataru]

Подсчитайте руками, сколько комбинаций для массива из 1,2,3,4 элементов? ответ будет 1,3,7,15 - степени двойки минус один. Подумайте, откуда это берется? Каждый элемент может или быть в ответе, или нет. 2 варианта. Премножаем все, получаем степень двойки. Но это учитывает варинат пустого ответа, поэтому один надо вычесть.

Тут есть 2 подхода - рекурсивная функция перебора, которая или берет или пропускает текущий элемент. В конце, если хоть один элемент был взят - выводит текущий массив.

Второй подход - перебирать битовую маску. Каждое число от 1 до 2^n будет в двоичной системе числения представлять какой-то вариант выбора разрядов. Поэтому можно прогнать цикл от 1 до 2^n, потом посмотреть на биты этого числа и брать соотвествтующие числа из массива.