ReSQL.ru
     
powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Какие есть идеи? Нужна помощь в вариантах решения задачи.
18 сообщений из 43, страница 2 из 2
  2  все
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480503
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
RomanBanan,

В лоб: если левых скобок больше чем правых, то убираем число скобок равное разнице (в твоем примере это две скобки) и строим все возможные комбинации. Потом проверяем полученные строки на корректность.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
SQL> with t(str) as (select '(()(()' from dual),
  2       permute(ord, str, delta)
  3       as (select level ord, str, length(replace(str, ')')) - length(replace(str, '(')) delta
  4             from t
  5           connect by level <= length(replace(str, ')'))),
  6       rec(lvl, ord, str)
  7       as (select 1, ord, regexp_replace(str, '\(', '', 1, ord)
  8             from permute p
  9           union all
 10           select rec.lvl + 1, p.ord, regexp_replace(rec.str, '\(', '', 1, p.ord - rec.lvl)
 11             from rec join permute p on p.ord > rec.ord
 12            where lvl < p.delta),
 13       candidates
 14       as (select distinct str
 15             from rec
 16            where rec.lvl = (select delta from permute where rownum = 1)),
 17       rec_check(iter, str, result)
 18       as (select 1, str, replace(str, '()') result from candidates
 19           union all
 20           select iter + 1, str, replace(result, '()') result
 21             from rec_check
 22            where iter < 2)
 23  select str
 24    from rec_check
 25   where iter = (select delta from permute where rownum = 1)
 26     and result is null;

STR
--------------------------------------------------------------------------------
(())
()()

В запросе надо допилить логику в permute и rec когда правых больше левых, я думаю ты справишься.
Не делать же за тебя лабу полностью.
...
Рейтинг: 0 / 0
30.06.2017, 16:02
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480522
Скобарь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скобарь
Гость
RomanBanan, так?

............/´¯/)..............(\¯`\...... ......
............/....//..............\\....\...........
.........../....//................\\....\..........
....../´¯/..../´¯\............/¯` ....\¯`\.....
..././.../..../..../.|_....._|.\....\....\...\.\..
(.(....(....(..../.)..).....(..(.\....)....)....).)
.\................\/.../....\...\/................/
..\................. /........\................../.
....\..............(............)............../...
......\.............\.........../............./....
...
Рейтинг: 0 / 0
30.06.2017, 16:15
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480526
RomanBanan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RomanBanan
Гость
vladimir74,
допустим, а почему тогда нет такого варианта ответа? ()
Потому что в задании нужно найти последовательности максимальной длины.

Вообще для строки посложнее '((())(()' ответ будет:
(())()
((()))

А для строки '((()()((())(()' :
()()(())()
(())((()))
((())())()
((())(()))
((()()()))
(())(())()
((()()))()
()()((()))
(()()())()
(()()(()))
Осталось только понять на глаз все ли верны эти ответы или может какого не хватает)))
...
Рейтинг: 0 / 0
30.06.2017, 16:17
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480536
RomanBanan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RomanBanan
Гость
dbms_photoshop,

Да этот код вдвое компактнее моего, но для строки с более глубокой вложенностью это не работает например '((()()((())(()'
...
Рейтинг: 0 / 0
30.06.2017, 16:26
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480542
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
RomanBanandbms_photoshop,

Да этот код вдвое компактнее моего, но для строки с более глубокой вложенностью это не работает например '((()()((())(()'
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
SQL> with t(str) as (select '((()()((())(()' from dual),
  2       permute(ord, str, delta)
  3       as (select level ord, str, length(replace(str, ')')) - length(replace(str, '(')) delta
  4             from t
  5           connect by level <= length(replace(str, ')'))),
  6       rec(lvl, ord, str)
  7       as (select 1, ord, regexp_replace(str, '\(', '', 1, ord)
  8             from permute p
  9           union all
 10           select rec.lvl + 1, p.ord, regexp_replace(rec.str, '\(', '', 1, p.ord - rec.lvl)
 11             from rec join permute p on p.ord > rec.ord
 12            where lvl < p.delta),
 13       candidates
 14       as (select distinct str
 15             from rec
 16            where rec.lvl = (select delta from permute where rownum = 1)),
 17       rec_check(iter, str, result)
 18       as (select 1, str, replace(str, '()') result from candidates
 19           union all
 20           select iter + 1, str, replace(result, '()') result
 21             from rec_check
 22            where iter < (select delta from permute where rownum = 1))
 23  select str
 24    from rec_check
 25   where iter = (select delta from permute where rownum = 1)
 26     and result is null;

STR
--------------------------------------------------------------------------------
(()()())()
(()()(()))
(())(())()
((())(()))
((())())()
()()((()))
(())((()))
((()()))()
((()()()))
()()(())()

10 rows selected.

Ну константу можно ж додуматься убрать.
...
Рейтинг: 0 / 0
30.06.2017, 16:35
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480544
kernA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kernA
Участник
dbms_photoshopRomanBanandbms_photoshop,

Да этот код вдвое компактнее моего, но для строки с более глубокой вложенностью это не работает например '((()()((())(()'
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
SQL> with t(str) as (select '((()()((())(()' from dual),
  2       permute(ord, str, delta)
  3       as (select level ord, str, length(replace(str, ')')) - length(replace(str, '(')) delta
  4             from t
  5           connect by level <= length(replace(str, ')'))),
  6       rec(lvl, ord, str)
  7       as (select 1, ord, regexp_replace(str, '\(', '', 1, ord)
  8             from permute p
  9           union all
 10           select rec.lvl + 1, p.ord, regexp_replace(rec.str, '\(', '', 1, p.ord - rec.lvl)
 11             from rec join permute p on p.ord > rec.ord
 12            where lvl < p.delta),
 13       candidates
 14       as (select distinct str
 15             from rec
 16            where rec.lvl = (select delta from permute where rownum = 1)),
 17       rec_check(iter, str, result)
 18       as (select 1, str, replace(str, '()') result from candidates
 19           union all
 20           select iter + 1, str, replace(result, '()') result
 21             from rec_check
 22            where iter < (select delta from permute where rownum = 1))
 23  select str
 24    from rec_check
 25   where iter = (select delta from permute where rownum = 1)
 26     and result is null;

Ну константу можно ж додуматься убрать.

Дельта неправильно считается, неучитываются вырожденные случаи:

'))(('
...
Рейтинг: 0 / 0
30.06.2017, 16:41
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480557
kernA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kernA
Участник
kernA
[src oracle]
SQL> with t(str) as (select '((()()((())(()' from dual)


Дельта неправильно считается, неучитываются вырожденные случаи:

'))(('



with t(str) as (select regexp_replace(')(()()((())(((','^\)*','') from dual)

*Убираем незначимые ')' из начала строки
...
Рейтинг: 0 / 0
30.06.2017, 17:00
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480584
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
kernAДельта неправильно считается, неучитываются вырожденные случаи:

'))(('dbms_photoshopВ лоб: если левых скобок больше чем правых, то убираем число скобок равное разнице (в твоем примере это две скобки) и строим все возможные комбинации. Потом проверяем полученные строки на корректность.Что имено из двух предложений осталось непонятным?

Если число скобок равно - просто генерация вариантов не происходит и на корректность проверяется исходная строка, а не сгенерированные.
...
Рейтинг: 0 / 0
30.06.2017, 17:43
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480587
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
kernAУбираем
Код: plsql
1.
rtrim(ltrim(..., ')'), '(')
...
Рейтинг: 0 / 0
30.06.2017, 17:49
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480595
kernA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kernA
Участник
dbms_photoshopkernAДельта неправильно считается, неучитываются вырожденные случаи:

'))(('dbms_photoshopВ лоб: если левых скобок больше чем правых, то убираем число скобок равное разнице (в твоем примере это две скобки) и строим все возможные комбинации. Потом проверяем полученные строки на корректность.Что имено из двух предложений осталось непонятным?

Если число скобок равно - просто генерация вариантов не происходит и на корректность проверяется исходная строка, а не сгенерированные.

У тебя предполагается, что максимальная длина это кол-во совпадений ')','('

Например, delta = least(length(replace(str, ')')) , length(replace(str, '(')) )

В случае, когда скобки не соответствуют синтаксису(например, ')' стоят вначале, уровень (iter = (select delta from permute where rownum = 1)), должен быть изначально меньше(тк у тебя не будет комбинаций)

Код: plsql
1.
rtrim(ltrim(..., ')'), '(')


Как вариант.
...
Рейтинг: 0 / 0
30.06.2017, 18:03
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480609
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
kernAУ тебя предполагаетсяТы ничего не понял.

Хотя если просто хочется поговорить - это в ПТ.
...
Рейтинг: 0 / 0
30.06.2017, 18:20
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480645
Фотография Ozornitca
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ozornitca
Участник
в пт не очень интересно разговаривать
...
Рейтинг: 0 / 0
30.06.2017, 19:27
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480760
krudensoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
krudensoft
Участник
Ozornitca,

так ведь пятничная задача же сама искала.
Конечно, кривовато, но... Вот вам чучело. Ругайте:

clear screen;
WITH t1 AS--исходные данные
(
SELECT '(()(()(()' src
FROM dual
)
, t11 AS
(
SELECT replace(rtrim(replace(
replace(ltrim(replace(src, ')', ' ')), ' ', ')')
, '(', ' ')), ' ', '(') src--и сразу их почистим от левака
FROM t1
)
, t2 AS --разбивка на строки с символом скобки
(
SELECT
SUBSTR(src,LEVEL,1) scb
,ROWNUM RN
FROM t11
CONNECT BY LEVEL <= LENGTH(src)
)
,t3 AS --вычисляем количество левых и правых скобок
(
SELECT
SUM(CASE WHEN scb='(' THEN 1 ELSE 0 END) scbR
,SUM(CASE WHEN scb=')' THEN 1 ELSE 0 END) scbL
FROM t2
)
, t4 AS--находим минимум
(
SELECT
CASE WHEN scbR < scbL THEN scbR ELSE scbL END scbMin
FROM t3
)
,t5 AS --все нужные правые и левые скобки
(
SELECT
'(' scb
,ROWNUM RN
FROM t4
CONNECT BY LEVEL <= t4.scbMin*2
UNION ALL
SELECT
')' scb
,ROWNUM RN
FROM t4
CONNECT BY LEVEL <= t4.scbMin*2
)
, t6 AS --И получаем все варианты скобок! Тут волшебство и магия. Вжух!
(
SELECT
REPLACE(sys_connect_by_path(scb, ' '),' ','') as res
,SUBSTR(sys_connect_by_path(scb, '.*\'),1) as res2
from t5
where connect_by_isleaf = 1
start with rn = 1
connect by rn = prior rn + 1
)
,t7 AS --теперь осталось вычистить ненужные...
(
SELECT
t6.res txt
, t6.res2
, scbMin
, rownum RN
FROM t6, t4
WHERE
LENGTH(replace(t6.res,'(','')) = t4.scbMin--левых скобок нужное кол-во
AND LENGTH(replace(t6.res,')','')) = t4.scbMin --правых скобок нужное кол-во
AND SUBSTR(t6.res, 1,1)='(' --начинается с левой скобки
AND SUBSTR(t6.res, -1,1)=')' --заканчивается правой скобкой
)
,t8 AS --просто счетчик. Без него не получилось
(
SELECT LEVEL RN
FROM t4
CONNECT BY LEVEL <= scbMin*2
)
, t9 AS --плохие скобки, фу
(
SELECT t7.RN
FROM t7, t8
WHERE NVL(LENGTH(REPLACE(SUBSTR(t7.Txt, 1, t8.RN),')','')),0) - NVL(LENGTH(REPLACE(SUBSTR(t7.Txt, 1, t8.RN),'(','')),0) < 0
)
,t10 AS
(
SELECT t7.TXT, t7.SCBMIN, t7.RN, (SELECT src FROM t1) src, t7.res2
FROM t7
WHERE t7.RN NOT IN (SELECT rn FROM t9)
)
SELECT txt, src, res2, REGEXP_REPLACE(src, res2,'*') ss
FROM t10
WHERE REGEXP_LIKE(src, res2) ;
...
Рейтинг: 0 / 0
30.06.2017, 23:47
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39480776
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
RomanBananДля произвольной строки, состоящей из открывающих и закрывающих скобок написать запрос для вывода всех слов максимальной длины, представляющих правильные скобочные записи.Если решать задачу без "всех", то получается достаточно компактно.
Можно переформулировать: убрать из исходного выражения минимальное число скобок так, чтоб оно стало корректным.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
SQL> with t(id, str) as
  2   (select 1, '(()(()' from dual union all
  3    select 2, '((()()((())(()' from dual union all
  4    select 3, '((()))))))(()' from dual union all
  5    select 4, ')))()(((' from dual union all
  6    select 5, '(()))))(((())((()())())((' from dual),
  7  rec(lvl, id, str, prev) as
  8   (select 1, id, str, ' '
  9      from t
 10    union all
 11    select lvl + 1, id, regexp_replace(str, '\((#*)\)', '#\1#'), str
 12      from rec
 13     where str <> prev)
 14  select *
 15    from (select id, max(str) keep(dense_rank first order by lvl desc) str_mod from rec group by id)
 16    join t using (id)
 17   cross apply (select listagg(decode(substr(str_mod, rownum, 1), '#',
 18                                      substr(str, rownum, 1))) within group(order by level) as str_fixed
 19                  from dual
 20                connect by rownum <= length(str));

        ID STR_MOD                        STR                            STR_FIXED
---------- ------------------------------ ------------------------------ --------------------
         1 (##(##                         (()(()                         ()()
         2 ((####(####(##                 ((()()((())(()                 ()()(())()
         3 ######))))(##                  ((()))))))(()                  ((()))()
         4 )))##(((                       )))()(((                       ()
         5 ####)))((##############((      (()))))(((())((()())())((      (())(())((()())())

Для общего случая надо делать более хитрый перебор чем было у меня в заготовке, но неохота заморачиваться на SQL.
...
Рейтинг: 0 / 0
01.07.2017, 01:36
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39481447
kernA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kernA
Участник
dbms_photoshopТы ничего не понял.

dbms_photoshopДля общего случая надо делать более хитрый перебор чем было у меня в заготовке, но неохота заморачиваться на SQL.

Я тебе об этом и говорю, что сначала нужно определить максимальное кол-во совпадения "правильных" скобок("()"), а затем по этому кол-ву выводить все варианты.
...
Рейтинг: 0 / 0
03.07.2017, 09:21
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39481645
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
kernA,

А, понял. Ты не из тех, кто пишет решения, ты советчик, оценщик... и провайдер "полезных" ссылок.
...
Рейтинг: 0 / 0
03.07.2017, 12:23
| Ответить | Цитировать | Написать  
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39481804
kernA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kernA
Участник
dbms_photoshopkernA,

А, понял. Ты не из тех, кто пишет решения, ты советчик, оценщик... и провайдер "полезных" ссылок.

наверное, да.
Сначала спроектирую вариант, а потом делаю.

В данном случае, я не вижу эффективного запроса в sql, который не будет колбасить одни и те же данные по несколько раз и который выведет результат без построения дерева( не доверяю я ему при кол-ве символов от 1000)
...
Рейтинг: 0 / 0
03.07.2017, 14:47
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Какие есть идеи? Нужна помощь в вариантах решения задачи.
    #39912624
kochhar
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kochhar
Гость
А не подскажете, пожалуйста, как такую задачу можно решить при помощи model?
...
Рейтинг: 0 / 0
10.01.2020, 20:12
| Ответить | Цитировать | Написать  
18 сообщений из 43, страница 2 из 2
  2  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Какие есть идеи? Нужна помощь в вариантах решения задачи.
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&gotonew=1&tid=1881678]:
 0ms
get settings:
 19ms
get forum list:
 12ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 50ms
get topic data:
 9ms
get first new msg:
 5ms
get forum data:
 2ms
get page messages:
 50ms
get tp. blocked users:
 1ms
others: 279ms
total:  433ms
созд. / загр.: 433ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]