Anagrammid ja Python II

Sisendiks sõna, fraas või lause.

Väljundiks sõnapaar, mis on esimese anagramm.

Ülesande võib sõnastada "leia sõnade paar, mille summa võrdub sisend": sorted(x + y) = sorted(sisend).

Selle lahendus on triviaalne: kahekordne tsükkel üle kõikide sõnade koos summa võrdlusega.

Et kiirem oleks, võib eelvalikusse võtta sõnad, mis SAAVAD anagrammi osad olla, st mis sisalduvad algses fraasis.

Aga lihtsam on lahendada pöörduülesanne.

Sõnu mitte liita, vaid lahutada:

"Iga sõna jaoks leia sisendi ja sõna vahe. Kui see on ka sõna, siis leidsid anagrammi."

Ehk, ühekordne tsükkel üle kõikide sobivate sõnade ning kontroll, kas sorted(sisend - sõna) sisaldub sõnastikus.

(Sisuliselt me loodame, et Python on tark ja et sõnastikus sisaldumise kontroll ei ole lineaarne otsing. Kui oleks, oleks algoritm endiselt O(n2).

Sõnastiku eeltöötlus

Kõigepealt on meil vaja sõnastik lühemaks töödelda.

Jätame alles vaid sõnad, mis VÕIVAD olla anagrammi osad.

Ehk sõnad, mille kõik tähed (ka korduvad) on sisend-fraasis olemas.

# Defineerime funktsiooni, mis ütleb, kas kõik s2 tähed on s1 sees.

# s1_contains_s2("kala", "aa")  => True

# s1_contains_s2("kala", "ab")  => False

def s1_contains_s2(s1, s2):

    l1 = len(s1)

    l2 = len(s2)

    if(l2>l1):

         return False

    for x in s2:

        s1 = s1.replace(x, '', 1)

    return (len(s1) == l1 - l2)

Ja siis rakendame seda sõnastiku peal.

Kõige lühem on läbi list comprehension'i.

Muidugi võib ka tsükliga teha - käia kogu sonastik läbi ja kui sõnastiku võti on fraas'i sees, siis jätta see võti alles.

Uus andmehulk on tüüpi "set" ehk iga sõna võib seal olla täpselt ühe korra.

Ja muidugi pole seal sõnad, vaid sõnade "sorteeritud" variandid.

fraas = input("Palun sisesta fraas, mille anagramme otsid: ")

voimalikud = set()

for x in sonastik:

    if s1_contains_s2(fraas_n, x):

    e    voimalikud.add(x)

Teiseks defineerime abifunktsiooni, mis "lahutab" ühest sõnast teise.

# s1_minus_s2("aabc", "ab") => "ac"

def s1_minus_s2(s1, s2):

    y = s1

    for z in s2:

        y = y.replace(z, '', 1)

    return y

Paneme kõik kokku

while(True):

    fraas = input("Palun sisesta fraas, mille anagramme otsid: ")

    fraas_s = sorted(fraas.lower().strip().replace(' ',''))     # sisendfraas, sorditud märkide listi kujul

    fraas_n = ''.join(fraas_s)                                  # sisendfraas, sorditud stringi kujul

    voimalikud = set()

    for x in sonastik:

        if s1_contains_s2(fraas_n, x):

            voimalikud.add(x)

    print("Leidsime", len(voimalikud), "sobivat lemmat.")

    # lahutame anagrammitavast fraasist järgmise sõna

    # kui tulemus on samuti sõna, oleme leidnud anagrammi!!

    for x in voimalikud:

        y = s1_minus_s2(fraas_n, x)

        if y in voimalikud:

print("Jee! Anagramm!", pp(sonastik[x]), "--", pp(sonastik[y]))

Edasiarendusi

Muidugi ei pea Pythonis päriselt tsükleid kirjutama.

Kõik eelnev oli meelega ja illustratiivselt pikaks venitatud.

Tegelikult on programm viidav kahe list comprehension'i peale.

Ühega lühendame sõnastiku ära, teisega leiame ja trükime välja kõik anagrammid.

voimalikud = set([k for k in sonastik.keys() if s1_contains_s2(fraas_n, k) ])

print([(sonastik[x],sonastik[s1_minus_s2(fraas_n, x)]) for x in sorted(voimalikud) if s1_minus_s2(fraas_n, x) in voimalikud])

Meil on bugi: et anagramme leitakse topelt.

Palun sisesta fraas, mille anagramme otsid: kaur virunurm

Leidsime 169 sobivat lemmat.

Jee! Anagramm! ruuminurk -- arv

Jee! Anagramm! arv -- ruuminurk

Ravimeid on palju.

Kogu programm

# Anagrammide leidmine

# Leiab fraasi kõik kaheosalised anagrammid

# sõnade allikaks https://www.eki.ee/tarkvara/wordlist/lemmad2013.txt

# algoritm lühidalt:

# ettevalmistus:

# 1) loeme eesti sõnastiku sisse

# 2) teeme sellest pythoni sõnastiku (dictionary), kus sõnad on grupeeritud enda sorteeritud kuju kaupa ja viitavad iseenda kõikidele anagrammidele: aakl => kala kaal

# 3) kogu edasine töö käib sorditud sõnadega (aakl)

# küsime kasutajalt fraasi F ja:

# 1) leiame sõnad S, mis VÕIVAD olla fraasi anagramm osad: neis on sees sobivad tähed ja nad ei ole liiga pikad

# 2) iga sellise sõna jaoks leiame fraasi ülejäänud osa, F-S

# 3) kui F-S on samuti sõna, siis ongi meil anagramm: F = S ++ (F-S)

# 4) eraldi pingutust nõuab see, et me lisaks S ++ (F-S) anagrammile ei leiaks ka selle koopiat (F-S) ++ S

import re                   # regexp teek, väljundi viisakaks formaatimiseks

sona_min_pikkus = 3         # minimaalse anagrammi-osa pikkus

sonastik = dict()

ff = open("lemmad2013.txt", "r", encoding="utf8")

for x in ff:

    sona = x.lower().strip()

    if len(sona)>=sona_min_pikkus:

        sona_rasi = ''.join(sorted(sona))

        if sona_rasi in sonastik:

            sonastik[sona_rasi].append(sona)

        else:

            sonastik[sona_rasi] = [sona]

ff.close()

print ("Lugesime sisse", len(sonastik), "anagrammatiliselt erinevat sõna.")

def s1_contains_s2(s1, s2):

    l1 = len(s1)

    l2 = len(s2)

    if(l2>l1):

         return False

    for x in s2:

        s1 = s1.replace(x, '', 1)

    return (len(s1) == l1 - l2)

def s1_minus_s2(s1, s2):

    y = s1

    for z in s2:

        y = y.replace(z, '', 1)

    return y

def pp(s):

    return re.sub("[\'\[\],]", "", str(s))

while(True):

    fraas = input("Palun sisesta fraas, mille anagramme otsid: ")

    fraas_s = sorted(fraas.lower().strip().replace(' ',''))     # sisendfraas, sorditud märkide listi kujul

    fraas_n = ''.join(fraas_s)                                  # sisendfraas, sorditud stringi kujul

    voimalikud = set()

    for x in sonastik:

        if s1_contains_s2(fraas_n, x):

            voimalikud.add(x)

    print("Leidsime", len(voimalikud), "sobivat lemmat.")

    # lahutame anagrammitavast fraasist järgmise sõna

    # kui tulemus on samuti sõna, oleme leidnud anagrammi!!

    for x in voimalikud:

        y = s1_minus_s2(fraas_n, x)

        if y in voimalikud:

            print("Jee! Anagramm!", pp(sonastik[x]), "--", pp(sonastik[y]))

    # lühem ja segasem variant

    # voimalikud = set([k for k in sonastik.keys() if s1_contains_s2(fraas_n, k) ])

    # print([(sonastik[x],sonastik[s1_minus_s2(fraas_n, x)]) for x in sorted(voimalikud) if s1_minus_s2(fraas_n, x) in voimalikud])

Google Sites

Report abuse