Составить алгоритм перебора вариантов с весом?

Question

[MasterCopipaster]

Подскажите чет туплю не знаю как сделать, есть такой массив.

<?php
$a = [
    0 => 'a',
    1 => 'b',
    2 => 'c'
];

Мне надо перебрать все возможные варианты, но с сохранением веса, в качестве веса индекс массива.
Сейчас объясню подробнее: тоесть элемент с индексом 0 не может идти за индексом 1 а индекс 1 не может быть перед нулем.
Для текущего массива получатся такие варианты:

a
b
c
ab
ac
bc
abc

Обратите внимание что не могут получится варианты типа acb потому что индекс b меньше индекса с
Надеюсь понятно объяснил, алгоритм перебора всех возможных вариантов тут не подходит. А мне чет в голову не приходит как это написать адекватно.

Comments

[Одиночка Айс]

'bc' попадает сюда или нет?

[MasterCopipaster]

Одиночка Айс, да да поподает - спасибо я не заметил когда писал вопрос

[Adamos]

А вес-то тут при чем? Это всего лишь порядок.
После каждой буквы есть ряд вариантов продолжения: либо строка заканчивается, либо берется одна из букв, следующих за ней. Заворачиваете эту логику в рекурсию - получаете все варианты.

Answer 1

[Дмитрий]

Если перестановки не нужны, то все просто. Каждый элемент либо входит в следующий вариант, либо нет. Соответственно делаете цикл 1 до pow(2, count($arr)). Преобразовываете каждое число цикла в двоичное встроенной функцией decbin, переворачиваете результат, и по нему составляете новый вариант - если 1 на соответствующем месте возвращенной decbin строки, то включаете элемент, если 0, то исключаете.

$arr = [0 => 'a', 1 => 'b', 2 => 'c'];
$res = [];

for ($i = 1; $i < pow(2, count($arr)); $i++ ) {
    $bin = decbin($i);
    $case = "";
    foreach(str_split(strrev($bin)) as $ind => $symb) if ($symb == "1") $case .= $arr[$ind];
    $res[] = $case;
}

echo implode(", ", $res); // a, b, ab, c, ac, bc, abc