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.
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.
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.
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);
Zgrabnie. A co w przypadku dwóch blanków?
Nie chce mi sie myslec.
Ale mogę Ci podac sposób na siedem blznków 😀