Permutacje po polsku

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.

5 komentarzy

  1. jeśli blakni = char(32), to @s='nie mowa', rozszerzenie pól [zamian 7 na 8]. Od varcharów odchodzić nie trzeba, bo blanki na końcu się nie liczą.

    Aczkolwiek nie wiem, czy ostatni join tego nie wytnie.

    1. Nie może być osiem – na stojaku zawsze jest siedem liter (z czego maksymalnie dwa blanki). W zależności od tego czy jest jeden blank czy dwa, ilość możliwych permutacji rośnie 32-krotnie lub 1024-krotnie (a więc w najgorszym przypadku mamy trochę ponad 5 milionów permutacji).

      Mam już działające rozwiązanie, ale strasznie się ślimaczy. 22 sekundy na wyszukanie wszystkich "legalnych" słówek z dwoma blankami i jakieś 3 sekundy z jednym.

      1. Nie gram w Scramble czy inne sudoku z całkami [jak mówi Kowalski], więc musisz bardziej łopatologicznie wyłożyć problem. Blank może zastąpić dowolną literę?
        Jeśli tak, to wynik bez blanków potraktowałbym jako materiał wejściowy do kolejnej pętli a tam [x:1-7; dla każdego z wyników]
        SELECT slowo FROM words
        where words.slowo like
        permutacje ON like left(permutacje.s,x)+'_'+right(permutacje.s,6-x);

Leave a Comment

Twój adres e-mail nie zostanie opublikowany.