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.