Помогите ускорить алгоритм

← →
madmech © (2008-12-05 17:38) [0]

Некоторое время назад я задал вопрос на другом форуме:

И частично проблема мной была решена, но теперь возникла новая загвоздка - надо ускорить алгоритм. Описываю суть:

Добрый день, дамы и господа! Некоторое время назад я задавал вопрос по поводу комплектования малых подгрупп. Задачу выполнил с помощью [b]pva[/b] и используя данный алгоритм (функция формирования перестановок):
http://algolist.manual.ru/maths/combinat/permutations.php

Но! Дело в том, что при количестве людей большем 12, алгоритм перебора начинает захлебываться, то есть жутко тормозить или зависать. Поэтому встает вопрос: как можно ускорить процесс? Вкратце опишу суть того, что я делаю: формирую всевозможные перестановки N людей. На определенном шаге отсекаю все варианты, начинающиеся с 2.
Варианты, начинающиеся с 3, 4 и т.д. уходят автоматически. Таким образом, количество перестановок резко сокращается. На каждом шаге формирования перестановки я осуществляю проверку на невозрастание внутри подгруппы и невозрастание первых людей подгрупп в соотвествии с алгоритмом, предложенным [b]pva[/b], . Если все ОК, то записываю перестановку в поток (TStream). После записи всех "правильных" перестановок (c учетом подгрупп) в поток
я считываю данные из потока в ClientDataSet и далее они автоматически переносятся в DBGrid.
Понятно, что промежуточные звенья (TStream и ClientDataSet) значительно тормозят процесс, но даже если
их отключить и оставить алгоритм формирования перестановок работающим "вхолостую", то процесс все равно захлебывается. Что делать? Как выкрутиться из этой непростой ситуации?

← →
madmech © (2008-12-05 17:41) [1]

Забыл указать адрес того форума, чтобы было понятно, о чем идет речь:
http://forum.oszone.net/post-973199.html#post973199
:)

← →
Jeer © (2008-12-05 17:43) [2]

Мозг с мыслями приведи в порядок - потом еще раз попробуй.
Зайти, типа.

← →
MBo © (2008-12-05 17:47) [3]

А на алголисте я тебе говорил, что нужно не перестановки, а сочетания генерировать. Зря не прислушался.
Однако для больших чисел все равно наборов будет дофигища...

← →
madmech © (2008-12-05 17:47) [4]

Не понял, поясни.
Изначальная проблема описана на том форуме, лень здесь по второму кругу писать, так что милости прошу пройти по сцылке.

← →
Leonid Troyanovsky © (2008-12-05 17:55) [5]

> madmech © (05.12.08 17:47) [4]

> Не понял, поясни.

Поясняю.

Если проблем уж обсуждался, изволь привести, скажем, резюм.
Чтоб всем нам не бродить по неким ссылкам.
У нас и своих проблем хватает.

--
Regards, LVT.

Предыдущий пост относился к Jeer.)
MBo, проблема в том, что у меня есть функция, формирующая сочетания из N элементов, то есть элементы берутся от 1 до N. А как сформировать, например, все возможные сочетания из 3, 5, 6? Из 1, 2, 3 я могу. А тут затрудняюсь. Поэтому и решил реализовывать задачу через перестановки.
Еще раз поясню: там, на Алголисте, ты мне предложил реализовывать так:
фиксируем 1, далее из оставшихся элементов формируем все сочетания, то бишь 2..N. С этим у меня трудности.

Leonid Troyanovsky, special for you and Jeer привожу еще раз формулировку задачи:
Народ, подскажите, пожалуйста, как лучше создать и реализовать алгоритм. Может быть, кто-то уже сталкивался с подобной комбинаторной задачей. Суть в следующем: есть N людей в группе. Их надо разбить на m подгрупп по k людей в каждой. Например: 16=8x2, или 16=4х4, 15=3х5 и т.д. Передо мной стоит задача вывести на экран все возможные разбиения начальной группы. Формула для количества всевозможных вариантов (I) мной уже выведена. Выглядеть это должно примерно следующим образом (выводим в StringGrid или в DBGrid):

Разбиение 8=2х4:
_____________________________
| № | Подгруппа 1 | Подгруппа 2 |
-----------------------------------------------
| 1 | (1, 2, 3, 4) | (5, 6, 7, 8) |
| 2 | (1, 5, 3, 4) | (2, 6, 7, 8) |
| 3 | (1, 2, 5, 4) | (3, 6, 7, 8) |

| 35 | (1, 3, 5, 6) | (2, 4, 7, 8) |
----------------------------------------------|

Всего для данного конкретного разбиения существует 35 вариантов.

Как не сложно догадаться есть некоторые ограничения, значительно усложняющие на первый взгляд простенькую задачу:
1. Перестановки внутри подгруппы нас не интересуют, то есть: (1, 2, 3, 4) = (2, 1, 3, 4)
2. Перестановки подгрупп между собой тоже: [(1, 2), (3, 4)] = [(3, 4), (1, 2)]
3. Один и тот же человек не может входить сразу в две подгруппы, например: [(1, 2), (1, 3)]

Я решил для себя, что задачу проще всего будет организовать через трехмерный массив, где заполнение элементов будет осуществляться через 3 цикла (по количеству людей в подгруппе (1..k), по количеству подгрупп (1..m) и по количеству всевозможных вариантов (1..I)). Или, если быть точным, нужно составить двумерную матрицу, элементами которой являются одномерные массивы-строки (состав подгруппы). А потом полученные элементы "внешнего" массива я запишу в DBGrid, как показано в таблице.

Пояснение-резюме: человек на том форуме предложил сформировать все возможные перестановки и отобрать из них часть с учетом формирования подгрупп для дальнейшего занесения в ClientDataSet. Вкратце:
1. Люди внутри подгруппы должны быть выстроены по возрастанию.
2. Первые номера подгрупп так же должны быть выстроены по возрастанию.

> сформировать все возможные перестановки

излишне.
вполне алгоритмуется только необходимое.

> Изначальная проблема описана на том форуме, лень здесь по
> второму кругу писать, так что милости прошу пройти по сцылке.

Тебе лень, а нам лень ходить по ссылкам, лучше ты сам туда иди.

Помогите ускорить алгоритм Найти похожие ветки