Forum: Ders Arası RSS
The Algorithm Design Manual, problem 2-43
Seçilme şansları k/n olan sayılar
acehreli (Moderatör) #1
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: The Algorithm Design Manual, problem 2-43
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
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
acehreli (Moderatör) #3
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
acehreli (Moderatör) #5
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Ders Arası RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 20:02:06 (UTC -08:00)