Di R, jika saya set.seed (), dan kemudian menggunakan fungsi sampel untuk mengacak daftar, dapatkah saya menjamin saya tidak akan menghasilkan permutasi yang sama?
yaitu...
set.seed(25)
limit <- 3
myindex <- seq(0,limit)
for (x in seq(1,factorial(limit))) {
permutations <- sample(myindex)
print(permutations)
}
Ini menghasilkan
[1] 1 2 0 3
[1] 0 2 1 3
[1] 0 3 2 1
[1] 3 1 2 0
[1] 2 3 0 1
[1] 0 1 3 2
akankah semua permutasi yang dicetak menjadi permutasi unik? Atau ada beberapa kesempatan, berdasarkan cara ini diterapkan, bahwa saya bisa mendapatkan beberapa pengulangan?
Saya ingin dapat melakukan ini tanpa pengulangan, dijamin. Bagaimana saya melakukannya?
(Saya juga ingin menghindari harus menggunakan fungsi seperti permn (), yang memiliki metode yang sangat mekanistik untuk menghasilkan semua permutasi --- itu tidak terlihat acak.)
Juga, sidenote --- sepertinya masalah ini adalah O ((n!)!), Jika saya tidak salah.
r
sampling
combinatorics
resampling
Mittenchops
sumber
sumber
limit
melebihi 12, Anda kemungkinan akan kehabisan RAM ketika R mencoba mengalokasikan ruang untukseq(1,factorial(limit))
. (12! Membutuhkan sekitar 2 GB, jadi 13! Akan membutuhkan sekitar 25 GB, 14! Sekitar 350 GB, dll.)Jawaban:
Pertanyaannya memiliki banyak interpretasi yang valid. Komentar - terutama yang mengindikasikan permutasi 15 elemen atau lebih diperlukan (15! = 1307674368000 semakin besar) - menunjukkan bahwa yang diinginkan adalah sampel acak yang relatif kecil , tanpa penggantian, dari semua n! = n * (n-1) (n-2) ... * 2 * 1 permutasi 1: n. Jika ini benar, ada (agak) solusi yang efisien.
Fungsi berikut
rperm
,, menerima dua argumenn
(ukuran permutasi untuk sampel) danm
(jumlah permutasi ukuran n untuk menggambar). Jika m mendekati atau melebihi n !, fungsi akan membutuhkan waktu yang lama dan mengembalikan banyak nilai NA: ini dimaksudkan untuk digunakan ketika n relatif besar (katakanlah, 8 atau lebih) dan m jauh lebih kecil dari n !. Ia bekerja dengan caching representasi string dari permutasi yang ditemukan sejauh ini dan kemudian menghasilkan permutasi baru (secara acak) sampai yang baru ditemukan. Ini mengeksploitasi kemampuan pengindeksan daftar asosiatif R untuk mencari daftar permutasi yang ditemukan sebelumnya dengan cepat.Sifat dari
replicate
adalah mengembalikan permutasi sebagai vektor kolom ; misalnya , berikut mereproduksi contoh dalam pertanyaan asli, ditransformasikan :Pengaturan waktu sangat baik untuk nilai m kecil hingga sedang, hingga sekitar 10.000, tetapi menurunkan untuk masalah yang lebih besar. Sebagai contoh, sampel dari m = 10.000 permutasi dari n = 1000 elemen (sebuah matriks dengan nilai 10 juta) diperoleh dalam 10 detik; sampel m = 20.000 permutasi n = 20 elemen yang diperlukan 11 detik, meskipun output (matriks 400.000 entri) jauh lebih kecil; dan menghitung sampel m = 100.000 permutasi n = 20 elemen dibatalkan setelah 260 detik (saya tidak memiliki kesabaran untuk menunggu penyelesaian). Masalah penskalaan ini tampaknya terkait dengan penskalaan inefisiensi dalam pengalamatan asosiatif R. Seseorang dapat mengatasinya dengan menghasilkan sampel dalam kelompok, katakanlah, sekitar 1000 atau lebih, kemudian menggabungkan sampel tersebut ke dalam sampel besar dan menghapus duplikat.
Edit
Kita dapat mencapai kinerja asimptotik linier dekat dengan memecah cache menjadi hierarki dua cache, sehingga R tidak perlu mencari melalui daftar besar. Secara konseptual (meskipun tidak seperti yang diterapkan), buat array yang diindeks oleh elemen pertama dari permutasi. Entri dalam larik ini adalah daftar semua permutasi yang membagikan elemen pertama . Untuk memeriksa apakah permutasi telah terlihat, gunakan elemen pertamanya untuk menemukan entri dalam cache dan kemudian cari permutasi tersebut di dalam entri itu. Kita dapat memilih untuk menyeimbangkan ukuran yang diharapkan dari semua daftar. Implementasi aktual tidak menggunakank k k kk k k k k -lipat array, yang akan sulit diprogram secara umum, tetapi menggunakan daftar lain.
Berikut adalah beberapa waktu yang berlalu dalam detik untuk berbagai ukuran permutasi dan jumlah permutasi berbeda yang diminta:
(Speedup yang kelihatannya anomali dari ukuran = 10 ke ukuran = 15 adalah karena level pertama dari cache lebih besar untuk ukuran = 15, mengurangi jumlah rata-rata entri dalam daftar tingkat kedua, sehingga mempercepat pencarian asosiatif R.) biaya dalam RAM, eksekusi dapat dibuat lebih cepat dengan meningkatkan ukuran cache tingkat atas. Hanya meningkatkan
k.head
dengan 1 (yang mengalikan ukuran level atas dengan 10) mempercepatrperm(100000, size=10)
dari 11,77 detik menjadi 8,72 detik, misalnya. cache 10 kali lebih besar namun tidak mencapai perolehan yang berarti, clocking pada 8,51 detik.)Kecuali untuk kasus 1.000.000 permutasi unik dari 10 elemen (sebagian besar dari semua 10! = Sekitar 3,63 juta permutasi semacam itu), praktis tidak ada tabrakan yang pernah terdeteksi. Dalam kasus luar biasa ini, ada 169.301 tabrakan, tetapi tidak ada kegagalan total (satu juta permutasi unik sebenarnya diperoleh).
Perhatikan bahwa dengan ukuran permutasi yang besar (lebih dari 20 atau lebih), peluang untuk mendapatkan dua permutasi yang identik bahkan dalam sampel sebesar 1.000.000.000 semakin kecil. Dengan demikian, solusi ini berlaku terutama dalam situasi di mana (a) sejumlah besar permutasi unik (b) antara dan atau lebih elemen yang dihasilkan tetapi meskipun demikian, (c) secara substansial lebih sedikit daripada semuapermutasi diperlukan.n = 15 n !n=5 n=15 n!
Kode kerja berikut.
sumber
> rperm(6,3) $failures [1] 9 $sample [,1] [,2] [,3] [1,] 3 1 3 [2,] 2 2 1 [3,] 1 3 2 [4,] 1 2 2 [5,] 3 3 1 [6,] 2 1 3
Menggunakan
unique
dengan cara yang benar seharusnya melakukan trik:sumber
Saya akan sedikit melangkah ke pertanyaan pertama Anda, dan menyarankan bahwa jika Anda berurusan dengan vektor yang relatif pendek, Anda bisa menghasilkan semua permutasi menggunakan
permn
dan mereka secara acak memesan mereka yang menggunakansample
:sumber
permn(10)
atau apa pun hanya sekali.set.seed
: ini menjelaskan cara menyimpan status RNG dan mengembalikannya nanti.