Bagaimanakah Algoritma Knuth Boleh Menjana Permutasi Set dengan Cekap?

Menjana Pilihatur Set Dengan Cekap

Dalam masalah menjana pilih atur set, mencari algoritma yang paling cekap adalah penting. Kod yang disediakan mencapai kecekapan tinggi, tetapi untuk pengiraan yang menuntut, pengoptimuman diperlukan.

Penyelesaian Cadangan: Algoritma Knuth

Algoritma Knuth menawarkan pendekatan yang sangat cekap untuk menjana pilih atur. Ia beroperasi dalam empat langkah utama:

1. Kenalpasti Indeks Terbesar j: Tentukan indeks j di mana pilih atur semasa tidak dalam tertib menaik, dengan elemen pada indeks j dan j 1 tidak teratur.
2. Cari Elemen Seterusnya yang Lebih Besar: Kenal pasti indeks l di mana unsur pada indeks j adalah lebih kecil daripada unsur pada indeks l, dengan indeks j < indeks l.
3. Elemen Tukar: Tukarkan elemen pada indeks j dan l.
4. Terbalikkan Ekor: Balikkan susunan unsur dari indeks j 1 kepada tamat.

Pelaksanaan

Kod C# yang disediakan melaksanakan algoritma Knuth diberikan di bawah:

private static bool NextPermutation(int[] numList)
{
  // 1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
  var largestIndex = -1;
  for (var i = numList.Length - 2; i >= 0; i--)
  {
    if (numList[i] < numList[i + 1])
    {
      largestIndex = i;
      break;
    }
  }

  // If no such index exists, return false indicating the last permutation.
  if (largestIndex < 0) return false;

  // 2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
  var largestIndex2 = -1;
  for (var i = numList.Length - 1; i >= 0; i--)
  {
    if (numList[largestIndex] < numList[i])
    {
      largestIndex2 = i;
      break;
    }
  }

  // 3. Swap a[j] with a[l].
  var tmp = numList[largestIndex];
  numList[largestIndex] = numList[largestIndex2];
  numList[largestIndex2] = tmp;

  // 4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
  for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--)
  {
    tmp = numList[i];
    numList[i] = numList[j];
    numList[j] = tmp;
  }

  return true;
}
Pertimbangan Pengoptimuman Kelajuan 
Untuk pengoptimuman kelajuan selanjutnya, pertimbangkan berikut:


Pembukaan Kod: Menyahgelung gelung terbalik dalam langkah 4 boleh meningkatkan prestasi sedikit.

Cache Nilai: Cache yang kerap diakses nilai, seperti panjang tatasusunan, untuk meminimumkan lebihan pengiraan.

Fungsi Inlining: Sebaris fungsi NextPermutation untuk menghapuskan overhed panggilan fungsi.

Elakkan Casting yang Tidak Diperlukan: Pastikan nilai perantaraan adalah daripada jenis data yang sesuai untuk mengelakkan operasi penghantaran.


Atas ialah kandungan terperinci Bagaimanakah Algoritma Knuth Boleh Menjana Permutasi Set dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!