Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
496 kez görüntülendi

İki kelimenin izomorf olmasını şöyle örneklendirelim:

word1 = "xxyzzx" , word2 = "ddaccd" kelimeleri izomorftur. Fakat word3 = "xxy" ile word4 = "abb" kelimeleri izomorf değildir. Yani birinci kelimenin harflerindeki farklılaşma/aynı olma sıralaması, ikinci kelimede de aynı şekilde görülüyorsa bu kelimeler izomorftur diyeceğiz.

 

Buna göre, verilen iki kelimenin izomorf olup olmadığını kontrol eden python programını yazınız.

 

Bilgiler:

1. İpucu olarak:  pythonda-index-fonksiyonunu-kodlama sorusuna bakılabilir.

2. Soru ile codewars sitesinde karşılaştım ve zorluk düzeyi kyu 6 dır.

Veri Bilimi kategorisinde (2.6k puan) tarafından  | 496 kez görüntülendi

Mathematica ile soyle yapilabilir..

f[x_, y_] := SameQ @@ (Values@PositionIndex@StringPartition[#, 1] & /@ {x, y})

word1 = "AAyzzA";
word2 = "ddaccd";

f[word1, word2]

True


word3 = "xxy";
word4 = "abb";

f[word3, word4]

False

 

1 cevap

1 beğenilme 0 beğenilmeme
En İyi Cevap

 

Sanirim dogru cevap bu olmali (versiyon 3 lokman gokcenin yorumlarda okuyabileceginiz test(ler)i uzerine, stringlerin boylarinin ayni olma zorunlulugunu ekledim)

def izomorf_mu(x,y):
   f = lambda x : (x.index(i) for i in x)
   return len(x)==len(y) and (all(a==b for (a,b) in zip(f(x),f(y)))


Hiz

(3.editten sonra eklendi)

x.index(i)  methodunun kompleksitesi, kotumser bakarsak x kelimesinin uzunlugu ile dogru orantili. Bu methodu x kelimesindeki her harf icin icin cagiriyoruz. Yani fonksiyonun kompleksitesi girdinin uzunlugunun karesi ile orantili. Yanilmiyorsam bu programin calisma suresini girdinin uzunlugu ile orantili yapabiliriz. Nasil ? 

 

from collections import Counter

def izomorf_mu(x,y):
	if len(x) != len(y):
		return False
	x_vars =Counter(x)
	y_vars = Counter(y)
	if len(set(x_vars.values())) != len(set(y_vars.values())): return False
	xy = {i:set() for i in x}
	yx = {i:set() for i in y}

	for (key,value) in zip(x,y):
		xy[key].add(value)
		yx[value].add(key)
	for (i,j) in zip(x,y):
		if x_vars[i] != y_vars[j]: return False
		if x_vars[i] != 1 and len(xy[i])!=1 and  len(yx[j]) != 1: return False
	return True

 

BURANIN ASAGISI YANLIS. SORUYU YANLIS ANLAMISTIM

def izomorf_mu(x,y):
     return len( set( a-b for (a,b) in zip(map(ord,x),map(ord,y)))) == 1

"ord" fonksyonu bir karakterin ascii degerini verir.

"map" fonksyonu bir fonksyonu bir kolleksyonun her elemanina uygular

"zip" fonksyonu iki tane koleksyondan bir tuple kolleksyonu olusturur.

"set" fonksyonu kume olusturmak icin. Kumelerdeki her obje biriciktir.

iki kelimenin karakterleri arasindaki fark hep ayni ise, kelimeler izomorftur diyebiliriz bence.

O zaman kelimelerin karakterlerinin farkindan bir kume yaratalim ve uzunlugu bir mi dize kontrol edelim.

 

muhtemelen herseyden once kelmielerin uzunlugu ayni mi diye kontrol etmemiz gerekir.

def izomorf_mu(x,y):
     return len(x)==len(y) and len( set( a-b for (a,b) in zip(map(ord,x),map(ord,y)))) == 1



 

(1.6k puan) tarafından 
tarafından seçilmiş

x = "ESTATE"

y = "DUELED"

kelimeleri için test ettim. Bunlar izomorftur ama, program False sonucunu veriyor.

 

Sanırım hata, ascii degerinin arasındaki farkı eşit olmaya zorladığımız için oluyor.

Ben soruyu yanlis anlamisim.
Benim kafamda bu iki kelime izomorf degil idi. Benim kafamda kelimelerin harflerini ayni miktarda ileri geri itmek vardi

DXEYED

x y den farkli olmak uzere gene izomorf degil mi ?
def izomorf_mu(x,y):

    f = lambda x : (x.index(i) for i in x)

    return all(a==b for (a,b) in zip(f(x),f(y)))

 

kodu için teste tabi tuttum.

Failed test with a = "AA" and b = "BBB": True should equal False
def izomorf_mu(x,y):

    f = lambda x : (x.index(i) for i in x)

    return len(a) == len(b) and all(a==b for (a,b) in zip(f(x),f(y)))
 

olmali
def isomorph(x,y):
    f = lambda x : (x.index(i) for i in x)
    return len(x) == len(y) and all(a==b for (a,b) in zip(f(x),f(y)))

len(a) == len(b)  kısmını düzelterek len(x) == len(y)  yaptım. $263$ testten başarıyla geçti bu kod. Tebrikler @eloi :))

peki bu kodun calisma zamani nedir? Bu kod neden kotudur ?
20,248 soru
21,774 cevap
73,420 yorum
2,148,411 kullanıcı