PHP でバックトラッキングを使用してすべての文字列の順列を生成するにはどうすればよいですか?

バックトラッキング手法を使用した文字列の置換

置換とは、文字列の文字をすべての可能な順序で並べ替えることを指します。 PHP で文字列のすべての順列を生成するには、バックトラッキング アルゴリズムを使用できます。

文字列 "hey" があるとします。

1. 文字列の分割個々の文字へ:

   まず、文字列を個々の文字の配列に分割します。この場合、['h', 'e', 'y'].

2. 順列を再帰的に生成します:

   再帰を使用して、系統的に文字を交換し、可能なすべての文字を生成することで順列を生成します。

3. バックトラックして元の順序を復元:

   順列を生成した後、バックトラックして文字の元の順序を復元します。これにより、重複した順列が生成されなくなります。

コード例:

// Function to generate and print all 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 to swap the characters at positions $i and $j of $str.
function swap(&$str, $i, $j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}

$str = "hey";
permute($str, 0, strlen($str)); // Call the function.

出力:

hey
hye
ehy
eyh
yeh
yhe

このバックトラッキングアプローチにより、すべての順列が系統的に生成され、印刷されました。

以上がPHP でバックトラッキングを使用してすべての文字列の順列を生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。