Как генерировать перестановки ограниченных подстановок?

Question

Как генерировать перестановки ограниченных подстановок?

Это лучше всего объяснить на примере.

Допустим, у вас есть список замен, вы будете использовать PHP, потому что это моя цель:

$s = array(
'p' => array('b', 'f', 'v'),
'a' => array('e'),
't' => array('d', '')
);

Вышеуказанное означает, что «p» можно заменить на «b», «f» или «v»; ‘a’ by ‘e’; и «т» на «д» или ничего. Одновременно допускается только одна замена каждого списка.

Таким образом, генерация всех замен ‘pa’ даст: ‘ba’, ‘fa’, ‘va’, ‘pe’, ‘be’, ‘fe’, ‘ve’

И генерирует все замены «папа»: «баба», «фафа», «вава», «pepe», «bebe», «fefe», «veve»

Я могу легко перебирать верхние элементы:

// 2 ^ count($s) permutations, assuming count($s) < 31
$k = 1 << count($s);
for ($l = 0; $l < $k; $l++)
{
$x = $input;
for ($m = $l, reset($s); $m; $m >>= 1, next($s))
if ($m & 1)
// Will fail here, maybe this should be an outer loop but how?
// For now, just replacing with the first element
$x = str_replace(key($s), current($s)[0], $x);
print $x."\n";
}

Просто не могу обернуть голову, как правильно сделать внутренние замены.

Я подумал о преобразовании $ s в ряд простых замен:

$t = array(
array('p' => 'b'),
array('a' => 'e'),
array('p' => 'b', 'a' => 'e'),
array('p' => 'f'),
...

Но это все еще возвращает меня к той же проблеме.

Любой совет будет принят во внимание.

4

algorithm combinatorics php

Решение

Другие решения

Используя ответ Джейсона МакКрири как источник вдохновения, я нашел решение, которое использует минимальное количество памяти. Самый большой массив, который может получить $ X, это is (| список перестановок |), поэтому для приведенного ниже примера 3 × 1 × 2 = 6.

$input = 'pat';

$S = array(
'p' => array('b', 'f', 'v'),
'a' => array('e'),
't' => array('d', '')
);

// 2 ^ count($S) permutations, assuming count($S) < 31
for ($k = 1 << count($S), $l = 0; $l < $k; $l++)
{
$X = array($input);
for ($m = $l, reset($S); $m; $m >>= 1, next($S))
if ($m & 1)
{
$w = key($S);
$Y = $X;
$X = array();
foreach ($Y as $y)
foreach (current($S) as $s)
$X[] = str_replace($w, $s, $y);
}

foreach ($X as $x)
print $x.' ';
}
print "\n";

Выход:

pat bat fat vat pet bet fet vet pad pa bad ba fad fa vad va ped pe bed be fed fe ved ve

1

Источник

Accepted Answer

Ваше управление for Циклы в сочетании с указателями массивов слишком сложны.

Ниже приведен очень наивный подход, который, вероятно, можно было бы упростить, приняв другие стратегии, такие как рекурсия.

function generate_permutations($subtitutions, $subject) {
$permutations = array($subject);

foreach ($subtitutions as $search => $replacements) {
$new_permutations = array();

foreach ($replacements as $replacement) {
foreach ($permutations as $permutation) {
if (strpos($permutation, $search) === false) {
continue;
}

$new_permutations[] = str_replace($search, $replacement, $permutation);
}
}

$permutations = array_merge($permutations, $new_permutations);
}

return $permutations;
}

Замечания: Я проверял только на твоих примерах.

1