Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2004.03.14;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2004.03.14;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.46 MB
Время: 0.014 c
14-43894
RealRascal
2004-02-16 06:22
2004.03.14
Идеи...


14-43770
Думкин
2004-02-19 06:13
2004.03.14
С днем рождения! 19 февраля.


1-43512
Алексей
2004-01-23 13:21
2004.03.14
вопрос по EditChange


1-43574
Delph
2004-02-27 16:29
2004.03.14
Alignment и TEdit


3-43329
BlackTiger
2004-02-17 16:48
2004.03.14
Как сделать аналог





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский