Гость
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Быстрый алгоритм для математической задачи / 25 сообщений из 26, страница 1 из 2
02.04.2015, 01:29
    #38924371
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Здравствуйте.

Прошу помощи в решении задачи с математическим уклоном.

Дано: A – последовательность значений, N – количество.
Найти: все группы из N элементов последовательности A; порядок элементов в группе должен совпадать c последовательностью A.

Например: A = (1, 2, 3, 4), N = 3. Ответ – 4 группы: 123, 234, 124, 134.

Решение нашел, но медленное. Сделал перебор всех вариантов через двоичные числа. Скорость никакая, если значений много. Например, если в последовательности 1000 элементов, а N = 10, то очень медленно.

Надеюсь, математики подскажут правильный подход.
...
Рейтинг: 0 / 0
02.04.2015, 09:10
    #38924466
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Сын вождяНапример, если в последовательности 1000 элементов, а N = 10, то очень медленно.Ну да, всего-то ~3*10^23 вариантов. И чё оно тормозит, непонятно...
...
Рейтинг: 0 / 0
02.04.2015, 09:29
    #38924499
Казанский
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Даже больше, =ПЕРЕСТ(1000;10) дает 9,56E+29. А перебор обычно рекурсией делается.
...
Рейтинг: 0 / 0
02.04.2015, 09:34
    #38924503
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Akina...всего-то ~3*10^23 вариантов...
Я как раз об этом :( Мой алгоритм, кроме искомых вариантов, перебирает кучу мусорных. Это тормозит еще больше. Ломаю голову, как перебирать только искомые варианты. Если это невозможно, то придется менять концепцию.
...
Рейтинг: 0 / 0
02.04.2015, 09:51
    #38924524
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Казанский=ПЕРЕСТ
=ПЕРЕСТ(4; 3) выдает 24. Что неверно, для моей задачи. Правильный ответ - 4 варианта.
Не пользовался функцией ПЕРЕСТ. В ее описании сказано, что учитывается порядок. Не понял как.
...
Рейтинг: 0 / 0
02.04.2015, 10:04
    #38924549
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
КазанскийДаже большеУ него не перестановки, а сочетания - требуется сохранять относительное местоположение элементов.
...
Рейтинг: 0 / 0
02.04.2015, 10:08
    #38924555
Казанский
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Да, я ошибся, это ЧИСЛКОМБ(4;3)=4, а ЧИСЛКОМБ(100;10)=1,73E+13
...
Рейтинг: 0 / 0
02.04.2015, 10:12
    #38924561
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Сын вождякак перебирать только искомые варианты
Имхо наиболее разумный вариант - рекурсивный. Схематично где-то так:

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
public elements()
public fin_len
' ...
sub recurs(cur_substr, cur_pos)
if ubound(elements)-len(cur_substr) < fin_len-cur_pos then exit sub 
if len(cur_substr)=fin_len then then print cur_substr:exit sub 
for i = cur_pos+1 to ubound(elements)
  call recurs(cur_substr & elements(i), i) 
next i
end sub
' ...
call recurs("", 0)
' ...
...
Рейтинг: 0 / 0
02.04.2015, 10:14
    #38924565
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
КазанскийДа, я ошибся, это ЧИСЛКОМБ(4;3)=4, а ЧИСЛКОМБ(100;10)=1,73E+13У него не 100, а 1000. Так что ещё 10 порядков добавь...
...
Рейтинг: 0 / 0
02.04.2015, 10:18
    #38924571
Казанский
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Да... чет не мой день сегодня... пойду домашние дела делать )
...
Рейтинг: 0 / 0
02.04.2015, 10:25
    #38924585
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Akina...где-то так...
Благодарю. Буду разбираться...
Akina...не 100, а 1000. Так что ещё 10 порядков добавь...
По жизни, число элементов в группе будет близко к общему числу элементов. Для 1000 - от 900, для 100 - от 80...
...
Рейтинг: 0 / 0
02.04.2015, 10:31
    #38924595
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
О скорости.

Вот тест-код:

Код: vbnet
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.
Public elements() As String
Public fin_len As Integer

Sub recurs(cur_substr As String, cur_pos As Integer)
Dim i As Integer
If UBound(elements) - Len(cur_substr) < fin_len - cur_pos Then
    Exit Sub
End If
If Len(cur_substr) = fin_len Then
    'Debug.Print cur_substr
    Exit Sub
End If
For i = cur_pos + 1 To UBound(elements)
  Call recurs(cur_substr & elements(i), i)
Next i
End Sub

Sub test()
Dim i As Integer, cnt As Integer
For cnt = 11 To 30
    ReDim elements(1 To cnt)
    For i = 1 To cnt
        elements(i) = "1"
    Next i
    fin_len = 10
    t = Timer
    Call recurs("", 0)
    Debug.Print cnt, fin_len, Timer - t
Next cnt
End Sub


Среда - Excel 2007, проц Е2160 (1,8ГГц). И вывод:
cnt i dTime 11 10 0 12 10 0 13 10 3.90625E-03 14 10 0.0078125 15 10 0.015625 16 10 2.734375E-02 17 10 5.078125E-02 18 10 0.09375 19 10 0.1601563 20 10 0.28125 21 10 0.4726563 22 10 0.7695313 23 10 1.25 24 10 1.972656 25 10 3.082031 26 10 4.707031 27 10 7.089844 28 10 10.48047 29 10 15.42969 30 10 22.19531
Так что 100,10, а тем более 1000,10 я бы запускать не стал...
...
Рейтинг: 0 / 0
02.04.2015, 10:32
    #38924596
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Да и 100,80 - тоже... тем более 1000,900.
...
Рейтинг: 0 / 0
02.04.2015, 10:44
    #38924614
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
AkinaДа и 100,80 - тоже... тем более 1000,900.
Да, я уже глянул число комбинаций :( Оптимизация этого алгоритма - почти глухой номер. Благодарю, просветили :)
...
Рейтинг: 0 / 0
02.04.2015, 10:49
    #38924622
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Сын вождяДа, я уже глянул число комбинаций :( Оптимизация этого алгоритма - почти глухой номер.
Это говорит о неправильном подходе. Не проведён предварительный анализ и не определены дополнительные условия отсечения. Перебор же (любой!) - это тупик, тогда как при правильных доп. ограничениях и бОльшие количества обрабатываются за вменяемое время.
...
Рейтинг: 0 / 0
04.04.2015, 22:54
    #38927191
Михаил Ч.
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Какова конечная задача? Может найдутся другие алгоритмы, а не полный перебор всех сочетаний?
...
Рейтинг: 0 / 0
05.04.2015, 05:48
    #38927263
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Задача: найти похожие параграфы в Word.

Видел готовые решения для сравнения строк. Правда адаптации для Word не встречал. Изучил предлагаемые алгоритмы. Но интересно же сделать самому :) Да и в Word и в его макросах есть своя специфика.

Планировал этот алгоритм использовать для побуквенного сравнения. Но так даже два параграфа не сравнить :)
Попробую сделать через отсев, ну и сравнивать надо без перебора - одним проходом.
...
Рейтинг: 0 / 0
05.04.2015, 09:45
    #38927282
uux
uux
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Сын вождяЗадача: найти похожие параграфы в Word.

Видел готовые решения для сравнения строк. Правда адаптации для Word не встречал. Изучил предлагаемые алгоритмы. Но интересно же сделать самому :) Да и в Word и в его макросах есть своя специфика.

Планировал этот алгоритм использовать для побуквенного сравнения. Но так даже два параграфа не сравнить :)
Попробую сделать через отсев, ну и сравнивать надо без перебора - одним проходом.

А каковы критерии похожести? С этого надо ИМХО начинать решение задачи:).

И в качестве бредовой идеи в рамках мозгового штурма - брать два параграфа, переводить в один регистр, убирать знаки препинания, обеспечить разделение слов одиночными пробелами, выгружать в текстовые файлы, обрабатывать эти файлы встроенной shell'овской утилитой fc (file compare) и затем анализировать результаты ее работы.
...
Рейтинг: 0 / 0
05.04.2015, 10:39
    #38927292
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
uuxА каковы критерии похожести? С этого надо ИМХО начинать решение задачи:)
Я и не ставил сразу такую задачу :)
Похожими считаем строки, которые отличаются определенным числом знаков. То есть: одни знаки заменены другими, вставлены лишние знаки, удалены отдельные знаки.
uux...брать два параграфа, переводить в один регистр, убирать знаки препинания, обеспечить разделение слов одиночными пробелами...
Это уже реализовал. Сейчас пытаюсь оптимизировать сравнение двух строк.
uux...выгружать в текстовые файлы, обрабатывать эти файлы встроенной shell'овской утилитой fc (file compare) и затем анализировать результаты ее работы.
Почитал про Diff. Алгоритм как раз такой, какой нужен. Только задача найти похожие абзацы для каждого абзаца документа. Значит, придется в цикле обрабатывать связку:
файл1 - все абзацы документа, очищенные от мусора;
файл2 - текущий проверяемый абзац, размноженный до количества абзацев в файл1, чтобы сравнить его со всеми.
...
Рейтинг: 0 / 0
05.04.2015, 10:58
    #38927299
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Если по науке, то хочу написать макрос вычисления наибольшей общей подпоследовательности для двух строк.
...
Рейтинг: 0 / 0
05.04.2015, 11:01
    #38927300
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Этап полного перебора уже прошел :) Перешел к методу динамического программирования :)
...
Рейтинг: 0 / 0
05.04.2015, 11:05
    #38927301
Shocker.Pro
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Сын вождяПохожими считаем строки, которые отличаются определенным числом знаковя в свое время делал такой алгоритм сравнения строк (искал в прайс-листе совпадающие товары, написанные иначе, в том числе с перестановкой слов):

сравниваемые строки сжимались (удалялись пробелы и спецсимволы, в случае литературного текста имеет смысл удалить знаки препинания или вообще только буквы оставить)

исходная строка разбивалась на перекрывающиеся тройки символов, то есть для строки
Код: plaintext
"фывапро"
разбивка была
Код: plaintext
"фыв","ыва","вап","про"

каждая тройка искалась во второй строке

вычислялся коэффициент попадания (полностью одинаковые строки давали 1, отсутствие совпадений троек - 0)

алгоритм не очень быстрый, но скорости хватало
...
Рейтинг: 0 / 0
05.04.2015, 13:19
    #38927371
fixxer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Идея с триграммами правильная. Возможно для абзацев стоит делать триграмы по словам. Далее триграмы нужно прохешировать и построить минхеши чтобы вычислить похожесть.
...
Рейтинг: 0 / 0
05.04.2015, 13:24
    #38927372
Shocker.Pro
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
fixxerИдея с триграммами правильнаяспасибо, это была полностью моя собственная идея зеленого еще программиста, в изучение существующих математические методов я тогда не полез, да и интернет был еще молод )))
...
Рейтинг: 0 / 0
06.04.2015, 10:35
    #38927776
Сын вождя
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм для математической задачи
Пока остановился на таком алгоритме:

1. Первый этап - ищу пару абзацев с похожими наборами знаков. Например, "1234" и "4321".

2. Второй этап - для найденной пары, вычисляю максимальную общую последовательность знаков. Наример, для "1234" и "4123" это "123".

Довольно быстро работает, по сровнению с начальным вариантом :)
...
Рейтинг: 0 / 0
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Быстрый алгоритм для математической задачи / 25 сообщений из 26, страница 1 из 2
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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