Как генерировать перестановки ограниченных подстановок?
Это лучше всего объяснить на примере.
Допустим, у вас есть список замен, вы будете использовать 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'),
...
Но это все еще возвращает меня к той же проблеме.
Любой совет будет принят во внимание.
Решение
Ваше управление 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;
}
Замечания: Я проверял только на твоих примерах.
Другие решения
Используя ответ Джейсона МакКрири как источник вдохновения, я нашел решение, которое использует минимальное количество памяти. Самый большой массив, который может получить $ 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