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

← →
Ske4er (2004-03-01 02:02) [0]

Я пытался найти ответ, но на сайтах с алгоритмами такого нет (или я не нашел) а на сайтах про комбинаторику есть только формулы для вычисления колличества. Конкретнее: Как получить все сочетания элементом массива? Порядок не имеет значения. Т.е. есть массив, допустим 3 элемента:
1
2
3
12
13
23
123

Это легко, но если их больше 5, то нужен работающий алгоритм. Как я и сказал, на сайтах по теории вероятности и комбинаторики есть только определения и формулы для вычесления количества таких сочетаний (и то порядок имеет значение) и все :(. Помогите плиз, может у кого есть пример? А то на Королевстве Дельфи был 1-н такой вопрос, году этак в 1999, но ответ приблизительно такой: напиши мне на мыло, я тебе скину. Автор и тот, кто ответил, не отвечают...

← →
Defunct (2004-03-01 02:15) [1]

На помощь придет рекурсия.
Это задачка максимум на пол-часа.

Тока в условии Вы запутались, раз уж 3 элемента в массиве, то и сочетаниями будут:

123
132
213
231
312
321

← →
kaif (2004-03-01 02:56) [2]

Видимо автор вопроса считает сочетания 123 и 132 идентичными. И я думаю он прав. Принцип "обхода" мне видится таким: сначала ищутся сочетания первого эелемента с остальными, затем первый исключается и ищутся сочетания второго с остальными и так далее. Так мы собираем все неповторяющиеся сочетания в виде "пар". Затем мы можем подумать, как собирать "тройки". Важно не собрать тройку вида 111 или 112 или 121. То есть нужно придумать, как добиться того, чтобы тройки состояли опять-таки из неповторяющихся элементов. С парами было просто. Мы исключали тот элемент, скоторым уже найдены все сочетания из цикла:
и сборка пар выглядела так:

for i := 1 to N do
for j := i + 1 to N do
<добавление в список пар A[i] и A[j]>

Как выбрать тройки?... Да, неприятно...
...Но видимо проще сначала вообще решить, какого типа сочетания будут набираться. Если у нас три исходных элемента, то возможно "одиночки","пары" и "тройки". Если у нас пять исходных элементов, то самое длинное сочетание - "пятерка". Причем она одна (!). Может можно от этого плясать. Вниз. Я просто рассуждаю... Итак у нас имеется, скажем 11 элементов. Сначала собираем все 11 в одно сочетание. Затем собираем 11 сочетаний, из которых исключен 1 элемент ("десятки"). Затем собираем "девятки". Сколько их и как их собрать? Нужно обойти имеющиеся "десятки" и исключить из них по одному элементу. В результате имеем 11*10 таких групп... Затем обойти каждую полученную "девятку" и исключить из нее по одному элементу, чтобы получить все возможные восьмерки (11*10*9)... Я бы применил рекурсию... Но здесь важно придумать красивый способ, как заведомо исключать "одинаковые". что-то подобное мы придумали в самом начале, когда разрабатывали алгоритм для находнения пар...
Одним словом, если просто наивно порассуждать на бумаге, мне кажется, что алгоритм вырисуется максимум через пол-часа... Просто нужно идти в рассуждениях от самой динной (и единственной группы) к более мелким постепенно, пока не дойдем до 11 групп из 1 элемента. И при этом найти способ исключать повторяющиеся группы. Это главное.
Ведь если из группы 12345678 выбросить 1, а из группы 23456789 выбросить 9, то получим одну и ту же группу 2345678. Нужно подумать, как избегать именно этого на каждом этапе... Можно, конечно, сначала все тупо перебрать, а затем одинаковые выбросить... Но это плохой алгоритм. Так каждый дурак может. Барон любит, чтобы было потруднее...

← →
Ske4er (2004-03-01 03:52) [3]

2Defunct
Спасибо, просто видимо сочетания не то слово, скорее комбинации. Насколько помню, в матиматике такое обозначалось как Р(х), где х это set. Т.е при x=(a,b,c), P(x)={{abc},{ab},{ac},..., {пустое множество}}.

2kaif
Огронейшее спасибо! Поверте, на бумаге я потратил не полчаса! :) Пробовал по разному, но ошибка была одна: начинал не сверху, а снизу. Поэтому после 4 элемента запутывался ОЧЕНЬ глубоко, а попробовав сейчас начать не 1, а 12345 все прекрасно получилось. Еще раз спасибо!

← →
Ske4er (2004-03-01 03:53) [4]

Забыл: Ветка закрыта :)

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