Permutacje po polsku

https://xpil.eu/8nkMe 📋

Niedawno pokazałem jak z bazy słów języka polskiego powyciągać słowa z unikalnymi końcówkami. Dzisiaj kontynuuję zabawę z tą samą bazą słów, tym razem jednak pokażę jak znaleźć wszystkie permutacje siedmioliterowe należące do słownika. Innymi słowy, taki dopalacz do gry w Scrabble / Literaki, pomagający znaleźć wszystkie siedmioliterowe (a więc wysoko punktowane) słowa z danego zestawu liter.

Dla uproszczenia przyjąłem brak mydeł (czyli pustych płytek zwanych też "blankami" lub "jokerami").

W pierwszej kolejności należy przygotować sobie bazę ze słówkami, według zaleceń z tego wpisu. Następnie tworzymy pustą tabelę, do której będziemy generować wszystkie permutacje siedmioliterowe (będzie ich zawsze 5040). Tablica nazywa się [permutacje] i tworzymy ją o tak:

CREATE TABLE permutacje(s char(7) NOT NULL);

Następnie deklarujemy i inicjalizujemy zmienną reprezentującą słowo, które będziemy permutować:

DECLARE @s VARCHAR(7)= 'niemowa';

W kolejnym kroku zerujemy tabelę z permutacjami:

TRUNCATE TABLE permutacje;

No i teraz samo gęste, czyli wypełniamy tabelę [permutacje] wszystkimi siedmioliterowymi permutacjami liter słowa 'niemowa':

WITH

n AS

(SELECT 1 AS liczba UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7),

perm AS

(SELECT

CAST(SUBSTRING(@s, liczba, 1) AS VARCHAR(7)) AS anagram,

CAST('.'+CAST(liczba AS CHAR(1))+'.' AS VARCHAR(13)) AS uklad,

CAST(1 AS INT) AS poziom

FROM n

UNION ALL

SELECT

CAST(anagram+SUBSTRING(@s, liczba, 1) AS VARCHAR(7)),

CAST(uklad+CAST(liczba AS CHAR(1))+'.' AS VARCHAR(13)),

p.poziom + 1

FROM

perm p

JOIN n

ON p.uklad NOT LIKE '%.'+CAST(liczba AS CHAR(1))+'.%'

AND p.poziom < 7

)

INSERT permutacje

SELECT DISTINCT anagram

FROM perm

WHERE poziom = 7

ORDER BY anagram;

W ostatnim kroku wyświetlamy wynik, czyli te permutacje, które są słowami języka polskiego:

SELECT slowo FROM words JOIN permutacje ON words.slowo=permutacje.s;

Całość wykonuje się bardzo szybko (poniżej jednej sekundy).

Wyniki: aminowe, emanowi, manowie, miewano, moweina, namowie, niemowa.

Jeżeli którykolwiek z Czytelników dotarł aż do tego miejsca bez bólu głowy, a jeszcze, nie daj Billu, zrozumiał sposób generowania permutacji, zapraszam do kolejnego wysiłku umysłowego: jak do powyższej logiki dodać blanki? Przypominam, że zarówno w Scrabble (TM) jak i w Literakach możliwe są maksymalnie dwa blanki.

https://xpil.eu/8nkMe 📋