Как найти все возможные неповторяющиеся комбинации из слов на PHP?

Question

[Madion]

Есть массив:

array(
0 => 'один',
1 => 'два',
3 => 'три',
4 => 'четыре',
5 => 'пять',
6 => 'шесть'
);

Как можно найти все возможные неповторяющиеся комбинации из этих слов?
Т.е. например нужно получить подобное:

array(
0 => array('один', 'два', 'три', 'четыре', 'пять', 'шесть'),
1 => array('один', 'два', 'три', 'четыре', 'пять'),
3 => array('один', 'два', 'три', 'четыре'),
4 => array('один', 'два', 'три'),
5 => array('один', 'два'),
6 => array('один'),
7 => array('один', 'три', 'четыре', 'пять', 'шесть'),
8 => array('два', 'три', 'четыре', 'пять', 'шесть'),
9 => array('четыре', 'пять', 'шесть'),
//и т.д.
);

Голову сломал уже всю. Не могу сообразить.

Answer 1

[cjey]

Если порядок слов не важен, то полным перебором от 1 до 2^n (где n - кол-во слов).
Если i-й бит итератора равен 1, то i-е слово включено в комбинацию, иначе нет.

Answer 2

[egor_nullptr]

function gen_wc(array $array)
{
    yield $array;

    if (count($array) > 1) {
        for ($i = count($array) - 1; $i >= 0; --$i) {
            $sub = $array;
            unset($sub[$i]);
            foreach (gen_wc(array_values($sub)) as $a) {
                yield $a;
            };
        };
    };
};

$src = ['один', 'два', 'три', 'четыре', 'пять', 'шесть'];
$res = [];

foreach (gen_wc($src) as $a) {
    $res[crc32(implode(',', $a))] = $a;
};

print_r(array_values($res));

Comments

[drupby]

Забыли указать требуемую версию php для исполнения данного кода.

Answer 3

[egor_nullptr]

Для версий PHP до 5.5

function gen_wc(array $array)
{
    $res = [];

    for ($i = 1; $i < pow(2, count($array)); ++$i) {
        $pre = [];
        for ($j = 0; $j < count($array); ++$j) {
            if ($i & pow(2, $j)) {
                $pre[] = $array[$j];
            };
        };
        $res[] = $pre;
    };

    return $res;
};

print_r(gen_wc(['один', 'два', 'три', 'четыре', 'пять', 'шесть']));

Comments

[tummi_gummi]

Я новичок в программировании, так что задам такой вопрос: Как вы пришли к такому решению с побитовыми операциями ($i & pow(2, $j))? Может подскажите о чем почитать или в какую сторону копать, чтобы я мог и сам разобраться ?