powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Быстрый алгоритм для математической задачи
26 сообщений из 26, показаны все 2 страниц
Быстрый алгоритм для математической задачи
    #38924371
Фотография Сын вождя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.

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

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

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

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

Надеюсь, математики подскажут правильный подход.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924466
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сын вождяНапример, если в последовательности 1000 элементов, а N = 10, то очень медленно.Ну да, всего-то ~3*10^23 вариантов. И чё оно тормозит, непонятно...
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924499
Казанский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Даже больше, =ПЕРЕСТ(1000;10) дает 9,56E+29. А перебор обычно рекурсией делается.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924503
Фотография Сын вождя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Akina...всего-то ~3*10^23 вариантов...
Я как раз об этом :( Мой алгоритм, кроме искомых вариантов, перебирает кучу мусорных. Это тормозит еще больше. Ломаю голову, как перебирать только искомые варианты. Если это невозможно, то придется менять концепцию.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924524
Фотография Сын вождя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Казанский=ПЕРЕСТ
=ПЕРЕСТ(4; 3) выдает 24. Что неверно, для моей задачи. Правильный ответ - 4 варианта.
Не пользовался функцией ПЕРЕСТ. В ее описании сказано, что учитывается порядок. Не понял как.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924549
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
КазанскийДаже большеУ него не перестановки, а сочетания - требуется сохранять относительное местоположение элементов.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924555
Казанский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Да, я ошибся, это ЧИСЛКОМБ(4;3)=4, а ЧИСЛКОМБ(100;10)=1,73E+13
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #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
Быстрый алгоритм для математической задачи
    #38924565
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
КазанскийДа, я ошибся, это ЧИСЛКОМБ(4;3)=4, а ЧИСЛКОМБ(100;10)=1,73E+13У него не 100, а 1000. Так что ещё 10 порядков добавь...
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924571
Казанский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Да... чет не мой день сегодня... пойду домашние дела делать )
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924585
Фотография Сын вождя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Akina...где-то так...
Благодарю. Буду разбираться...
Akina...не 100, а 1000. Так что ещё 10 порядков добавь...
По жизни, число элементов в группе будет близко к общему числу элементов. Для 1000 - от 900, для 100 - от 80...
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #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
Быстрый алгоритм для математической задачи
    #38924596
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да и 100,80 - тоже... тем более 1000,900.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924614
Фотография Сын вождя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AkinaДа и 100,80 - тоже... тем более 1000,900.
Да, я уже глянул число комбинаций :( Оптимизация этого алгоритма - почти глухой номер. Благодарю, просветили :)
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38924622
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сын вождяДа, я уже глянул число комбинаций :( Оптимизация этого алгоритма - почти глухой номер.
Это говорит о неправильном подходе. Не проведён предварительный анализ и не определены дополнительные условия отсечения. Перебор же (любой!) - это тупик, тогда как при правильных доп. ограничениях и бОльшие количества обрабатываются за вменяемое время.
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38927191
Михаил Ч.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Какова конечная задача? Может найдутся другие алгоритмы, а не полный перебор всех сочетаний?
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38927263
Фотография Сын вождя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задача: найти похожие параграфы в Word.

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

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

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

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

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

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

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

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

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

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

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

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

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

Довольно быстро работает, по сровнению с начальным вариантом :)
...
Рейтинг: 0 / 0
Быстрый алгоритм для математической задачи
    #38927780
Фотография Shocker.Pro
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Защита от плагиата?

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


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