Разбиения множества

Добрый вечер.
У меня есть множество точек в трехмерном пространстве, которые я считала и занесла в двухмерный массив. Задача состоит в том, чтобы рассмотреть все разбиения этого множества на два и сравнить их центры тяжести. Но как сравнить я знаю, а вот как разбить понятия не имею.
Например, если у меня три точки, то должно получится три варианта разбиения. Программирую на Си.

0

Логическая схема:
Перебираем все числа m от 1 до n-1, где n -- количество точек
Для каждого m перебираем все комбинации из m точек таким образом:
Перебираем все точки, и для каждой из них комбинации из m-1 точки (рекурсия).
Итого, получили разбиение на m и n-m точек

0

Сообщение от UFO94 Перебираем все точки, и для каждой из них комбинации из m-1 точки (рекурсия).

Вот это не совсем понятно...

0

В каком виде вы собираетесь хранить комбинацию?

0

UFO94, в итоге мне нужно будет вывести номера точек первого и второго множества. Но можно вывести и координаты самих точек, что мне кажется более проблематично.

0

Можно и номера. Тогда это выглядит так:
Вроде так. Компилировать не пробовал, экспромт, потому очень удивлюсь, если будет работать без ошибок. Пробуйте, пишите, будем разбираться.
Ах, и да, что пишем в основной программе:
И есть одна проблемма, если n -- четное, то каждое разбиение пополам будет считаться дважды. Не знаю, как это исправить...

0

UFO94, я вот тут подумала, что можно было бы комбинировать не целые точки, а массы этих точек, а потом просто в принтф писать номера строк массива с точками, которые будут совпадать с номерами масс.

0

Если вы собираетесь рассмотреть все возможные комбинации, то это одно и то же.

0

UFO94, нет. Мне нужно найти разбиение на два множества, расстояние между центрами масс которых минимальное.
Просто как сделать так, чтобы он сам перебрал все варианты?

0

Ну, мой алгоритм и будет перебирать все варианты. Придеться ввести глобальные переменные "расстояние" и "разбиение", и все ок.

0

UFO94, Ваш алгоритм кажется мне каким-то сложным %) Я думала, что через for можно как-то сделать

0

Тогда для каждого m прийдется писать свою функцию. Т.е., у нас например 10 точек. Для выбора 1 точки пишем 1 for. Для 2-х точек -- 2. Для 5 точек пожалуйте 5 for'ов. Здесь без рекурсии ну никак не обойтись. Другое дело, что, возможно, это не самый рациональный алгоритм... По крайней мере, по использованию памяти. Он использует m(m+1)*sizeof(int)/2 памяти, что при m=23 составляет больше мегабайта оперативной памяти.

0

UFO94, а можете тогда еще раз объяснить рекурсию, пожалуйста.

0

Рекурсивная функция -- функция, вызывающая саму себя. Как это в данном случае работает:
мы перебираем по очереди точки (т.е. выбираем 1 точку), а потом сводим задачу к предидущей -- теперь нам нужно выбрать m-1 точку из принципиально возможных n-1. Когда мы выбрали все нужные нам m точек (условие m1==m, это т.н. "выход из рекурсии"), мы уже получили разбиение -- одна группа точек -- те точки, чьи номера входят в массив num, вторая -- те, чьи номера туда не входят.
Есть 2 тонких момента во всем этом. Во первых, нам нету смысла расматривать такие разбиения, которые отличаются только порядком выбора точек (например разбиение с выбраным на первом шаге номером 1, на втором -- 2, на третьем -- 3, и разбиение с выбраным на первом шаге номером 2, на втором -- 3, и на третьем -- 1 для нас одинаковы (разбиения [1;2;3] и [2;3;1])). Потому имеет смысл каждую точку выбирать не из всех еще не вошедших в наш массив, а из тех, у которых номер больше номера последней точки. Таким образом, массив num получается отсортированным по нарастанию. Также очевидно, что если нам нужно выбрать 3 точки из 10, то выбрав на первом шаге точку №9 мы уже никак не сможем выбрать еще 2 точки с большими номерами, потому мы выбираем точки не от последней выбраной до последней вообще, а от последней выбраной до n-m+m1+1. И еще 1 момент, нам надо как-то начать этот рекурсивный процесс. За начало отвечает условие if(m1==0) и то, что там внутри. Кстати, я придумал лучший способ использования памяти, для этого в функции grouping:
--Убираем строки 7,10,22-24,27
--В строках 8,9,25,26 меняем num1 на num.
В вызове из основной программы:
-- в четвертой строке 1 меняем на i.
И алгоритм будет жрать память как корень квадратный из того, что жрал раньше

1

Сообщение от UFO94 Когда мы выбрали все нужные нам m точек (условие m1==m

То есть чтобы он перебрал все варианты комбинаций точек нужно еще на это цикл наложить?

А не проще будет все-таки комбинировать массы точек, а потом уже сопоставлять с точками?

0

Сообщение от ejk То есть чтобы он перебрал все варианты комбинаций точек нужно еще на это цикл наложить?

Нужен цикл в основной программе и в нем вызов функции grouping. Ну, я приводил этот кусок кода.

Сообщение от ejk комбинировать массы точек

А что вы имеете в виду под комбинированием масс?

0

Сообщение от UFO94 вызов функции grouping

Мы эту функцию вообще не затрагивали Я понятия не имею, что это.

0

Вообще-то, это та функция, которую я написал. На первой странице, сообщение номер 6, там сначала функция grouping, потом ее вызов из основной программы

0

Сообщение от UFO94 А что вы имеете в виду под комбинированием масс?

У меня для каждой точки задана ее масса и основной целью является найти разбиение точек на два подмножества, чтобы расстояния между центрами тяжести были минимальны. Вот я и подумала, что комбинировать массы проще, чем точки.
Еще можно создать один цикл фор, где просто перебираются точки, как будто шарики из мешка. Но там мне еще посоветовали рэндом засунуть

Добавлено через 38 секунд

Сообщение от UFO94 там сначала функция grouping

Я помню Ваш код. Эта функция присутствует в языке Си или это как раз и есть рекурсия?

0

Это не стандартная функция в языке С, иначе я бы ее не писал. Рекурсия -- это просто прием вызова функцией самой себя. Например:
Функция нахождения факториала числа n:
{
Если n!=0
Возвращаем n*Факториал(n-1);//Вот он, вызов функции самой из себя. Но нужно этот процесс еще как-то закончить.
Если n==0 возвращаем 1;// 0! по определению равен 1
}

Сообщение от ejk комбинировать массы

Просто напишите, чисто логически, как вы это представляете.

Сообщение от ejk цикл фор, где просто перебираются точки, как будто шарики из мешка

Если бы нам нужно было выбрать 1 точку, то был бы просто цикл for. Но нам нужно много точек, потому циклом for принципиально можно, но уж очень муторно.

Сообщение от ejk рэндом засунуть

ИМХО, плохая идея. Так мы можем и не перебрать все комбинации, либо очень долго их перебирать. Львиную часть времени рендом будет обрабатывать уже пройденые нами варианты.

0