Bagaimana untuk menghasilkan gabungan permutasi yang tidak diulangi dan tidak bersebelahan dengan watak -watak yang sama berdasarkan set aksara dan bilangan lapisan yang diberikan?

Set dan Lapisan Karakter: Menjana permutasi yang unik

Artikel ini meneroka cara menjana gabungan permutasi tanpa pendua dan tanpa aksara identik berturut -turut berdasarkan set aksara dan bilangan lapisan yang diberikan. Sebagai contoh, set aksara {a, b}, kombinasi permutasi tiga lapisan harus mengandungi AAB, ABA, ABB, BAA, BAB, BBA, dan lain-lain, tetapi bukan AAA, BBB dan watak berulang berturut-turut. Ini memerlukan algoritma untuk mengendalikan deduplikasi dan mengelakkan pertindihan aksara yang berterusan.

Cabaran teras adalah untuk merancang algoritma yang boleh menyesuaikan diri dengan set dan lapisan aksara yang berbeza dan menjana permutasi dengan cekap yang memenuhi kriteria. Artikel ini akan memperkenalkan dua kaedah: kaedah penggantian digital dan kaedah backtracking.

Kaedah 1: Kaedah Penggantian Digital

Kaedah ini merawat kombinasi permutasi sebagai nombor M-digit (M ialah saiz set aksara). Sebagai contoh, set aksara {a, b} sepadan dengan nombor binari. 00 mewakili AA, 01 mewakili AB, dan sebagainya. Dengan melintasi semua nombor M-angka dan menggantikan watak, anda boleh mendapatkan semua kombinasi yang mungkin. Untuk mengelakkan aksara yang sama, nombor m-digit tertentu perlu dikecualikan, seperti nombor di mana semua bit adalah sama.

Contoh kod python:

 def solve_digit (arr, m, allow_all_same = false):
    res, cur = [], [''] * m
    n = len (arr)
    all_same_num = 0
    untuk _ dalam julat (m):
        all_same_num = all_same_num * n 1
    untuk D dalam julat (n ** m):
        jika membenarkan_all_same atau d % all_same_num! = 0:
            untuk saya dalam julat (m -1, -1, -1):
                cur [i] = arr [d % n]
                d // = n
            res.Append (''. Sertai (CUR))
    Kembali res

cetak (solve_digit ('ab', 2)) # ['ab', 'ba']
cetak (solve_digit ('ab', 2, true)) # ['aa', 'ab', 'ba', 'bb']
cetak (solve_digit ('ab', 3)) # ['aab', 'aba', 'abb', 'baa', 'bab', 'bba']
cetak (solve_digit ('abc', 2)) # ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']

Kaedah 2: Kaedah Backtracking

Backtrace adalah algoritma rekursif yang mendapati hasil dengan mencuba semua kombinasi yang mungkin. Tambah watak pada kombinasi semasa pada setiap langkah dan rekursif menghasilkan kombinasi yang lebih lama. Pada masa yang sama, adalah perlu untuk mengesan sama ada watak -watak terdahulu adalah sama untuk mengelakkan kombinasi yang tidak memenuhi syarat -syarat.

Contoh kod python:

 def solve_backtracking (arr, m, allow_all_same = false):
    res, cur = [], [''] * m

    def dfs (i, sama):
        jika i == m:
            Sekiranya tidak sama:
                res.Append (''. Sertai (CUR))
            Kembali
        untuk arr:
            cur [i] = a
            DFS (I 1, sama dan A == Cur [i - 1])

    untuk arr:
        cur [0] = a
        dfs (1, tidak membenarkan_all_same)

    Kembali res

cetak (solve_backtracking ('ab', 2)) # ['ab', 'ba']
cetak (solve_backtracking ('ab', 2, true)) # ['aa', 'ab', 'ba', 'bb']
cetak (solve_backtracking ('ab', 3)) # ['aab', 'aba', 'abb', 'baa', 'bab', 'bba']
cetak (solve_backtracking ('abc', 2)) # ['ab', 'ac', 'ba', 'bc', 'ca', 'cb']

Kedua -dua kaedah dapat menyelesaikan masalah ini. Kaedah penggantian digital lebih efisien dan kaedah mundur lebih mudah difahami. Kaedah yang mana untuk dipilih bergantung pada senario aplikasi tertentu dan keutamaan peribadi.

Atas ialah kandungan terperinci Bagaimana untuk menghasilkan gabungan permutasi yang tidak diulangi dan tidak bersebelahan dengan watak -watak yang sama berdasarkan set aksara dan bilangan lapisan yang diberikan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!