Bagaimana untuk Menjana Semua Permutasi Rentetan Menggunakan Backtracking dalam PHP?

Permutasi Rentetan menggunakan Pendekatan Menjejak Undur

Pindaan merujuk kepada menyusun semula aksara rentetan dalam semua susunan yang mungkin. Untuk menjana semua pilih atur rentetan dalam PHP, kita boleh menggunakan algoritma penjejakan ke belakang.

Andaikan kita mempunyai rentetan "hey".

1. Pisah Rentetan ke dalam Watak Individu:

   Kita mulakan dengan membelah rentetan kepada susunan aksara individu. Dalam kes ini, ['h', 'e', ​​'y'].

2. Rekursif Menjana Pilihatur:

   Menggunakan rekursi, kami menjana pilih atur dengan menukar aksara secara sistematik dan menjana semua yang mungkin gabungan.

3. Backtrack untuk Memulihkan Susunan Asal:

   Selepas menjana pilih atur, kami berundur untuk memulihkan susunan asal aksara. Ini menghalang pilih atur pendua daripada dijana.

Contoh Kod:

// 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.

Output:

hey
hye
ehy
eyh
yeh
yhe

Pendekatan menjejak ke belakang ini memastikan semua pilih atur dijana secara sistematik dan dicetak.

Atas ialah kandungan terperinci Bagaimana untuk Menjana Semua Permutasi Rentetan Menggunakan Backtracking dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!