Alt Küme Bulma Algoritması

By | 27 Aralık 2012

GİRİŞ

Geçenlerde ziyaretçilerden biri bir elektronik posta ile bana ulaştı. 4 elemanlı bir kümenin tüm alt kümelerini oluşturabilecek bir kod talebinde bulundu. Normalde uzun bir süredir bu tarz isteklere cevap vermiyorum. Zira özel sektörde çalışan, evli barklı biri olduğum için özel istekleri çözümlemeye vaktim yok. Fakat bu problem çok eskiden bir kaç defa önüme çıkmıştı ve sonrasında sümen altı etmiştim. Tekrar önüme çıkınca ilk müsait zamanımda tekrar kafa yormayı istedim ve sonunda kendi oluşturduğum bir çözüm metodu buldum. Belki yıllar yıllar önce bu metodu bulan biri olmuştur. Hak yemeyelim. O kadar derin bir literatür taraması yapamadım. Google amcayla bir kaç defa haşır-neşir oldum ama bulduğum sonuçlar beni pek tatmin etmedi. Genelde 1’den başlayan ve sıralı şekilde integer elemanlara sahip dizilerin çözümleri yapılmıştı. Mesela A={1, 2, 3, 4, 5, 6} kümesi gibi. Ben biraz daha genel bir şey istedim. String ifadeleri de kapsayabilsin. Hatta tek karakterli değil, çok karakterli elemanlara sahip dizileri de kapsayabilsin. Mesela B={1, 13, “ABC”, 8, “onalti”, 55} gibi. İncelediğim bir çok algoritmayı Ali Ağaoğlu gibi “Bu değil, bu da değil, bu hiç değil, olmamış” diyerek elimin tersiyle ittim. Sonra “işte bu” diyerek “Altküme 1453″ projemi bitirdim. Bilgisayarınızın hemen yanında böyle bir algoritma istemez misiniz?

GENEL ALGORİTMA

Şimdi elimizde N elemanlı bir dizi var. Bir de altküme dizisi var. Altküme dizisi başlangıçta boş. Altküme dizisinin her bir elemanı, oluşacak alt kümeleri saklayacak. Bu durumda altküme dizisinin en son gideceği limit, N elemanlı kümenin altküme sayısı. Yani 2^N-1.

Hemen küçük bir örnek vereyim:

A = {“ali”, “45”, “9”} olsun.

Altküme = {“ali”, “45”, “9”, “ali,45″, “ali,9″, “45,9”, “ali,45,9″}

olacak. Yani oluşacak 7 adet altkümeyi tek bir dizide tuttum. Elemanları virgül ile ayırdım. Başlangıçta Altküme dizisi boş. İlk olarak halihazırda N elemanın hepsini altküme dizisine yazalım. Şimdi altküme dizimizde N adet 1 elemanlı altkümeler var.

Altküme = {“ali”, “45”, “9”}

Şimdi bir döngü ile altküme dizisinin elemanlarını teker teker tarayalım. Tararken, 1.elemanı alıp teker teker A dizisindeki elemanlarla karşılaştıracağız. Kendisinden sonraki ilk elemanla birleştirip Altküme dizisine ekleyeceğiz. Nasıl yani? Şöyle ki, Altküme dizisinin ilk elemanı olan “ali” elemanını elimize aldık. Bunu A dizisindeki elemanlarla karşılaştırıyoruz. “ali” ile “ali” olmaz. Geçiyoruz. “ali” ile “45” olur. “ali” ile “45” elemanlarını birleştiriyoruz. İşte ilk alt kümemiz oluştu. bu altkümeyi Altküme dizisinin sonuna ekliyoruz.

A = {“ali”, “45“, “9”}
Altküme = {“ali“, “45”, “9”, “ali,45“}

Sonra 1. eleman hala daha seçiliyken bunu A kümesindeki bir sonraki elemanla birleştiriyoruz. Yani “ali” ile “9” u.

A = {“ali”, “45”, “9“}
Altküme = {“ali“, “45”, “9”, “ali,45″, “ali,9}

A kümesindeki tarama bittiğinde elimizde tuttuğumuz “ali” elemanı ile işimiz bitmiş oluyor. Şimdi Altküme dizisinin 2. elemanı olan “45” i elimize alıyoruz. Yine bunu da A kümesindeki elemanlarla karşılaştırıyoruz. Karşılaştırmayı ben yukarıda 1. elemandan başlatarak anlattım. Oysa, “45” elemanı kendisinden sonra gelen elemanlarla karşılaştırılsa yeterlidir. Çünkü, “45,ali” diye bir eleman olamaz. “ali,45″ var zaten. Kendisiyle de birleşemez. Dolayısıyla ancak kendisinden sonraki elemanlarla taranmalıdır. Şimdi buna göre taramamızı yaparsak “45” ile “9” karşılaşacak ve durum normal. Bunlardan bir altküme olur.

A = {“ali”, “45”, “9“}
Altküme = {“ali”, “45“, “9”, “ali,45″, “ali,9″, “45,9“}

“45” ile işimiz bitti. Çünkü A kümesinin sonuna geldik. Şimdi elimize Altküme dizisinin 3. elemanı olan “9” u alıyoruz. A dizisi ile karşılaştırıyoruz… derken baktık ki A dizisi bitmiş. “9” elemanını olduğu gibi yere bırakıyoruz. Kısfmet değilmiş.

Şimdi sırada Altküme dizisinin 4. elemanı olan “ali,45″ var. Bunu A dizisi ile karşılaştıracağız. Burada “ali,45″ altkümesinin en son elemanı olan “45” e bakıyoruz. Karşılaştırmayı bununla yapacağız ama birleştirmede hepsini kullanacağız. Yani, “45” ile karşılaşabilecek sadece “9” var. O halde, “ali,45″ ile “9” u birleştiriyoruz. Altküme dizisine ekliyoruz.

A = {“ali”, “45”, “9“}
Altküme = {“ali”, “45”, “9”, “ali,45“, “ali,9″, “45,9”, “ali,45,9“}

İşimiz kağıt üstünde bitmiş gözüküyor ama algoritma hala daha çalışmayı sürdürecek. Sonra sırasıyla “ali,9″ elemanını elimize alacağız. Bakacağız ki “9” a karşılık bir şey yok. Sonra elimize “45,9” elemanını alacağız. Yine “9” a karşılık bir şey yok. Sonra elimizde “ali,45,9″ elemanını alacağız. Aynı mantık, en son eleman “9” a bakıyoruz. Yine yapabileceğimiz bir şey yok. Altküme dizisinin tüm elemanları tarandı ve bitti. Burada boşa zaman geçirmemek için Altküme dizisinin eleman sayısı 2^N-1 olduğunda herşeyi bitirebiliriz. Çok konuştuk haydi biraz kod yazalım.

VISUAL BASIC İÇİN ALT KÜME PROGRAMI

Bilgisayarımda VB6.0 kurulu olmadığı için bir Excel dosyası açıp VBA üzerinde test yaptım. Oluşan altküme sonuçlarını Sayfa1 üzerindeki 1.kolona sırayla yazdırdım. Kodu ham haliyle yazıyorum ve üzerinde herhangi bir kısaltma, geliştirme yapmıyorum.
Dizi adlı dizi önceden string tipinde tanımlanmış ve değerleri girilmiş olsun. Altkume adlı dizi önceden string tipinde tanımlanmış ve boş olsun.

Yukarıdaki kodlar için iki tane fonksiyon tanımlamak gerekiyor. Bunlardan birincisi, Altküme dizisinden seçtiğimiz “ali,45″ gibi birden çok elemana sahip bir alt kümenin en son elemanını döndüren fonksiyon. Hatırlayın, A kümesi ile karşılaştırma yapmak için bu son eleman lazımdı. Aşağıdaki kod bunu yapıyor. Kendisine parametre olarak gönderilen string değişkende eğer virgül karakteri yoksa son eleman olarak aynı değişkeni geri döndürüyor. Ama virgül varsa SPLIT fonksiyonu ile string ifade virgüle göre parçalanıp son eleman bulunuyor.

Bir diğer fonksiyon ise A kümesi üzerinde karşılaştırma yapmak için Altküme dizisinden seçilen alt kümenin son elemanının A kümesinde kaçıncı indiste bulunduğunu döndürüyor. Hatırlayınız, A kümesi üzerinde bir elemanı karşılaştırırken kendisinden sonraki elemanları taratalım demiştim. Ee bunu nasıl yapıcaz? O elemanın A üzerindeki indisini bileyim ki, o indisten sonraki elemanları tarayayım. İşte bu alttaki fonksiyon o işi yapıyor.

Yukarıdaki kodları Excel VBA üzerinde çalıştırdığım için ilk etapta hop diye VB 6.0 üzerinde çalışmayabilir. Formunuza uygun şekilde sağını solunu düzeltiniz. Başlangıçtaki dizi tanımlarını unutmayınız. Her gün suyunu eksik etmeyiniz.

Tam proje halini buradan indirebilirsiniz.

Umarım yararlı bir çalışma olmuştur.

3 thoughts on “Alt Küme Bulma Algoritması

  1. Gökhan Uzun

    Link olarak verilen dosya VB 6.0 için fakat yukarıda konu anlatımında verilen kodlar MS Excel için. Direkt olarak alıp bir buton nesnesinin altında çalıştırabilirsiniz. Örnekte CommandButton1_Click() diye bir yordam var. Başka isimli nesneler için o ifadeyi düzeltebilirsiniz. Function kısımlarını nesne dışında tutun.

    Reply
    1. gurcan

      Güzel bir çalışmaya benziyor.
      Yalnız eklediğiniz dosya vba olduğu için çalışmadı,
      Excel dosyası olarak bir çalışma örneği yükleyebilir misiniz?

      Reply

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir