Permutacje – wersja z blankami

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;

Dodaj komentarz

9 komentarzy do "Permutacje – wersja z blankami"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
tomek
Gość

oj namęczyłem się z blankami w swoim rozwiązaniu.
ale widzę że kolega ma zdecydowanie inne podejście;-)
co człowiek to podejście.

proponuję wyzwanie …

anagramacja na 13 literach + 2 blanki w czasie oczywiście skończonym.
a żeby było trudniej … bez generowania wcześniej tabelki z permutacjami.

pozdrawiam i zapraszam na

scrabblemania.pl
scrabblemania.de
scrabblemania.fr
scrabblemania.net

tomek

xpil
Gość

Już przy siedmioliterowych ilość permutacji przewyższa liczebność słownika. Przy trzynastoliterowych generowanie permutacji mija się z celem, ponieważ ich ilość to prawie 37 trylionów. Zakładając nawet że udałoby mi się generować milion permutacji na sekundę, trwałoby to sporo ponad milion lat (bez blanków!), a więc trzeba zagadnienie ugryźć od dupy strony. Podejmę wyzwanie, o ile czas pozwoli 😉

xpil
Gość

Mam gotowca. 13 sekund (na moim starym QuadCore 2.4 GHz + dysk SSD), bez wstępnego generowania permutacji, wyszukuje wszystkie 15-literowe słówka z zestawu 13 liter + 2 blanki. W wolnej chwili opublikuję.

butter
Gość

ad IF @qmpos2 > 0 .. – tu już wystarczy update bez charindex – innych ? już nie powinno być
Inna sprawa: czemu nie zrobisz joina pomiędzy permutacje a words na like'u?
word.slowo* like replace(permutacje.s,'?','_')

*- jaka piękna synergia językowa.

xpil
Gość

ad IF @qmpos2 > 0 – jesteś pewien? Zerknij jeszcze raz. Moim zdaniem jest sens zapuszczać drugi update (ten z $) tylko jeżeli drugi ? istnieje. Inna sprawa, że to tylko <5K wierszy więc koszt żaden.

A ten join na like'u – spróbuję jak się tylko dorwę do domowego kompa.

butter
Gość

nie piszę – nie zapuszczaj. Piszę, że charindexy są tam zbędne.
Dodatkowo – alfabet też jakimś Cte mógłbyś wygenerować a nie tak łopatologicznie

xpil
Gość

Alfabet? Cte? Próbowałem, ale mi ogonki przeszkadzały.

Co do charindeksów – UPDATE zapuszczam na permutacjach a charindexy obliczam ze stringu wejściowego. Hm.

butter
Gość

Któryś z nas ma dzisiaj słabszy dzień [nie wykluczam, że ja]
IF @qmpos2 > 0 update permutacje set s=left(s, charindex(‘?’, s)-1) + ‘$’ + right(s, len(s)-charindex(‘?’, s));

–>

IF @qmpos2 > 0 — tu sprawdzamy, czy warto
update permutacje set s=replace(s, ‘?’, ‘$’);

inna sprawa, że bezwarunkowy update set s=case…. były na pewno wydajniejszy

xpil
Gość

Ach, teraz rozumię. Rzygam honorem.

wpDiscuz