Bagaimana cara membuat ulang dalam R tanpa mengulangi permutasi?

12

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.

Mittenchops
sumber
Secara default, argumen 'ganti' dari 'sampel' diatur ke FALSE.
ocram
Terima kasih ocram, tapi itu berhasil di dalam sampel tertentu. Jadi itu memastikan bahwa 0,1,2, dan 3 tidak akan mengulangi dalam undian (jadi, saya tidak bisa menggambar 0,1,2,2), tapi saya tidak tahu apakah itu menjamin bahwa sampel kedua, Saya tidak bisa menggambar urutan yang sama 0123 lagi. Itulah yang saya pikirkan tentang implementasi, apakah pengaturan seed memiliki efek pada pengulangan itu.
Mittenchops
Ya, inilah yang akhirnya saya pahami dengan membaca jawaban ;-)
ocram
1
Jika limitmelebihi 12, Anda kemungkinan akan kehabisan RAM ketika R mencoba mengalokasikan ruang untuk seq(1,factorial(limit)). (12! Membutuhkan sekitar 2 GB, jadi 13! Akan membutuhkan sekitar 25 GB, 14! Sekitar 350 GB, dll.)
whuber
2
Ada yang cepat, kompak, dan elegan solusi untuk menghasilkan urutan acak semua permutasi dari 1: n, asalkan Anda bisa dengan nyaman menyimpan n! bilangan bulat dalam kisaran 0: (n!). Ini menggabungkan representasi tabel inversi permutasi dengan representasi bilangan faktorial angka.
Whuber

Jawaban:

9

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 argumen n(ukuran permutasi untuk sampel) dan m(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.

rperm <- function(m, size=2) { # Obtain m unique permutations of 1:size

    # Function to obtain a new permutation.
    newperm <- function() {
        count <- 0                # Protects against infinite loops
        repeat {
            # Generate a permutation and check against previous ones.
            p <- sample(1:size)
            hash.p <- paste(p, collapse="")
            if (is.null(cache[[hash.p]])) break

            # Prepare to try again.
            count <- count+1
            if (count > 1000) {   # 1000 is arbitrary; adjust to taste
                p <- NA           # NA indicates a new permutation wasn't found
                hash.p <- ""
                break
            }
        }
        cache[[hash.p]] <<- TRUE  # Update the list of permutations found
        p                         # Return this (new) permutation
    }

    # Obtain m unique permutations.
    cache <- list()
    replicate(m, newperm())  
} # Returns a `size` by `m` matrix; each column is a permutation of 1:size.

Sifat dari replicateadalah mengembalikan permutasi sebagai vektor kolom ; misalnya , berikut mereproduksi contoh dalam pertanyaan asli, ditransformasikan :

> set.seed(17)
> rperm(6, size=4)
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    2    4    4    3    4
[2,]    3    4    1    3    1    2
[3,]    4    1    3    2    2    3
[4,]    2    3    2    1    4    1

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 kkkkkk-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:

 Number Size=10 Size=15 Size=1000 size=10000 size=100000
     10    0.00    0.00      0.02       0.08        1.03
    100    0.01    0.01      0.07       0.64        8.36
   1000    0.08    0.09      0.68       6.38
  10000    0.83    0.87      7.04      65.74
 100000   11.77   10.51     69.33
1000000  195.5   125.5

(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.headdengan 1 (yang mengalikan ukuran level atas dengan 10) mempercepat rperm(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=5n=15n!

Kode kerja berikut.

rperm <- function(m, size=2) { # Obtain m unique permutations of 1:size
    max.failures <- 10

    # Function to index into the upper-level cache.
    prefix <- function(p, k) {    # p is a permutation, k is the prefix size
        sum((p[1:k] - 1) * (size ^ ((1:k)-1))) + 1
    } # Returns a value from 1 through size^k

    # Function to obtain a new permutation.
    newperm <- function() {
        # References cache, k.head, and failures in parent context.
        # Modifies cache and failures.        

        count <- 0                # Protects against infinite loops
        repeat {
            # Generate a permutation and check against previous ones.
            p <- sample(1:size)
            k <- prefix(p, k.head)
            ip <- cache[[k]]
            hash.p <- paste(tail(p,-k.head), collapse="")
            if (is.null(ip[[hash.p]])) break

            # Prepare to try again.
            n.failures <<- n.failures + 1
            count <- count+1
            if (count > max.failures) {  
                p <- NA           # NA indicates a new permutation wasn't found
                hash.p <- ""
                break
            }
        }
        if (count <= max.failures) {
            ip[[hash.p]] <- TRUE      # Update the list of permutations found
            cache[[k]] <<- ip
        }
        p                         # Return this (new) permutation
    }

    # Initialize the cache.
    k.head <- min(size-1, max(1, floor(log(m / log(m)) / log(size))))
    cache <- as.list(1:(size^k.head))
    for (i in 1:(size^k.head)) cache[[i]] <- list()

    # Count failures (for benchmarking and error checking).
    n.failures <- 0

    # Obtain (up to) m unique permutations.
    s <- replicate(m, newperm())
    s[is.na(s)] <- NULL
    list(failures=n.failures, sample=matrix(unlist(s), ncol=size))
} # Returns an m by size matrix; each row is a permutation of 1:size.
whuber
sumber
Ini dekat, tapi saya perhatikan saya mendapatkan beberapa kesalahan, seperti 1, 2, dan 4, tapi saya rasa saya mengerti apa yang Anda maksud dan harus bisa bekerja dengannya. Terima kasih! > 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
Mittenchops
3

Menggunakan uniquedengan cara yang benar seharusnya melakukan trik:

set.seed(2)
limit <- 3
myindex <- seq(0,limit)

endDim<-factorial(limit)
permutations<-sample(myindex)

while(is.null(dim(unique(permutations))) || dim(unique(permutations))[1]!=endDim) {
    permutations <- rbind(permutations,sample(myindex))
}
# Resulting permutations:
unique(permutations)

# Compare to
set.seed(2)
permutations<-sample(myindex)
for(i in 1:endDim)
{
permutations<-rbind(permutations,sample(myindex))
}
permutations
# which contains the same permutation twice
MånsT
sumber
Maaf karena tidak menjelaskan kodenya dengan benar. Saya agak terburu-buru sekarang, tapi saya senang menjawab pertanyaan yang Anda miliki nanti. Juga, saya tidak tahu tentang kecepatan kode di atas ...
MånsT
1
Saya memfungsikan apa yang Anda berikan kepada saya dengan cara ini: `myperm <- function (limit) {myindex <- seq (0, limit) endDim <-faktorial (batas) permutasi <-sample (myindex) sementara (is.null (dim (unik) (permutasi))) || redup (unik (permutasi)) [1]! = endDim) {permutasi <- rbind (permutasi, sampel (myindex))} return (unik (permutasi))} 'Berhasil, tetapi ketika saya dapat melakukan limit = 6, limit = 7 membuat komputer saya kepanasan. = PI pikir pasti masih ada cara untuk melakukan
subsampel
@Mittenchops, Mengapa Anda mengatakan kami perlu menggunakan unik untuk resampling dalam R tanpa mengulangi permutasi? Terima kasih.
Frank
2

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 permndan mereka secara acak memesan mereka yang menggunakan sample:

x <- combinat:::permn(1:3)
> x[sample(factorial(3),factorial(3),replace = FALSE)]
[[1]]
[1] 1 2 3

[[2]]
[1] 3 2 1

[[3]]
[1] 3 1 2

[[4]]
[1] 2 1 3

[[5]]
[1] 2 3 1

[[6]]
[1] 1 3 2
joran
sumber
Saya suka ini BANYAK, dan saya yakin itu pemikiran yang tepat. Tapi masalah saya membuat saya menggunakan urutan naik ke 10. Permn () secara signifikan lebih lambat antara faktorial (7) dan faktorial (8), jadi saya pikir 9 dan 10 akan menjadi sangat besar.
Mittenchops
@Mittenchops Benar, tetapi masih mungkin Anda benar-benar hanya perlu menghitungnya sekali, bukan? Simpan ke file, lalu muat ketika Anda membutuhkannya dan "sampel" dari daftar yang telah ditentukan. Jadi Anda bisa melakukan perhitungan lambat permn(10)atau apa pun hanya sekali.
joran
Benar, tetapi jika saya menyimpan semua permutasi di suatu tempat, bahkan ini rusak sekitar faktorial (15) --- terlalu banyak ruang untuk menyimpan. Itu sebabnya saya bertanya-tanya apakah pengaturan seed akan memungkinkan saya untuk sampel permutasi secara kolektif --- dan jika tidak, jika ada algoritma untuk melakukan itu.
Mittenchops
@Mittenchops Mengatur seed tidak akan memengaruhi kinerja, itu hanya menjamin awal yang sama setiap kali Anda melakukan panggilan ke PRNG.
Roman Luštrik
1
@Mitten Lihat bantuan untuk set.seed: ini menjelaskan cara menyimpan status RNG dan mengembalikannya nanti.
Whuber