Branżowe

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.

Tagi
Pokaż więcej

xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a'capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

5 komentarzy do "Permutacje po polsku"

avatar
  Subscribe  
najnowszy najstarszy oceniany
Powiadom o
butter
Gość

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.