Bagaimanakah Saya Boleh Menjana Semua Pilihatur Tatasusunan?

Menjana Pilihatur Tatasusunan

Pilihan tatasusunan terdiri daripada susunan unik elemennya. Untuk tatasusunan elemen N, terdapat N! (N faktorial) pilih atur yang berbeza. Soalan ini bertujuan untuk menggariskan algoritma untuk menjana pilih atur ini.

Algoritma:

Pertimbangkan langkah berikut untuk menjana pilih atur tatasusunan:

1. Mulakan: Mulakan dengan mengambil elemen pertama sebagai pangsi dan meletakkannya di dalam kedudukan pertama senarai pilih atur semasa.

2. Permutasi Rekursif: Gelung melalui elemen tatasusunan yang tinggal. Tukar setiap elemen dengan pangsi, panggil fungsi pilih atur secara rekursif dengan pangsi yang dikemas kini pada kedudukan seterusnya dan tukar sekali lagi untuk memulihkan susunan asal.

   • Sebagai contoh, diberikan {3,4,6, 2,1} dengan pangsi 3, anda mengulangi {4,6,2,1}. Anda menukar 4 dengan 3, mengubah suai {4, 3, 2, 1} secara rekursif dengan pangsi 4 dan menukar kembali.
3. Penamatan: Apabila gelung mencapai elemen terakhir, senarai pilih atur semasa telah lengkap. Keluarkannya.

Pelaksanaan:

Berikut ialah pelaksanaan Python bagi algoritma di atas:

def generate_permutations(arr):
  perms = []
  _generate_permutations_helper(arr, 0, perms)
  return perms


def _generate_permutations_helper(arr, start, perms):
  if start == len(arr) - 1:
    perms.append(arr.copy())
  else:
    for i in range(start, len(arr)):
      arr[start], arr[i] = arr[i], arr[start]
      _generate_permutations_helper(arr, start + 1, perms)
      arr[start], arr[i] = arr[i], arr[start]

Contoh Penggunaan:

arr = [3, 4, 6, 2, 1]
permutations = generate_permutations(arr)
print(permutations)  # [[3, 4, 6, 2, 1], [3, 4, 2, 6, 1], ... ]

Nota: Kaedah ini boleh dioptimumkan untuk penggunaan ingatan dengan mengekalkan hanya elemen permulaan dan akhir pilih atur semasa dan membina senarai penuh hanya di berakhir, menghapuskan keperluan untuk menyimpan keseluruhan senarai pilih atur dalam ingatan.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Menjana Semua Pilihatur Tatasusunan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!