如何生成受限替换的排列？

Question

最好用一个例子来解释。

假设你有一个替换列表，将使用 PHP 因为那是我的目标：

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

上面的意思是'p'可以用'b'、'f'、'v'代替； 'a' 来自 'e'；和 't' 通过 'd' 或什么都没有。每个列表一次只能替换一个。

因此生成 'pa' 的所有替换将得到：'ba'、'fa'、'va'、'pe'、'be'、'fe', 've'

并生成 'papa' 的所有替换：'baba'、'fafa'、'vava'、'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'),
    ...

但这仍然让我回到同样的问题。

如有任何建议，我们将不胜感激。

Answer 1

您对 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;
}

注意：我只用你的例子测试过。

Answer 2

以 Jason McCreary 的回答为灵感，我找到了一个使用最少内存的解决方案。数组$X最大可以得到的是Π(|排列列表|)，所以对于下面的例子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

如何生成受限替换的排列？

How to generate permutations of restricted substutions?

php

algorithm

combinatorics