Permutacje – wersja z blankami

https://xpil.eu/v7KnL 📋

Jeżeli kogoś zainteresował poprzedni wpis o wyszukiwaniu wszystkich słówek polskich z zadanego zestawu siedmiu liter, dziś dorzucam wisienkę do tego tortu. Wisienka jest niestety spasiona jak wieprz, ale co mi tam.

Udało mi się mianowicie dodać możliwość używania blanków (blank zastępuje dowolną literę). Blanki podajemy w postaci znaków zapytania, może ich być maksymalnie dwa.

Początek skryptu jest w zasadzie bez zmian w stosunku do poprzedniej wersji. Dodałem tabelę z literami alfabetu (przyda się później do wygenerowania wszystkich podstawień blanków). Dodałem dwie zmienne liczbowe @qmpos1 i @qmpos2 (reprezentujące pozycje, na których w zadanym zestawie liter pojawiają się blanki). Gęste zaczyna się po początkowym wypełnieniu tabeli [permutacje]. Najpierw znajdujemy pierwszy i drugi znak zapytania, zamieniamy pierwszy na # a drugi na $ (potrzebujemy odróżnić jeden ? od drugiego przy generowaniu wszystkich kombinacji w następnych krokach).

Następnie, w zależności od ilości znaków zapytania, generujemy dodatkowe rekordy do tabeli [permutacje] - w przypadku dwóch pytajników używamy iloczynu kartezjańskiego z dwóch instancji tabeli [alfabet].

Na koniec usuwamy wpisy z # lub $ (o ile takowe istnieją) i generujemy listę wyników (w podobny sposób jak poprzednio).

Niestety, przy dwóch znakach zapytania ilość kombinacji rośnie do ponad pięciu milionów (a więc kombinacji jest prawie dwa razy więcej niż słów w słowniku), co znacznie wydłuża proces. Udało mi się zejść z czasem wykonania do 24 sekund, ale wiem, że można szybciej.

A oto i skrypt. Jak się komuś nudzi, niech spróbuje go ulepszyć - głównie pod kątem szybkości.

USE slowa;

GO

DROP TABLE permutacje;

GO

DROP TABLE alfabet;

GO

CREATE TABLE alfabet(litera char(1) not null);

INSERT alfabet

SELECT 'a' UNION SELECT 'ą' UNION SELECT 'b' UNION SELECT 'c' UNION SELECT 'ć' UNION SELECT 'd'

UNION SELECT 'e' UNION SELECT 'ę' UNION SELECT 'f' UNION SELECT 'g' UNION SELECT 'h' UNION SELECT 'i'

UNION SELECT 'j' UNION SELECT 'k' UNION SELECT 'l' UNION SELECT 'ł' UNION SELECT 'm' UNION SELECT 'n'

UNION SELECT 'ń' UNION SELECT 'o' UNION SELECT 'ó' UNION SELECT 'p' UNION SELECT 'r' UNION SELECT 's'

UNION SELECT 'ś' UNION SELECT 't' UNION SELECT 'u' UNION SELECT 'w' UNION SELECT 'y' UNION SELECT 'z'

UNION SELECT 'ź' UNION SELECT 'ż'

ALTER TABLE alfabet ADD CONSTRAINT PK_alfabet PRIMARY KEY CLUSTERED (litera);

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

DECLARE @s VARCHAR(7)= 'o?mi?na', @qmpos1 int, @qmpos2 int;

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;

SELECT @qmpos1 = charindex('?', @s);

SELECT @qmpos2 = charindex('?', @s, @qmpos1 + 1);

IF @qmpos1 > 0 update permutacje set s=left(s, charindex('?', s)-1) + '#' + right(s, len(s)-charindex('?', s));

IF @qmpos2 > 0 update permutacje set s=left(s, charindex('?', s)-1) + '$' + right(s, len(s)-charindex('?', s));

IF @qmpos2 > 0 BEGIN;

INSERT permutacje

SELECT REPLACE(REPLACE(p.s, '#', a1.litera), '$', a2.litera) AS perm

FROM

alfabet a1,

alfabet a2,

permutacje p;

END ELSE IF @qmpos1 > 0 BEGIN;

INSERT permutacje

SELECT REPLACE(p.s, '#', a.litera) AS perm

FROM

alfabet a,

permutacje p;

END;

DELETE permutacje WHERE s like '%[#$]%';

SELECT DISTINCT slowo

FROM words

JOIN permutacje ON words.slowo=permutacje.s;

https://xpil.eu/v7KnL 📋