Bagaimanakah saya boleh menjana semua kemungkinan kombinasi saiz tertentu daripada set aksara tertentu menggunakan pendekatan rekursif?

Algoritma untuk Menjana Gabungan daripada Set Tunggal

Tugas di tangan adalah untuk merangka algoritma yang boleh menjana semua kemungkinan kombinasi yang ditentukan saiz daripada set aksara yang diberikan, berfungsi dengan berkesan sebagai algoritma pensampelan. Tidak seperti algoritma pilih atur, teknik ini membenarkan pengulangan aksara dalam kombinasi.

Pendekatan Rekursif

Untuk menangani masalah ini, kami menggunakan fungsi rekursif yang mengambil sebagai input set aksara, saiz gabungan yang diingini dan tatasusunan gabungan perantaraan (dimulakan sebagai set asal untuk lelaran awal).

1. Kes Asas: Jika saiznya ialah 1, fungsi mengembalikan set gabungan semasa.

2. Langkah Rekursif:

   • Buat tatasusunan kosong untuk set gabungan baharu.
   • Untuk setiap gabungan dan aksara sedia ada dalam set, gabungkan dan tambahkannya pada tatasusunan baharu.
   • Imbas kembali fungsi yang sama dengan set aksara yang dikemas kini (tidak berubah), saiz yang dikecilkan dan set gabungan baharu sebagai input.

Contoh Pelaksanaan

Kod PHP berikut menggambarkan pelaksanaan algoritma rekursif:

function sampling($chars, $size, $combinations = array()) {

    // Base case
    if (empty($combinations)) {
        $combinations = $chars;
    }

    // Size 1 case
    if ($size == 1) {
        return $combinations;
    }

    // Initialize new combinations array
    $new_combinations = array();

    // Generate new combinations by concatenating existing and new characters
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    // Recursive call
    return sampling($chars, $size - 1, $new_combinations);

}

Contoh Penggunaan

Untuk menunjukkan kefungsian, mari kita pertimbangkan set aksara:

$chars = array('a', 'b', 'c');

Menggunakan algoritma, kita boleh menjana semua kombinasi saiz 2 :

$output = sampling($chars, 2);
var_dump($output);

Output:

array(9) {
  [0]=>
  string(2) "aa"
  [1]=>
  string(2) "ab"
  [2]=>
  string(2) "ac"
  [3]=>
  string(2) "ba"
  [4]=>
  string(2) "bb"
  [5]=>
  string(2) "bc"
  [6]=>
  string(2) "ca"
  [7]=>
  string(2) "cb"
  [8]=>
  string(2) "cc"
}

Atas ialah kandungan terperinci Bagaimanakah saya boleh menjana semua kemungkinan kombinasi saiz tertentu daripada set aksara tertentu menggunakan pendekatan rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!