S kümesindeki sayılardan n adedine sahipsiniz. S kümesinin S' alt kümesinden k adet öyle sayı seçin ki S içindeki her sayının S' içinde yer alma olasılığı aynı olsun. (Yani, her sayının seçilme şansı k/n olsun.) Sayıların üzerinden yalnızca bir kere geçebilirsiniz. n'nin bilinmediği durumda ne yapardınız?

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Sayıların üzerinden yalnızca bir kere geçebilirsiniz ifadesini doğru anlıyorsam, sayılar sanki stdin'den geliyorlarmış da hiç depolanmayacaklarmış diye düşünülmeli. Yani, akım halinde gelecekler ve biz sonuçtaki elemanları yine de k/n olasılığı ile üreteceğiz.

Aslında tam aralıklara göre bir soru bu: Giriş bir InputRange ve belki çok sayıda eleman olduğundan onları depolamamız bile mümkün değil.

Örneğin, S kümesi şu dört sayıdan oluşsun: 1, 2, 3, 4. k değeri 2 ise, yani iki elemanlı yeni bir küme oluşturacaksak o dört elemanın her birisinin sonuçta yer alma şansı k/n, yani 2/4, yani %50 olsun.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Aşağıdaki program n'nin bilindiği durum için bir çözüm:

import std.stdio;
import std.string;
import std.range;
import std.exception;
import std.random;
import std.algorithm;

/* Bu çözüm dilimlerle işliyor ama InputRange de alabilirdik. InputRange
* kullanımını n'nin bilinmediği duruma saklayacağım çünkü o durumda zaten
* dilim olamıyor. */
T[] eşitOlasılıklaSeç(T)(T[] dilim, size_t k)
{
   T[] sonuç;
   auto n = dilim.length;

   enforce (k <= n, format("%s içinden %s eleman seçemem", n, k));

   foreach (eleman; dilim) {
       if (uniform(0, n) < k) {
           sonuç ~= eleman;
           --k;

           /* Burada 'if (k == 0) break;' gibi bir eniyileştirme
            * düşünülebilir ama ne kadar doğru olacağından emin değilim çünkü
            * zaten O(n) gibi bir algoritmamız olduğundan bütün sayılar
            * seçilmiş olsa bile sonuna kadar devam etmek bir sorun
            * oluşturmaz.
            *
            * Ayrıca, her sayı seçildiğinde 'if (k == 0)' denetimi
            * yapılacağını düşünürsek k'nin n'ye yakın olduğu durumlarda
            * yarardan çok zarar bile getirebilir.
            */
       }

       --n;
   }

   return sonuç;
}

unittest
{
   /* Olanaksız uzunluk istendiğinde hata atılmalı. */
   assertThrown([ 1, 2 ].eşitOlasılıklaSeç(3));

   /* Boş dilim kullanılabilmeli. */
   assert((int[]).init.eşitOlasılıklaSeç(0) == []);

   /* Sıfır uzunlukta dilim üretebilmeli. */
   assert([ 1, 2 ].eşitOlasılıklaSeç(0) == []);

   /* Aynı uzunluk istendiğinde dizinin bütün elemanları üretilmeli. */
   assert([ 1, 2, 3, 4 ].eşitOlasılıklaSeç(4) == [1, 2, 3, 4]);
}

void main()
{
   /* Dağılımın gerçekten eşit olduğunu görmek için bir de deney yapalım. */

   enum sayıAdedi = 100;
   enum seçilenAdedi = 10;
   enum deneyAdedi = 100_000;

   /* Her sayının kaç kere seçildiği bilgisi. */
   size_t[int] histogram;

   /* Sorudaki S kümesi. */
   const int[] sayılar = iota(sayıAdedi).array;

   foreach (i; 0 .. deneyAdedi) {
       /* Sorudaki S' kümesi. */
       const seçilenler = sayılar.eşitOlasılıklaSeç(seçilenAdedi);

       foreach (seçilen; seçilenler) {
           ++histogram[seçilen];
       }
   }

   /* Tembellik edeceğiz ve dağılımın eşit olup olmadığını programın
    * çıktısını gözle inceleyerek belirleyeceğiz! :p Yoksa herhalde dağılımın
    * standart sapmasına filan da bakabilir ve programın karar vermesini
    * düşünebilirdik. */
   foreach (sayı; histogram.keys.sort) {
       writefln("%4s: %4s", sayı, histogram[sayı]);
   }
}

Güvenimi arttırmak için programın çıktısına da baktım ve kendi deneyimdeki her sayının yaklaşık olarak 10 bin kere çıktığını gördüm.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Galiba n'nin bilinmediği durum da kolay çözülüyor. Hem de, kolay çözülmesinin nedeni, zaten başka yapacak pek bir şey olmaması. :)

n'yi bilmediğimize göre giriş tükenene kadar sayılar çekip k uzunluğundaki sonuca ekleyeceğiz. n==k bile olabileceğine göre, ilk k sayı arasında hiç seçici olamayız; hepsini almalıyız.

Daha sonra gelen sayılar için şöyle bir algoritma uygulayabiliriz: O sayıyı seçip seçmeyeceğine belirli bir olasılıkla karar ver. Eğer seçiyorsan, şimdilik seçilmiş olan k sayıdan rasgele birisinin yerine yeni seçtiğini yerleştir.

Eğer i'inci sayıdaysak, onu seçme kararı verirken şimdiye kadar çıkmış olanlara haksızlık olmasın diye k/i olasılığını kullanmalıyız. Önceden seçildiği halde diziden atılacak olan talihsizi de 1/k olasılığı ile belirlemeliyiz.

n ve k için seçtiğim örnekler ve kafamda yaptığım hesaplar bunun istenen sonucu vereceğini söylüyor: Sonuçta n sayının her birisinin seçilme şansı k/n olacak. Hatta, tüme varım ve tümden gelim gibi yöntemlerle ispatlanabilirmiş gibi de görünüyor.

i'inci sayının en sonda k sayı arasında kalma olasılığı şu: k/i olasılığıyla seçimiş olacak ve daha sonra gelenler tarafından diziden atılmamış olacak. Atılmamış olma şansı (1 - atılmaŞansı)'dır. Atılma şansı da şu: j=i+1'den n'ye kadar şu terimin toplamı k/j * 1/k. Yani, i+1'den n'ye kadar 1/j serisinin toplamı. O da seri açılımlarına göre 1'den küçük bir değerdir. Evet, galiba hesap doğru çıkacak ama kağıt üzerinde de göstermek gerek. :)

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

n'nin baştan bilinmediği durumda da şöyle bir kod oluyor:

import std.stdio;
import std.string;
import std.range;
import std.exception;
import std.random;
import std.traits;

ElementType!R[] eşitOlasılıklaSeç(R)(R aralık, size_t k)
   if (isInputRange!R)
{
   ElementType!R[] sonuç;

   /* İlk k elemanla başlıyoruz. */
   for (size_t i = 0; (i != k) && !aralık.empty; ++i) {
       sonuç ~= aralık.front;
       aralık.popFront();
   }

   /* Girişte en az k adet eleman olmalı. */
   enforce (sonuç.length == k,
            format("%s sayı içinden %s sayı seçemem.", sonuç.length, k));

   /* Geri kalan bütün elemanlara da şans tanıyoruz. */
   for (size_t n = k + 1; !aralık.empty; aralık.popFront(), ++n) {
       if (uniform(0, n) < k) {
           /* Bu eleman k/n olasılığı tutturdu. Şimdiye kadar seçilmiş olan k
            * elemandan bir talihsiz belirleyelim ve onun yerine yeni elemanı
            * alalım. */
           const talihsiz = uniform(0, k);
           sonuç[talihsiz] = aralık.front;
       }
   }

   return sonuç;
}


unittest
{
   /* Olanaksız uzunluk istendiğinde hata atılmalı. */
   assertThrown([ 1, 2 ].eşitOlasılıklaSeç(3));

   /* Boş dilim kullanılabilmeli. */
   assert((int[]).init.eşitOlasılıklaSeç(0) == []);

   /* Sıfır uzunlukta dilim üretebilmeli. */
   assert([ 1, 2 ].eşitOlasılıklaSeç(0) == []);

   /* Aynı uzunluk istendiğinde dizinin bütün elemanları üretilmeli. */
   assert([ 1, 2, 3, 4 ].eşitOlasılıklaSeç(4) == [1, 2, 3, 4]);
}

void main()
{
   /* Dağılımın gerçekten eşit olduğunu görmek için bir de deney yapalım. */

   enum sayıAdedi = 100;
   enum seçilenAdedi = 10;
   enum deneyAdedi = 100_000;

   /* Her sayının kaç kere seçildiği bilgisi. */
   size_t[int] histogram;

   /* Sorudaki S kümesi. */
   int[] sayılar = iota(sayıAdedi).array;

   foreach (i; 0 .. deneyAdedi) {
       /* Sorudaki S' kümesi. */
       const seçilenler = sayılar.eşitOlasılıklaSeç(seçilenAdedi);

       foreach (seçilen; seçilenler) {
           ++histogram[seçilen];
       }
   }

   /* Tembellik edeceğiz ve dağılımın eşit olup olmadığını programın
    * çıktısını gözle inceleyerek belirleyeceğiz! :p Yoksa herhalde dağılımın
    * standart sapmasına filan da bakabilir ve programın karar vermesini
    * düşünebilirdik. */
   foreach (sayı; histogram.keys.sort) {
       writefln("%4s: %4s", sayı, histogram[sayı]);
   }
}

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]