Помогите с комбинаторикой

← →
Труп Васи Доброго © (2008-11-27 15:45) [0]

Всем привет!
Попалась задача выбрать из массива элементов неповторяющиеся тройки, то есть просто выбрать все сочетания из N элементов по 3.
Пытался придумать как обеспечить неповторяемость... в голову лезли только громоздкие и поэтому пугающие трёхэтажные проверки.
Может кто сталкивался с такой задачей, подскажите умную мысль.

← →
Юрий Зотов © (2008-11-27 15:56) [1]

Тип элементов массива?

← →
Труп Васи Доброго © (2008-11-27 15:59) [2]

> [1] Юрий Зотов © (27.11.08 15:56)
> Тип элементов массива?

ТРoint, да какая разница??? Главное чтобы если выбраны (A[1],A[20],A[45]) не выбирались бы (A[20],A[1],A[45]), (A[1],A[45],A[20]) и т.д.

← →
Palladin © (2008-11-27 16:04) [3]

For i:=0 to N-1 Do
For j:=i+1 to N-1 Do
For k:=j+1 to N-1 Do
(A[i],A[j],A[K])

← →
Труп Васи Доброго © (2008-11-27 16:17) [4]

> [3] Palladin © (27.11.08 16:04)

Вот рука мастера! Всё гениальное - просто! Крутилась ведь мыслишка рядом, но вот до i+1 и j+1 не дотянул. Старый видать совсем стал ... пора думать об отдыхе, а не контрольные решать :)

← →
b z (2008-11-27 16:32) [5]

Тут вот есть http://www.codeproject.com/KB/recipes/Combinatorics.aspx, правда с#, может пригодится. :)

← →
TUser © (2008-11-27 20:19) [6]

держи ище на копейку быстрее

For i:=2 to N-1 Do
For j:=1 to i-1 Do
For k:=0 to j-1 Do
(A[i],A[j],A[K])

← →
uw © (2008-11-28 00:28) [7]

А что будет, если в массиве повторяющиеся элементы?
Я бы отсортировал то, что получилось у Палладина, и быбросил повторяющиеся тройки.

← →
Труп Васи Доброго © (2008-11-28 00:42) [8]

> А что будет, если в массиве повторяющиеся элементы?

Повторяющихся не бывает по условию задачи.
Есть массив точек, надо найти все тройки точек, образующие прямоугольные треугольники. Вот чтобы один и тот же треугольник три раза не находить мне и нужно было выбрать сочетания из N по 3 без повторов. Решение Палладина помогло, задача решена. Всем спасибо!

Труп Васи Доброго © (28.11.08 00:42) [8]
Повторяющихся не бывает по условию задачи.
Есть массив точек,

А если в массиве точек есть повторяющиеся точки?

> А если в массиве точек есть повторяющиеся точки?

Скажи, вот чисто физически (да хоть геометрически) как на плоскости могут быть две разные точки с одинаковыми координатами??? Геометрия говорит что это одна точка и я склонен ей верить.
К тому же я сказал - их нет ПО УСЛОВИЮ ЗАДАЧИ!
Соответственно я не буду делать плавающий велосипед, если он НИКОГДА не будет использоваться на воде.

Да я же не против, если по условию задачи все точки разные! Но ведь сначала ты говорил про массив элементов. Как можно было понять, что это точки? Потом ты сказал, что это массив точек. Как можно было понять, что в массиве точки все разные. Теперь ты говоришь про "чисто физически"... Я не против :)

Помогите с комбинаторикой Найти похожие ветки