Anagrammid ja Python III

Üks võimalik rekursiivne lahendus:

Otsime fraasi f anagramme nii, et lahutame fraasist sõnu maha ja otsime siis (fraas-sõna) anagramme.

Defineerime funktsiooni X mis võtab sisse fraasi f ja ettearvutatud sõnastiku S

- vaatame, kas f on ise S sees sisalduv sõna

- kui on, siis on üks anagramm leitud. jätame meelde!

- teeme tsükli üle kõikide sõnastiku S sõnade s

- leiame jääk-fraasi f-s

- arvutame välja jäägile vastava uue sõnalisti: selles on sõnad, mis võivad olla (f-s) anagrammiks või anagrammi osadeks

- kutsume X välja, fraasiks on siis (f-s) ja sõnastikuks uus sõnastik

Rekursiooni lõpp ehk baas on see, kui sisendfraas jääb nii lühikeseks, et temast enam anagrammi leida ei saa.

Kui sisend on "paks kurinurm", siis käik on umbes:

X (lõbuskurinurm) = "lõbus" + X (kurinurm) = "lõbus" + "kuri" + X(nurm), ja kuna viimane on sõna, siis anagramm ongi "lõbus kuri nurm".

Veel:

- peame alati teadma rekursiooni hetke taset. Me ei taha liiga sügavale minna / liiga mitmeosalisi anagramme leida) ja võimaliku anagrammi seni leitud osiseid.

- peame edasi andma juba leitud anagrammi osad.

Programm ise

# Anagrammide leidmine

# Leiab mitmeosalisi anagramme

# Rekursiivne

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

import re

anagrammi_max_pikkus = 3

sona_min_pikkus = 4

# teeme sõnalistist dictionary

# "räsi" on sõna sorditud kuju: kala => aakl

# dictionary 'key' on räsi ja 'value' on kõikide sama räsiga sõnade list[]

sonalist = dict()

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

for x in ff:

    sona = x.lower().strip().replace(" ", "")

    if len(sona)>=sona_min_pikkus:

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

        if sona_rasi in sonalist:

            sonalist[sona_rasi].append(sona)

        else:

            sonalist[sona_rasi] = [sona]

ff.close()

print("Saime sõnastikust", str(len(sonalist)), "erineva räsiga sõna.")

# defineerime funktsiooni, mis leiab, kas kõik S2 tähed on S1 sees olemas

# s1_contains_s2("kalad", "laad") => True

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)

# defineerime funktsiooni, mis lahutab kõik S2 tähed S1-st

# s1_minus_s2("kalad", "kala") => "d"

def s1_minus_s2(s1, s2):

    for x in s2:

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

    return(s1)

# rekursiivne alam-sõne leidja

# sisend:

# - ff: sisendfraas, mille anagrammi leitakse. string, tühikuteta

# - sonad: list räsidest, mis seal sees võivad veel olla. puhh on eelnevalt välja arvutatud

# - seni_leitud: list seni leitud sõnaosadest

# - level: kui sügaval me oleme ehk mitmendat anagrammi osa-sõna me leiame

#   level on piiramiseks, et ei leitaks igavaid lühisõnadest koosnevaid anagramme

def lammuta(ff, sonad, seni_leitud, level):

    ff = ''.join(sorted(ff))      # viime oma fraasi räsi kujule

    # kui leiame fraasile listist täpse vaste, siis olemegi leidnud anagrammi

    # lisame selle anagrammid hulka

    # duplikaatide eemaldamiseks teeme veidi keemiat:

    # teisendame leitud anagrammi listiks, sorteerime, teisendame tagasi stringiks

    if ff in sonad:

        anagrammid.add(" ".join(sorted((seni_leitud + ' ' + ff).split())))

    # rohkematest sõnadest koosnevaid anagramme me leida ei taha, naaseme

    if level >= anagrammi_max_pikkus:

        return

    # järelejäänud fraas on lühike, sellest endast ei saa enam mitmeosalist annagrammi olla, naaseme

    if len(ff)< sona_min_pikkus*2:

        return

    # rekursioon

    # - võtame kõik fraasis sisalduda võivad räsid

    # - lahutame nad ükshaaval sisend-fraasist

    # - rakendame lammuta() funktsiooni jäägi (fraas-räsi) peal

    for x in sonad:

        if (len(ff)-len(x)) >= sona_min_pikkus:

            jaak = s1_minus_s2(ff, x)

            # nüüd tuleb teha uus list räsidest, mis võivad olla jaak sees

            sonad_2 = [ k for k in sonad if s1_contains_s2(jaak, k) ]

            if (len(sonad_2) > 0):

                lammuta(jaak, sonad_2, seni_leitud + ' ' + x, level+1)

# Põhitsükkel

while(True):

    # muutujad:

    # - fraas - fraas, mille anagramme me otsime

    # - fraas2 - eelmise tühikute ja suurtähtedeta vorm

    # - sonalist - dictionary kõikidest räsidest ja neile vastavate sõnade listidest

    # - voimalikud - list räsidest, mis võivad fraas2 sees olla

    # - anagrammid - algselt tühi list[] leitavatest anagrammidest

    fraas = input("Kirjuta midagi: ")

    fraas2 = fraas.lower().strip().replace(' ','')

    voimalikud = [k for k in sonalist.keys() if s1_contains_s2(fraas2, k)]

    anagrammid = set()

    print("Fraas:", fraas)

    print("Fraasi normkuju:", fraas2)

    print("Võimalikud anagrammi osad:", len(voimalikud))

    print()

    # Lükkame rekursiooni käima!

    lammuta(fraas2, voimalikud, "", 1)

    print ("Leidsime", len(anagrammid), "erinevat anagrammi.")

    # anagrammid[] on nüüd hulk stringidest

    # sorteerime need kõigepealt pikkuse järgi, lühemad anagrammid ette - kõibepealt kaheosalised, siis kolmeosalised jne

    for x in sorted(anagrammid, key=len):

        # anagrammid on hulk (set), selle element on x on list

        # tuleb teda veidi kenamaks formaatida ja räsidele sõnastikust vasted otsida

        ss = ""

        for y in x.split():

            ss = ss + re.sub("[,\']", "", str(sonalist[y])) + " "

        print(ss)

    print()