Bagaimana saya bisa mendapatkan beberapa kombinasi yang mungkin dalam R?

8

Kadang-kadang saya ingin melakukan tes yang tepat dengan memeriksa semua kemungkinan kombinasi data untuk membangun distribusi empiris yang dengannya saya dapat menguji perbedaan yang saya amati antara sarana. Untuk menemukan kemungkinan kombinasi, saya biasanya menggunakan fungsi combn. Fungsi pilih dapat menunjukkan kepada saya berapa banyak kemungkinan kombinasi yang ada. Sangat mudah untuk jumlah kombinasi menjadi begitu besar sehingga tidak mungkin untuk menyimpan hasil fungsi combn, misalnya combn (28,14) membutuhkan vektor 2,1 Gb. Jadi saya mencoba menulis objek yang melangkah melalui logika yang sama dengan fungsi combn untuk memberikan nilai dari "tumpukan" imajiner satu per satu. Namun, metode ini (seperti yang saya instantiated) mudah 50 kali lebih lambat daripada combn pada ukuran kombinasi yang masuk akal,

Apakah ada algoritma yang lebih baik untuk melakukan hal semacam ini daripada algoritma yang digunakan dalam combn? Secara khusus apakah ada cara untuk menghasilkan dan menarik kombinasi Nth yang mungkin tanpa menghitung melalui semua kombinasi sebelumnya?

r nonparametric combinatorics russellpierce
sumber
Adakah yang memperhatikan bahwa sejumlah pertanyaan yang seharusnya ada di StackOverflow R meroket di sini baru-baru ini?
John
1
Mengapa tidak membuat sampel acak?
4
@ John: Jika Anda merasa seperti itu, diskusikan masalah ini di meta.stats.stackexchange.com/questions/248/… , tidak perlu menjadi snarky.
russellpierce
@ mbq: Pengambilan sampel acak akan dengan cepat memberikan perkiraan yang wajar, terutama dengan data yang berperilaku baik. Namun, saya memang menentukan bahwa tujuan saya adalah tes yang tepat.
russellpierce
@drknexus Itu sebabnya itu adalah komentar, bukan jawaban.

Jawaban:

6

Jika Anda ingin berdagang kecepatan pemrosesan untuk memori (yang saya pikir Anda lakukan), saya akan menyarankan algoritma berikut:

  • Atur loop dari 1 ke N Pilih K, diindeks oleh i
  • Setiap saya dapat dianggap sebagai indeks untuk kombinadik , decode seperti itu
  • Gunakan kombinasi untuk melakukan statistik pengujian Anda, simpan hasilnya, buang kombinasi tersebut
  • Ulang

Ini akan memberi Anda semua N Pilih K kombinasi yang memungkinkan tanpa harus membuatnya secara eksplisit. Saya memiliki kode untuk melakukan ini dalam R jika Anda menginginkannya (Anda dapat mengirim email kepada saya di mark dot m periode fredrickson at-symbol gmail dot com).

Mark M. Fredrickson
sumber
1
Berikut ini adalah posting dengan kode dan beberapa ilustrasi: markmfredrickson.com/thoughts/2010-08-06-combinadics-in-r.html
Mark M. Fredrickson
Saya menerima jawaban ini karena itu memecahkan (apa yang saya pikirkan) adalah lebih sulit dari masalah yang saya cari solusi untuk - memilih kombinasi tertentu tanpa menghitung nilai sebelumnya. Sayangnya, ini masih sangat lambat. Mungkin seperti yang disebutkan di sini dan di tempat lain pencarian biner akan membantu mempercepat. Mungkin pendekatan terbaik adalah memiliki satu utas menghasilkan kombinasi bertahap seperti dalam jawaban mbq dan utas lainnya membacanya dan menguji mereka.
russellpierce
1

Menghasilkan kombinasi cukup mudah, lihat misalnya ini ; tulis kode ini dalam R dan kemudian proses setiap kombinasi pada saat itu muncul.


sumber
Tetapi akankah ini mengatasi kombinasi yang sangat besar?
csgillespie
@csgillespie Yah, saya percaya begitu - ini bekerja di situ , jadi hanya satu kombinasi yang disimpan dalam memori pada suatu waktu, dan hasil simulasi juga dapat digabungkan untuk menghilangkan kebutuhan menyimpannya. Ini tentu saja akan bekerja sangat lama, tetapi pencarian lengkap biasanya dilakukan. Untuk kecepatan dapat ditulis dalam C, tetapi kemudian bersama dengan bagian simulasi, yang mungkin jauh lebih lambat daripada langkah generator.
2
Itu terlihat hampir identik dengan bagaimana fungsi combn R sudah melakukan sesuatu. Saya menulis versi combn yang mengambil kombinasi dari stack satu per satu, dan seperti yang dikatakan MBE karena hanya menyimpan satu kombinasi dalam memori pada satu waktu ia dapat menangani kombinasi yang sangat besar. Masalah dengan melakukannya di R adalah bahwa melakukan pendekatan langkah-demi-langkah dalam suatu fungsi biasanya melibatkan membaca variabel keadaan ke dalam fungsi, memanipulasi mereka, kemudian menyimpannya kembali ke global - yang tampaknya hanya memperlambat segalanya / cara / turun.
russellpierce