возможные комбинации массива php

26 ноября 2019, 13:00

Есть массив $test = ['a','b','c','d'];

Нужно в результате получить возможные комбинации данного массива, без павторов(a,b | b,a) в нужном порядке-

a
b
c
d
a,b
a,c
a,d
b,c
b,d
c,d
a,b,c
a,b,d
....

Не могу сообразить как это реализовать. Пробовал таким образом.

$test = ['a','b','c','d'];
$new = [];
foreach ($test as $value) {
  $new[] = $value;
  foreach ($test as $value1) {
    if($value != $value1) {
      // $new[] = $value;
      $new[] = $value.','.$value1;
    }
  }
}
function sort_value_strlen($a, $b) {
    return  mb_strlen($a) - mb_strlen($b);
}
uasort($new, 'sort_value_strlen');
print_r($new);

Но это не работает как мне нужно. Результат

Array
(
    [0] => a
    [4] => b
    [8] => c
    [12] => d
    [1] => a,b
    [2] => a,c
    [3] => a,d
    [5] => b,a
    [6] => b,c
    [7] => b,d
    [9] => c,a
    [10] => c,b
    [11] => c,d
    [13] => d,a
    [14] => d,b
    [15] => d,c
)

Он не идет больше 2 значений + есть повторы (a,b | b,a)

И возможна ли реализация без использования функций?

Answer 1

Рекурсивный алгоритм на Python:

def gen(lst, idx, result):
    if idx < 0:
        if len(result)> 0:
            print(result)
    else:
        gen(lst, idx - 1, result)
        gen(lst, idx - 1, lst[idx] + " " + result)
gen(["a","b","c"], 2, "")
a 
b 
a b 
c 
a c 
b c 
a b c

PHP:

$AA = array('a','b','c');
$BB = array();
function gen($A, $B, $idx) {
  if ($idx < 0) {
        if(sizeof($B)>0)
            print_r($B);
        return;
  }
  gen($A, $B, $idx - 1);
  array_unshift($B, $A[$idx]);
  gen($A, $B, $idx - 1);
  return;
}
gen($AA, $BB, sizeof($AA)-1);

Нерекурсивный алгоритм - проходим в цикле по числам от 1 до 2^N-1, где N - длина массива, и представляем счётчик цикла в бинарном виде. K-й бит установлен - k-й элемент массива в комбинации присутствует

L = ["a","b","c", "d"]
for i in range(1, 1<<len(L)):
    t = i
    k = 0
    result = ""
    while t > 0:
        if t & 1:
            result += L[k]
        t >>= 1
        k += 1
    print(result)
>>  a b ab c ac bc abc d ad bd abd cd acd bcd abcd

Answer 2

это задача на рекурсию

    $test = ['a','b','c','d'];
    function fillArray($incomeArr) {
      $outcomeArr = [];
      $firstLetter = $incomeArr[0];
      $incomeArr = array_slice($incomeArr, 1);
      for( $i = 0; $i < sizeof($incomeArr); $i++ ) {
        $outcomeArr[] = $firstLetter . ',' . $incomeArr[$i];
      }
      if (sizeof($incomeArr) > 1) {
         $outcomeArr = array_merge($outcomeArr, fillArray($incomeArr));
      }
      return $outcomeArr;
   }
   var_dump( fillArray($test) );

идея в том, что a конкатенируем сначала с b, c, d. Потом берем b и конкатенируем с, d. Наконец, берем с + d

Answer 3

Еще вариант с рекурсией:

<?php
function tuples(array $arr, array &$res, array $prefix = [], $offset = 0) {
    for ($i = $offset; $i < count($arr); $i++) {
        $nextPrfx = array_merge($prefix, [$arr[$i]]);
        array_push($res, $nextPrfx);
        tuples($arr, $res, $nextPrfx, ++$offset);
    }
}
$result = [];
tuples(['a', 'b', 'c', 'd'], $result);
var_dump($result);

Песочница