Algoritma sorusu

Merhabalar. Elimizde birden fazla kelime olduğunu düşünelim. Bunların uzunlukları farklı olabilir. Örnek kelimeler;

yazbel
kitap
belge

Bu kelimelerden, kelime sayısı uzunluğunda yeni kombinasyonlar üretilmesi isteniyor. Birinci kelimeden başlama koşulu var. Şöyle örnek verelim. Elimizde 3 kelime varsa, oluşacak kelimelerin uzunluğu 3 olmalıdır. Oluşturma kuralı şöyle. Yukarıdan aşağıya inerek her kelimeden bir harf alıyoruz. Örneğin;

y a z b e l
k i t a p
b e l g e

ykb
yke
ykl
ykg
yke

Bunlar birinci iterasyondan oluşan kelimelerdir. İkinci iterasyon da şöyle;

yib
yie
yil
yig
yie

Kısaca yukarıdan aşağı, tüm kelimelerin tüm harflerini kullanarak kelime sayısı uzunluğunda yeni kelimeler üretilmek isteniyor. Bu soruyu çözmek için siz nasıl bir yol izlerdiniz? Şimdiden teşekkürler.

Peki sadece algoritma mı istiyorsunuz yoksa koda dökülmüş halimi?

Farketmez. Hangisini paylaşmak istiyorsanız paylaşabilirsiniz :slight_smile: Amaç çeşitli çözüm yöntemlerini görmek.

kabul edilebilir mi bilmiyorum ama product fonksiyonu işi bayağı kolaylaştırıyor
Örneğin

import time
from itertools import product

list = ["yazbel","kitap", "belge"]

print(list)


def olustur(kelime_listesi):
       for j in product(*kelime_listesi):
           kelime = ''.join(j)
           print("\t", kelime)

olustur(list)

Neredeyse bütün işi product yapıyo :grin:

1 Beğeni

Yani kabul edilebilir neden olmasın? Ama product fonksiyonunun uyguladığı kartezyen çarpımı algoritması nasıl yapılabilir, başka yöntemlerle çözülebilir mi gibisinden sormuştum. Yine de teşekkür ederim :slight_smile:

İste tamda bundan sebep kabul edilebilirmi diye sormuştum :slight_smile:
Belki başka birileri farklı yöntemleri gösterir şimdi bende merak ettim

1 Beğeni

Evet mesela ben de ağaç veri yapısıyla çözülebilir diye düşündüm. Kök düğümden itibaren tüm ağacı gezdiğimizde kelimeler üretilmiş oluyor. Hafızada yer kaplamış oluyor ama yine de bir çözüm yöntemi diye düşünüyorum. Ya da yönlü graf yapılabilir, yukarıdan aşağıya yönlendirilmiş bir şekilde kök düğümden ilerlediğimizde son düğüme gelindiğinde gidilecek yer yoksa izlenilen yol yeni oluşturulan bir kelime olarak ele alınır. Ağaçtan farkı, aynı düğümü birçok kez oluşturmamış oluruz, sadece yönlendirme yapmış oluruz.

Ayrıca stackoverflow’da şöyle bir çözüm yapılmış:

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                yield (a,)+prod
3 Beğeni
def product(iterable, lenght, i=0):
    l = len(iterable)
    for i in range(i, l ** lenght):
        s = []
        for j in range(lenght):
            i, index = divmod(i,l)
            s.append(iterable[index])
        yield s

Tabii bu sadece iterable ^ lenght'i hesaplıyor.

2 Beğeni

Merhaba @coderistan ,
Ne kadar verimli olur bilmemekle birlikte benim de aklıma şöyle bir çözüm geldi. Ben de ikilik, onluk sistemlerdeki mantığın bir benzerini bu soruda uyguladım :slight_smile:

n = int(input()) # kelime sayisi

keys = []
keySizes = []
totalWordNum = 1
for i in range(n):
	key = list(set( input() ))
	keys.append(key)
	keyLength = len(key)
	keySizes.append(keyLength)
	totalWordNum *= keyLength
	
num = [0] * n

for i in range(totalWordNum):
	newStr = ""
	for j in range(n - 1):
		num[j + 1] += num[j] // keySizes[j]
		num[j] %= keySizes[j]
		newStr += keys[j][num[j]]
	newStr += keys[n - 1][num[n - 1]]
	print(newStr)
	num[0] += 1
2 Beğeni

Katkılarınız için sağolun arkadaşlar :slight_smile: Verilen cevaplarda(ve forum genelinde) dikkatimi çeken bir şey, değişken isimleri kısa ve amacına hitap eden bir isim ile isimlendirilmemiş, ben de dahil çok kişi dikkat etmiyor. Evet kod çalışıyor ama kodu okuyan kişi o değişkenin ne iş yaptığını anlamak için o değişkenin ismini hafızasına atıp aşağıya doğru iniyor ki ne işe yaradığını anlayabilsin. Bir yerden sonra takip edemez oluyor.

Okunabilir kod için mümkünse değişken isimlerini amacına uygun bir şekilde seçmeye dikkat etmemiz gerektiğini düşünüyorum :slight_smile: Tekrar teşekkürler…

1 Beğeni

Mantığınız gayet iyi hocam, amacına hizmet eden bir kod olmuş elinize sağlık :slight_smile:

1 Beğeni