排除字符串的某些排列

Question

代码最初来自this thread。

如何排除某些排列？例如，如果我将 $str 设置为 "heyy" 并希望它排除其中包含 "yy"（两个 y 在一起）的所有排列，我该怎么做？

所以它会打印 "hyey"，但不会打印 "hyye"。

mb_internal_encoding('UTF-8');

// function to generate and print all N! permutations of $str. (N = strlen($str)).
function permute($str,$i,$n)
{
    if ($i == $n)
    {
        print "$str\n";
    }
    else
    {
        for ($j = $i; $j < $n; $j++)
        {
            swap($str,$i,$j);
            permute($str, $i+1, $n);
            swap($str,$i,$j); // backtrack.
        }
    }
}

function swap(&$str,$i,$j) {
    $chars = array();
    for ($p = 0; $p < mb_strlen($str); $p++) {
        $chars[] = mb_substr($str, $p, 1);
    }
    $temp = $chars[$i];
    $chars[$i] = $chars[$j];
    $chars[$j] = $temp;
    $str = implode($chars);
}

$str = "heyy";

permute($str, 0, mb_strlen($str)); // call the function.

提前致谢！

Answer 1

这是您要找的吗？

function permute($str,$i,$n)
{
    if ($i == $n && strpos($str, 'yy') === false)    // note the extra condition
    {
        print "$str\n";
    }
    else
    {
        for ($j = $i; $j < $n; $j++)
        {
            swap($str,$i,$j);
            permute($str, $i+1, $n);
            swap($str,$i,$j); // backtrack.
        }
    }
}

如果这变得更复杂，你也可以为它写一个单独的函数（这个例子是迭代一个禁止的子字符串列表）：

$skip = array('yy', 'xx');

function valid_permutation($str)
{
    global $skip;
    // check all forbidden substrings
    foreach ($skip as $substring)
        if (strpos($str, $substring) !== false)
            return false;
    // no substring matches
    return true;
}

function permute($str,$i,$n)
{
    if ($i == $n && valid_permutation($str))
    {
        print "$str\n";
    }
    else
    {
        for ($j = $i; $j < $n; $j++)
        {
            swap($str,$i,$j);
            permute($str, $i+1, $n);
            swap($str,$i,$j); // backtrack.
        }
    }
}

排除字符串的某些排列

Exclude certain permutations of a string

php

algorithm

permutation