Задачка с хабра, голову себе сломал, — как сделать изящно.
Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы.
Скобки, возможно, несбалансированные.
Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
Например, "(a)())()))((b(b)" — три лишних ")" и две лишних "("
Здравствуйте, Кодт, Вы писали:
К>Задачка с хабра, голову себе сломал, — как сделать изящно.
К>Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы. К>Скобки, возможно, несбалансированные. К>Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
К>Например, "(a)())()))((b(b)" — три лишних ")" и две лишних "("
К>(a(()))b(b) К>(a(()))(bb) К>(a()())b(b) К>(a()())(bb) К>(a())()b(b) К>(a())()(bb) К>(a)(())b(b) К>(a)(())(bb) К>(a)()()b(b) К>(a)()()(bb)
Здравствуйте, kov_serg, Вы писали:
_>На скорую руку как-то так _>#include <set>
Вот это напрягает. Ведь легко создать такой набор, который даст комбинаторный взрыв:
k открывающих скобок, затем 2k закрывающих, и обязательно нескобочные символы между ними всеми.
Надо удалить k из 2k скобок, что, очевидно, даёт C(2k,k) вариантов ответа.
Предпочтительнее было бы сделать генератор (пусть даже с O(n) внутренней памяти, где n — длина строки), последовательно выдающий ответы.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, kov_serg, Вы писали:
_>>На скорую руку как-то так _>>#include <set>
К>Вот это напрягает. Ведь легко создать такой набор, который даст комбинаторный взрыв: К>k открывающих скобок, затем 2k закрывающих, и обязательно нескобочные символы между ними всеми. К>Надо удалить k из 2k скобок, что, очевидно, даёт C(2k,k) вариантов ответа.
К>Предпочтительнее было бы сделать генератор (пусть даже с O(n) внутренней памяти, где n — длина строки), последовательно выдающий ответы.
Так тут и есть два счетчика L * R
g++ a.cpp && ./a.out | grep -B 2 -A 2 count
Здравствуйте, kov_serg, Вы писали:
_>>>#include <set>
К>>Вот это напрягает. Ведь легко создать такой набор, который даст комбинаторный взрыв: К>>Предпочтительнее было бы сделать генератор (пусть даже с O(n) внутренней памяти, где n — длина строки), последовательно выдающий ответы. _>Так тут и есть два счетчика L * R
Не, я имею в виду вот что.
Ты используешь set<string> variants не просто для буферизации вывода, а для устранения дубликатов.
Например, строку "())" можно исправить двумя способами: "(_)" и "()_", где _ — место удаления.
Если мы подадим на вход алгоритма строку длиной 45 скобок, — получим С(30,15) = 155 млн вариантов длиной 30 скобок.
Во-первых, мы замучаемся ждать, пока первые ответы появятся на выходе. (И это я ещё пощадил, — а возьмём строку 20+40 скобок, там уже будут 137 млрд)
Во-вторых, оно выжрет память.
В-третьих, реальное количество вариантов без дубликатов — если мы добавим гораздо меньше посторонних символов — тоже будет гораздо меньше. Так, например, строка только из скобок даст ровно один вариант.
И вот ради него надо будет столько времени молотить?
Здравствуйте, Кодт, Вы писали:
К>Не, я имею в виду вот что. К>Ты используешь set<string> variants не просто для буферизации вывода, а для устранения дубликатов. К>Например, строку "())" можно исправить двумя способами: "(_)" и "()_", где _ — место удаления.
Да это чтобы не рассматривать симметрии которые могут быть.
К>Если мы подадим на вход алгоритма строку длиной 45 скобок, — получим С(30,15) = 155 млн вариантов длиной 30 скобок. К>Во-первых, мы замучаемся ждать, пока первые ответы появятся на выходе. (И это я ещё пощадил, — а возьмём строку 20+40 скобок, там уже будут 137 млрд) К>Во-вторых, оно выжрет память. К>В-третьих, реальное количество вариантов без дубликатов — если мы добавим гораздо меньше посторонних символов — тоже будет гораздо меньше. Так, например, строка только из скобок даст ровно один вариант. К>И вот ради него надо будет столько времени молотить?
К>Или я невнимательно прочитал твой код?
Да я как обычно поспешил. Можно было лучше рассмотреть симметрии выражения. Примерно так
Здравствуйте, Кодт, Вы писали:
К>Задачка с хабра, голову себе сломал, — как сделать изящно.
К>Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы. К>Скобки, возможно, несбалансированные. К>Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
К>Например, "(a)())()))((b(b)" — три лишних ")" и две лишних "("
К>(a(()))b(b) К>(a(()))(bb) К>(a()())b(b) К>(a()())(bb) К>(a())()b(b) К>(a())()(bb) К>(a)(())b(b) К>(a)(())(bb) К>(a)()()b(b) К>(a)()()(bb)
Здравствуйте, Кодт, Вы писали:
К>Задачка с хабра, голову себе сломал, — как сделать изящно. К>Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы. К>Скобки, возможно, несбалансированные. К>Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
Правльно я понимаю, изюминка в том, чтобы избежать дублирования, причем, это должно обеспечиваться самим алгоритмом, фильтрация дублей при помощи, например, std::set красивым решением не считается?
Ну вот, например, такое решение канает как красивое?
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, rg45, Вы писали:
R>>Ну вот, например, такое решение канает как красивое?
R>>http://ideone.com/odUmiM
_>С этой строкой попробуй c "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))" _>
Ну так то ведь был просто эскиз безо всякой оптимизации. После самой косметической оптимизации у меня этот пример считается за 4 секунды (на ideone). Только количество вариантов у меня получается побольше, чем у тебя, а именно 966730. Кто-то из нас где-то налажал Могу выслать архивом мой аутпут, если хочешь.
Здравствуйте, rg45, Вы писали:
R>Правльно я понимаю, изюминка в том, чтобы избежать дублирования, причем, это должно обеспечиваться самим алгоритмом, фильтрация дублей при помощи, например, std::set красивым решением не считается?
Именно. Потому что очень легко придумать строки, на которых получится комбинаторный взрыв. Я уже говорил выше: 15 открывающих скобок, затем 30 закрывающих с некоторым вкраплением посторонних символов.
R>Ну вот, например, такое решение канает как красивое?
Здравствуйте, Кодт, Вы писали:
К>Именно. Потому что очень легко придумать строки, на которых получится комбинаторный взрыв. Я уже говорил выше: 15 открывающих скобок, затем 30 закрывающих с некоторым вкраплением посторонних символов.
К>И тут же используешь set<string>.
Ну написал ведь уже, не пропадать же добру
А главное, я прочувствовал суть проблемы и смогу с ней справиться чисто алгоритмически, как мне кажется. Это потребует больше времени, конечно же.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>Ну так то ведь был просто эскиз безо всякой оптимизации. После самой косметической оптимизации у меня этот пример считается за 4 секунды (на ideone). Только количество вариантов у меня получается побольше, чем у тебя, а именно 966730. Кто-то из нас где-то налажал Могу выслать архивом мой аутпут, если хочешь.
R>http://ideone.com/MV2VDS
Здравствуйте, Кодт, Вы писали:
К>Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы. К>Скобки, возможно, несбалансированные. К>Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
К>Например, "(a)())()))((b(b)" — три лишних ")" и две лишних "("
Решим для начала задачу для скобок без других символов.
Посчитаем следующую динамику: число различных строк длиной i на суффиксе длиной j с балансом b и научимся находить k-ую в лексикографическом порядке строку.
Получим решение за O(N4). При подсчёте динамики будем жадным образом брать первую открывающую и первую закрывающую скобку.
Здравствуйте, NotImplemented, Вы писали:
NI>Здравствуйте, Кодт, Вы писали:
К>>Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы. К>>Скобки, возможно, несбалансированные. К>>Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
К>>Например, "(a)())()))((b(b)" — три лишних ")" и две лишних "("
NI>Решим для начала задачу для скобок без других символов. NI>Посчитаем следующую динамику: число различных строк длиной i на суффиксе длиной j с балансом b и научимся находить k-ую в лексикографическом порядке строку. NI>Получим решение за O(N4). При подсчёте динамики будем жадным образом брать первую открывающую и первую закрывающую скобку.
Для подсчета можно вычислить кол-во левых вариантов и умножить на кол-во правых, будет значительно быстрее (в корень раз от прямого варианта).
(a)())()))((b(b)
l ll lLL
RR r
L: 0/1 0/2 2/3
R: 0/1 2/2
count(L)=5
count(R)=2
5*2=10
()())()))((()
l ll lLL
RRr
L: 0/1 0/2 2/3
R: 2/3
count(L)=5
count(R)=1
5*1=5
Здравствуйте, Кодт, Вы писали:
К>Задачка с хабра, голову себе сломал, — как сделать изящно.
К>Дано: строка, в которой есть скобки (одного вида — круглые) и другие символы. К>Скобки, возможно, несбалансированные. К>Нужно: удалить минимальное количество скобок так, чтобы восстановить баланс. (Ну это просто). И вывести все возможные решения.
К>Например, "(a)())()))((b(b)" — три лишних ")" и две лишних "("
К>(a(()))b(b) К>(a(()))(bb) К>(a()())b(b) К>(a()())(bb) К>(a())()b(b) К>(a())()(bb) К>(a)(())b(b) К>(a)(())(bb) К>(a)()()b(b) К>(a)()()(bb)
Задачка на динамическое программирование. Просто немного изменили setting, суть- найти все возможные пути в графе.
Здравствуйте, Тёмчик, Вы писали:
Тё>Задачка на динамическое программирование. Просто немного изменили setting, суть- найти все возможные пути в графе.
Вот задачка на динамическое программирование
дано Aij, bi
y[i] = sum(A[i,j]*x[j],j=1..n) + b[i] , i=1..n
y[i]>=0, x[i]>= 0
найти x[i],y[i]
А тут просто перебор всех вариантов без повторов. Задачка чтоб мозг размять Ваше то решение-то где?
Здравствуйте, kov_serg, Вы писали:
_>А тут просто перебор всех вариантов без повторов. Задачка чтоб мозг размять Ваше то решение-то где?
Просто перебор всех вариантов без повторов- это и есть задача на дин. программирование. Попробуй перебрать, чтобы не получился комбинаторный взрыв.
Я указал направление, дальше лень. Подобная задача была на тесте, по результатам которого пригласили на собеседование и потом сделали оффер.
Здравствуйте, Тёмчик, Вы писали:
Тё>Здравствуйте, kov_serg, Вы писали:
_>>А тут просто перебор всех вариантов без повторов. Задачка чтоб мозг размять Ваше то решение-то где?
Тё>Просто перебор всех вариантов без повторов- это и есть задача на дин. программирование. Попробуй перебрать, чтобы не получился комбинаторный взрыв. Тё>Я указал направление, дальше лень. Подобная задача была на тесте, по результатам которого пригласили на собеседование и потом сделали оффер.
Дык уже http://ideone.com/C4L2Cu можно даже на две части раздели по левым и по правым общее кол-во их произведение.