Получите все уникальные комбинации для x количества мест с одинаковыми параметрами каждый раз

Question

Я не уверен насчет правильной терминологии, но мне нужна программа, которая дает все уникальные комбинации для фиксированного количества опций с переменным количеством точек, например:

options: "a", "b", "c"  
max spots: 3

output:
a 
a a 
a b
a c
a a a 
a a b
a b b 
a a c
a c c 
a b c
b
b b 
b c
b b b
b b c 
b c c 
c
c c 
c c c 

Я в настоящее время У меня есть немного кода, но я не знаю, как сделать его масштабируемым для большего количества мест. Обычно он помещает комбинацию в массив, а не печатает ее, и этот массив позже используется для других вычислений.

$options = array("a", "b", "c");

for ($x = 0; $x < 3; $x++) {
    print "$options[$x]\n";
    for ($y = $x; $y < 3; $y++) {
        print "$options[$x] $options[$y]\n";
        for ($z = $y; $z < 3; $z++) {
            print "$options[$x] $options[$y] $options[$z]\n";
        }
    }
}

Другая моя несколько успешная попытка заключалась в помещении сгенерированной комбинации в массив, сортировке этого массива, превращении массива в строку и проверке, существует ли строка в массиве со всеми принятыми строками комбинации. Это кажется ужасно неэффективным, и я надеялся, что есть лучший способ. Я бы предпочел не использовать внешние функции, потому что я хочу стать лучше в PHP и циклах и тому подобное.

Answer 1

Вот реализация генератора, которая не требует ссылок.

function permutations($alphabet, $max, $prefix = '') {
    $alphabetRemaining = $alphabet;

    if ($prefix) {
        yield $prefix;
    }

    if ($max <= 0) {
        return;
    }

    foreach ($alphabet as $alpha) {
        yield from permutations($alphabetRemaining, $max - 1, $prefix . $alpha);
        array_shift($alphabetRemaining);
    }
}

foreach (permutations(["a", "b", "c"], 3) as $perm) {
    echo "$perm\n";
}

Вывод

a
aa
aaa
aab
aac
ab
abb
abc
ac
acc
b
bb
bbb
bbc
bc
bcc
c
cc
ccc

Если вы хотите все возможные перестановки , вы должны использовать это вместо .

function permutations($alphabet, $max, $prefix = '') {
    $alphabetRemaining = $alphabet;

    if ($prefix) {
        yield $prefix;
    }

    if ($max <= 0) {
        return;
    }

    foreach ($alphabet as $alpha) {
        yield from permutations($alphabetRemaining, $max - 1, $prefix . $alpha);
    }
}

foreach (permutations(["a", "b", "c"], 3) as $perm) {
    echo "$perm\n";
}

Выход

a
aa
aaa
aab
aac
ab
aba
abb
abc
ac
aca
acb
acc
b
ba
baa
bab
bac
bb
bba
bbb
bbc
bc
bca
bcb
bcc
c
ca
caa
cab
cac
cb
cba
cbb
cbc
cc
cca
ccb
ccc

Answer 2

Вы можете попасть туда с помощью рекурсии (предполагается, что в массиве опций у вас есть только уникальные символы, если бы вам не пришлось это делать сначала):

function printCombinations(&$options, $max, $index = 0, $prefix = '') {
    if ($prefix)
        print "$prefix\n";
    if ($max <= 0)
        return;
    for ($i = $index; $i < count($options); $i++) {
        printCombinations($options, $max - 1, $i, $prefix . ' ' . $options[$i]);
    }
}

Вы бы назвали это так: printCombinations(['a', 'b', 'c'], 3);. Поскольку мы как бы перечисляем комбинации, мы не получаем дубликатов (если только у $ options нет дубликатов).

Это даст вам a b, но не b a, поэтому элементы должны быть взяты в порядке Похоже, это то, что указано в вашем списке. Вызов выше должен дать вам именно ваш список (в несколько ином порядке).