Python - Melacak mundur

Backtracking adalah salah satu bentuk rekursi. Tapi itu melibatkan memilih hanya opsi dari segala kemungkinan. Kami mulai dengan memilih opsi dan mundur darinya, jika kami mencapai keadaan di mana kami menyimpulkan bahwa opsi khusus ini tidak memberikan solusi yang diperlukan. Kami mengulangi langkah-langkah ini dengan menelusuri setiap opsi yang tersedia sampai kami mendapatkan solusi yang diinginkan.

Di bawah ini adalah contoh menemukan semua kemungkinan urutan pengaturan dari himpunan huruf tertentu. Saat kami memilih pasangan, kami menerapkan backtracking untuk memverifikasi apakah pasangan yang tepat tersebut telah dibuat atau belum. Jika belum dibuat, pasangan tersebut ditambahkan ke daftar jawaban jika tidak akan diabaikan.

def permute(list, s):
    if list == 1:
        return s
    else:
        return [ y + x
                 for y in permute(1, s)
                 for x in permute(list - 1, s)
                 ]

print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']