Это реальная задача по теории вероятностей!, от не п Налаштування

[Death]

(Show/Hide)

[LSA]

http://durdom.in.ua/public/main/photos/photo_34188.jpg
ось вам задача

[x3mEn]

Задача для знавців SQL.

Колись була така передача "Звёздный час".
Там була гра, давалося слово, із літер цього слова треба було на час скласти як можна більше інших слів.

Зараз є варіації на цю тему, наприклад "Слова из слов"
Якось мені стало цікаво, як можна було б знайти всі слова, які можна утворити із заданого, якщо в мене є словник усіх допустимих слів.

А тепер задача:
Є таблиця виду

create table WORDS
(
  WORD VARCHAR2(40)
);

Треба написати SQL, яким із таблиці WORDS вибираються всі відмінні від заданого слова, які можна утворити із літер даного.

Наприклад, якщо дадено слово ОСТРОВ, з нього можно утворити наступні слова:
ОР
ВОР
РОВ
РОТ
СОР
ТОР
ВОРС
ОСОТ
РОСТ
СОРТ
ТОРС
ТРОС
ВОРОТ
ОСТОВ
СТВОР

Коли я це завдання дав своїм знайомим, як не дивно, у них воно викликало ступор.
А вам слабо написати SQL?
Процедури не приймаються, тільки чистий select

[Rilian]

WITH RECURSIVE xtab AS (
WITH no_cte AS (
SELECT
1::int AS len
, idx as idx
, substring ( 'ОСТРОВ' FROM idx FOR 1) as str
FROM generate_series(1, char_length( 'ОСТРОВ' )) idx
)
SELECT t0.len as len
, t0.idx
, t0.str
FROM no_cte t0
UNION SELECT 1+t1.len
, tc.idx
, t1.str || tc.str AS str
FROM xtab t1
JOIN no_cte tc ON tc.idx > t1.idx
)
SELECT * FROM xtab
WHERE EXISTS (SELECT * FROM words WHERE word = str)

[x3mEn]

generate_series - це, вибачаюсь, який стандарт SQL?
взагалі-то задача написати SQL в стандарті ну хоча б SQL:2008

SQL Server 2008?
http://www.spatialdbadvisor.com/sql_server...aldbadvisor.com

Є набагато простіше рішення, без generate_series.
Та я і не впевнений, що наведене рішення працює правильно.
Бо не зміг привести його до стандарту SQL, щоб перевірити

[A1ex01]

та давай сразу свой вариант, а кто сможет выложит лучше)

[x3mEn]

ну ок, даю:

select * from words
where upper('&word') = '&word'
  and word <> '&word'
  and length(word) <= length('&word')
  and
    case
      when length(word) >= 1
        then length('&word') - length(replace('&word', substr(word,1,1))) - length(word) + length(replace(word, substr(word,1,1)))
      else 1
    end >=0
  and
    case
      when length(word) >= 2
        then length('&word') - length(replace('&word', substr(word,2,1))) - length(word) + length(replace(word, substr(word,2,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 3
        then length('&word') - length(replace('&word', substr(word,3,1))) - length(word) + length(replace(word, substr(word,3,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 4
        then length('&word') - length(replace('&word', substr(word,4,1))) - length(word) + length(replace(word, substr(word,4,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 5
        then length('&word') - length(replace('&word', substr(word,5,1))) - length(word) + length(replace(word, substr(word,5,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 6
        then length('&word') - length(replace('&word', substr(word,6,1))) - length(word) + length(replace(word, substr(word,6,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 7
        then length('&word') - length(replace('&word', substr(word,7,1))) - length(word) + length(replace(word, substr(word,7,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 8
        then length('&word') - length(replace('&word', substr(word,8,1))) - length(word) + length(replace(word, substr(word,8,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 9
        then length('&word') - length(replace('&word', substr(word,9,1))) - length(word) + length(replace(word, substr(word,9,1)))
      else 1
    end >=0    
  and
    case
      when length(word) >= 10
        then length('&word') - length(replace('&word', substr(word,10,1))) - length(word) + length(replace(word, substr(word,10,1)))
      else 1
    end >=0    
order by length(word), word;

Таким скриптом вибираються всі слова з обмеженням, що вхідне слово не більше 10 символів.
Якщо треба більше - домальовується ще N аналогічних конструкцій через and.
Просто мені було достатньо 10.
Можливо не зовсім і естетично, зате швидкодія майже не залежить від довжини слова.
Я думаю, що на довжині слова овер 16 літер рекурсія загнеться.
Можу поділитися словничком в 52 тисячі слів, на якому я тренувався.

[x3mEn]

А от і словничок.

[x3mEn]

перевірка на слові НИКОТИНАМИДАДЕНИНДИНУКЛЕОТИДФОСФАТГИДРИН (40 символів)

5614 rows selected in 1,517 seconds

[Rilian]

x3mEn, postgres

вариант с if это говнокод если можно юзать if то тогда уже и like надо заюзать

[Death]

а перевірка на слові АБВГДЕЄЖЗ.........Я что даст?

[Rilian]

а перевірка на слові АБВГДЕЄЖЗ.........Я что даст?

даст частичную выборку из словаря, ибо большая часть слов использует повторы букв

[x3mEn]

Rilian, PostgreSQL не у всьому відповідає стандарту SQL, скажімо так, свій власний діалект SQL.
На інших СУБД твій чудокод не запускається.
А мій запит принаймні на твоїй PostgreSQL має працювати.
Або буде працювати після невеличкої адаптації, я бачу що у substr і length в PostgreSQL свій синтаксис.

Щодо говнокоду не зрозумів. Хочеш, юзай like, це не заборонено.
Спробуй залий в базєйку табличку і тестани на 40-символьному слові.
Покажи час виконання і результат (кількість слів) на слові НИКОТИНАМИДАДЕНИНДИНУКЛЕОТИДФОСФАТГИДРИН,
тоді можна щось буде вирішити, що із написано говнокод, а що геніальний чудокод.

а перевірка на слові АБВГДЕЄЖЗ.........Я что даст?

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

13816 rows selected

Найдовші слова:
ГЕМОТРАНСФУЗИЯ
ЗВУКОСНИМАТЕЛЬ
ПОДХЛЁСТЫВАНИЕ
РАЗГИЛЬДЯЙСТВО
ЧЕТЫРЁХПОЛЮСНИК
ЧЕТЫРЁХУГОЛЬНИК

Щоправда в мене словничок з обмеженням слова в 15 символів максимум.
Просто в грі Ерудит максимальна довжина слова 15, тому сенсу ще довші слова пхати не було.

[Rilian]

x3mEn, сорри за троллинг, но вы в COMPANY_NAME пишете программу для платной подписки абонентов на "эрудит" ?

[x3mEn]

Не палимось, не палимось...

В дійсності я цей скрипт придумав в одну з безсонних ночей, коли був дома, а не на роботі, так що це моя інтелектуальна власність, а не COMPANY_NAME.

[A1ex01]

Покажи час виконання і результат (кількість слів) на слові НИКОТИНАМИДАДЕНИНДИНУКЛЕОТИДФОСФАТГИДРИН,
тоді можна щось буде вирішити, що із написано говнокод, а що геніальний чудокод.

+1, Rilian, время выполнения твоей версии давай