Deklaratív programozás

A feladat

A feladat tömör áttekintése:
Válogassa ki ts-ből azokat a ti és tj szavakat, amelyekhez van olyan h egész 1 ≤ h ≤ k mellett, hogy ti utolsó h karaktere megegyezik tj első h karakterével. Az ilyen szavakat a továbbiakban legfeljebb k helyen átfedőnek vagy röviden max-k-átfedőnek nevezzük.

Precízebben:
Jelöljük az m ≥ 0 hosszú u szót alkotó karaktersorozatot a következőképpen: u0 u1 ... um-1. Az u és v szavakat, amelyek hossza rendre m és n, h-átfedőnek nevezzük, ha h ≥ 1, és a következő feltételek mind teljesülnek: um-h = v0, um-h+1 = v1, ..., um-1 = vh-1. Ilyenkor azt is mondjuk, hogy az u a v-vel h-átfedésben van.

Írjon programot, amely az összes max-k-átfedő szópárt egy (u,hvs) párokból álló listaként állítja elő. Itt az u-val jelölt helyen pontosan akkor kell egy ts-beli szónak szerepelnie, ha van hozzá egy olyan, tőle különböző ts-beli szó, amellyel h ≤ k mellett h-átfedésben van. Egy adott u esetében a vele párban álló hvs nem más, mint azoknak a (h,v) pároknak a listája, amelyekre az u a v-vel h-átfedésben van, ahol v a ts lista egy eleme, v ≠ u és h ≤ k. Az (u,hvs) párokból álló listát az u szavak ábécé szerint növekvő sorrendjében, a (h,v) párokból álló hvs listát a h számok, azon belül pedig a v szavak ábécé szerint növekvő sorrendjében kell előállítani.

Ajánljuk figyelmébe:

• Azoknak a szavaknak, amelyek nincsenek átfedésben egyetlen szóval sem, nem szabad előfordulniuk az eredménylistában.
• Gondoljon arra, hogy egy szó teljes átfedésben lehet egy másikkal. (Például az u = "itat" és a v = "tat" szavak h-átfedésben vannak h = 1 és h = 3 esetén is, és az utóbbi esetben u tartalmazza v-t.)

SML-specifikációk

Írjon SML-függvényt max_k_atfedok néven, amely egy füzérlista szavaiból előállít egy (u,hvs) párokból álló olyan listát, amelyben minden u esetén a vele párt alkotó nem-üres hvs lista pontosan azokból a (h,v) elemekből áll, amelyek esetén az u a v-vel h-átfedésben van. Az (u,hvs) párokból álló listát az u szavak ábécé szerint növekvő sorrendjében, a (h,v) elemekből álló hvs listát a h számok, azon belül pedig a v szavak ábécé szerint növekvő sorrendjében kell előállítani.

(* max_k_atfedok : int -> string list -> (string * (int * string) list) list
 * max_k_atfedok k ts = a ts lista legfeljebb k helyen átfedő elemeit tartalmazó,
 *   (u,hvs) párokból álló olyan lista, amelyben minden u és a hozzá tartozó hvs
 *   lista minden (h,v) eleme esetén fennáll, hogy az u a v-vel h-átfedésben van.  
 *   Az (u,hvs) párok listáját u szerint, a (h,v) párokból álló hvs listákat
 *   pedig előbb a h, majd a v szerint növekvő sorrendben kell előállítani. 
 *)

Az ábécé szerinti sorrend megegyezik a String.compare által meghatározott sorrenddel. Egy fs füzérlista rendezhető a Listsort.sort String.compare fs függvényalkalmazással.

Példák

val t1=max_k_atfedok 2 ["asztalos","alma","apu","utas","anyu","satu","malom"];
> val t1 =
    [("alma", [(1, "anyu"), (1, "apu"), (1, "asztalos"), (2, "malom")]),
     ("anyu", [(1, "utas")]),
     ("apu", [(1, "utas")]),
     ("asztalos", [(1, "satu")]),
     ("satu", [(1, "utas")]),
     ("utas", [(1, "satu"), (2, "asztalos")])
    ] : (string * (int * string) list) list

val t2=max_k_atfedok 2 ["alma","omlik","mama","malom","ikra","atom","adat","ragad"];
> val t2 =
    [("adat", [(2, "atom")]),
     ("alma", [(1, "adat"), (1, "atom"), (2, "malom"), (2, "mama")]),
     ("atom", [(1, "malom"), (1, "mama"), (2, "omlik")]),
     ("ikra", [(1, "adat"), (1, "alma"), (1, "atom"), (2, "ragad")]),
     ("malom", [(1, "mama"), (2, "omlik")]),
     ("mama", [(1, "adat"), (1, "alma"), (1, "atom"), (2, "malom")]),
     ("omlik", [(2, "ikra")]),
     ("ragad", [(2, "adat")])
    ] : (string * (int * string) list) list

val t3=max_k_atfedok 3 ["aaa","aab","baa","aaaa"];
> val t3 =
    [("aaa", [(1, "aaaa"), (1, "aab"), (2, "aaaa"), (2, "aab"), (3, "aaaa")]),
     ("aaaa", [(1, "aaa"), (1, "aab"), (2, "aaa"), (2, "aab"), (3, "aaa")]),
     ("aab", [(1, "baa")]),
     ("baa", [(1, "aaa"), (1, "aaaa"), (1, "aab"), (2, "aaa"), (2, "aaaa"), (2, "aab")])
    ] : (string * (int * string) list) list

val t4=max_k_atfedok 999999 ["aaa","aab","baa","aaaa"];
> val t4 =
    [("aaa", [(1, "aaaa"), (1, "aab"), (2, "aaaa"), (2, "aab"), (3, "aaaa")]),
     ("aaaa", [(1, "aaa"), (1, "aab"), (2, "aaa"), (2, "aab"), (3, "aaa")]),
     ("aab", [(1, "baa")]),
     ("baa", [(1, "aaa"), (1, "aaaa"), (1, "aab"), (2, "aaa"), (2, "aaaa"), (2, "aab")])
    ] : (string * (int * string) list) list

Prolog-specifikációk

Írjon Prolog-eljárást max_k_atfedok/3 néven, amely egy névkonstans-lista elemeiből előállít egy u-hvs párokból álló olyan listát, amelyben minden u esetén a vele párt alkotó nem-üres hvs lista pontosan azokból a h-v elemekből áll, amelyek esetén az u a v-vel h-átfedésben van. Az u-hvs párokból álló listát az u szavak ábécé szerint növekvő sorrendjében, a h-v elemekből álló hvs listát a h számok, azon belül pedig a v szavak ábécé szerint növekvő sorrendjében kell előállítani.

% :- type szo          == atom
% :- type szolista     == list(szo).
% :- type atfedeshossz == int.
% :- type atfedoje     ---> atfedeshossz-szo.
% :- type atfedoi      ---> szo-list(atfededoje).
% :- type atfedok      ---> list(atfedoi).
% :- pred max_k_atfedok(szolista::in, atfedeshossz::in, atfedok::out)

% max_k_atfedok(K,L1,L2), ahol L2 az L1 lista legfeljebb K helyen átfedő
%   elemeit tartalmazó, U-HVS párokból álló olyan lista, amelyben minden U
%   és a hozzá tartozó HVS lista minden H-V eleme esetén fennáll, hogy az
%   U a V-vel H-átfedésben van. Az U-HVS párok listáját U szerint, a H-V
%   párokból álló HVS listákat pedig előbb a H, majd a V szerint növekvő
%   sorrendben kell előállítani.

Az ábécé szerinti sorrend megegyezik a '@<'/2 eljárás által meghatározott sorrenddel. Egy L1 lista rendezhető a sort(L1,L1S) hívással. (Ez ugyan összevonja az azonos elemeket, de ez nem baj, ha az L1-ben nincsenek azonos elemek.)

Példák

| ?- max_k_atfedok(2, [asztalos,alma,apu,utas,anyu,satu,malom], L1).
L1 = [alma-[1-anyu,1-apu,1-asztalos,2-malom],anyu-[1-utas],apu-[1-utas],
     asztalos-[1-satu],satu-[1-utas],utas-[1-satu,2-asztalos]] ? ;
no

| ?- max_k_atfedok(2,[alma,omlik,mama,malom,ikra,atom,adat,ragad],L).
L = [adat-[2-atom],alma-[1-adat,1-atom,2-malom,2-mama],atom-[1-malom,
    1-mama,2-omlik],ikra-[1-adat,1-alma,1-atom,2-ragad],malom-[1-mama,
    2-omlik],mama-[1-adat,1-alma,1-atom,2-malom],omlik-[2-ikra],
    ragad-[2-adat]] ? ;
no

| ?- max_k_atfedok(3,[aaa,aab,baa,aaaa],L).
L = [aaa-[1-aaaa,1-aab,2-aaaa,2-aab,3-aaaa],aaaa-[1-aaa,1-aab,2-aaa,2-aab,
    3-aaa],aab-[1-baa],baa-[1-aaa,1-aaaa,1-aab,2-aaa,2-aaaa,2-aab]] ? ;
no

| ?- max_k_atfedok(999999,[aaa,aab,baa,aaaa],L).
L = [aaa-[1-aaaa,1-aab,2-aaaa,2-aab,3-aaaa],aaaa-[1-aaa,1-aab,2-aaa,2-aab,
    3-aaa],aab-[1-baa],baa-[1-aaa,1-aaaa,1-aab,2-aaa,2-aaaa,2-aab]] ? ;
no

Megjegyzés

Tudnivalók a beadásról

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatokért plusz 1-1 pont jár.