Secara konseptual saya mencoba membangun susunan permutasi yang mungkin dari kumpulan 10 nilai ex.[0-9] di mana Anda memiliki pilihan 3 pada setiap elemen berdasarkan peringkat. Jadi katakanlah elemen pertama yang dipilih adalah 0 maka kumpulan nilai berikutnya yang mungkin untuk dipilih adalah 1,2,3. Jika tiga kemudian dipilih [0,3] maka pilihan berikutnya akan memiliki kumpulan [1,2,4] dan seterusnya. Saya ingin ini untuk 5 level tetapi tentu saja mencoba mengkodekan solusi yang sewenang-wenang dengan jumlah level, nilai, dan kondisi pembatas. Tujuannya adalah agar semua permutasi dikembalikan dalam array bersarang. Saya akan menggunakan array ini untuk membangun DataFrame untuk visualisasi.

Upaya pertama saya adalah membuat semua permutasi untuk 10 nilai menggunakan itertools permutations lalu hapus dari itu yang tidak sesuai dengan kondisi saya berdasarkan jarak dari entri sebelumnya. Ini tampaknya tidak efisien, tetapi saya juga kesulitan menentukan kondisi untuk melepasnya.

Edit: Saya tidak menentukan dengan benar bahwa proses pemilihan selalu dimulai dengan [0,1,2] sebagai pilihan pertama. Pilihan tambahan ditambahkan di setiap level sesuai dengan peringkat berikutnya yang tersedia hingga peringkat maksimal katakanlah 10. Jadi jika 2 dipilih pada level pertama, maka '3' masuk untuk menggantikannya. [0,1,3] adalah pilihan berikutnya yang tersedia. Jika 1 kemudian dipilih, Anda memiliki [0,3,4] di level berikutnya untuk dipilih. Ini berlanjut sampai Anda mencapai panjang maksimal katakanlah 5 pilihan yang dibuat.

0
JB5 6 Maret 2020, 20:30

1 menjawab

Jawaban Terbaik

Oke, jika saya mengerti dengan benar, ini adalah proses yang Anda gambarkan:

Reserve: [3, 4, 5, 6, 7, 8, 9]
Pool: [0, 1, 2]
Chosen: []

Selama kita belum memiliki 5 item Chosen, hapus item apa pun dari Pool dan tambahkan ke urutan yang dipilih. Kemudian hapus item pertama dari Reserve dan tambahkan ke kumpulan. Ulangi seperlunya.

Saya akan menggunakan P untuk ukuran kolam dan N untuk panjang urutan yang dipilih. Jadi P=3 dan N=5 dalam contoh ini.

Saya masih agak tidak yakin apakah ini proses yang ingin Anda gambarkan, karena tampaknya 7, 8, dan 9 tidak akan pernah muncul dalam urutan yang dipilih, tetapi Anda mengatakan bahwa Anda mencoba menemukan solusi umum, jadi saya akan menganggap bahwa "cadangan" sebenarnya berukuran tidak terbatas.

Dan pertanyaan Anda adalah, bagaimana kita menghitung semua urutan yang mungkin dipilih?

Satu-satunya pilihan yang bisa Anda buat selama proses ini adalah elemen mana yang harus diambil dari kolam. Anda selalu memiliki pilihan P (=3). Pilihan tersebut akan selalu menjadi item yang berbeda (karena hanya ada satu item untuk setiap item). Selama Anda yakin bahwa tidak ada dua urutan pilihan yang berbeda yang dapat menghasilkan urutan item yang sama, sekarang Anda dapat melihat bahwa Anda memiliki PN urutan yang mungkin. Satu-satunya hal rumit yang tersisa adalah mengubah urutan indeks pilihan menjadi urutan nilai pilihan. Sebagai pengganti melakukan sesuatu yang pintar, saya mengusulkan untuk menjalankan algoritma yang kami jelaskan di atas.

from itertools import (product, count)

def generate_sequences(pool_size, n):
    for choice_sequence in product(range(pool_size), repeat=n):
        pool = list(range(pool_size))
        sequence = []
        reserve = count(pool_size)
        for choice_index in choice_sequence:
            sequence.append(pool[choice_index])
            pool[choice_index] = next(reserve)
        yield sequence

Saya pikir ini bekerja. Untuk menyederhanakan masalah alih-alih menghapus item yang dipilih dari tengah kumpulan dan menambahkan item baru dari cadangan di ujung kumpulan, saya memasukkan item baru ke dalam slot yang dikosongkan oleh item yang dipilih. Ini mengubah urutan kami memancarkan urutan, tetapi saya pikir itu seharusnya tidak mengubah keseluruhan rangkaian urutan yang dihasilkan.

Mungkin ada cara yang lebih sederhana untuk melakukan ini, tetapi saya pikir ini sama bagusnya dengan kompleksitas waktu.


Tidak tertangani di sini adalah apakah kumpulan item dasar (sebut saja ukurannya R) mungkin terbatas. Jelas bahwa R N atau Anda tidak dapat memilih N item sama sekali. Namun jika R < P + N 1 maka Anda dapat memilih N item tetapi tidak mungkin untuk mempertahankan kumpulan ukuran P yang konstan - pada akhirnya Anda tidak memiliki item dalam cadangan untuk ditambahkan ke dalamnya. Itu bisa diatasi tapi fiddly. Aku akan meninggalkan itu sebagai latihan.

1
Weeble 10 Maret 2020, 14:52