Подскажите, пожалуйста, алгоритм поиска возможных комбинаций

[wrangels]

В общем есть такая задача.
Есть массив случайных целых чисел
 14 15 22 11 17
Дано число N,
Требуется в массиве найдти, все возожные варианты комплектов N

Допустим N равно 3, нужно найдти все возможных варианты
 ( Позиции цифр в нутри варианта не играет роли , главное найти все варианты наборов N чисел)
 список будет таким
14 15 22 11 17

14 15 22
14 15 11
14 15 17
14 22 11
14 22 17
14 11 17
15 22 11
15 22 17
15 11 17

 Подскажите пожалуйста , алгоритм поиска таких кобинаций, Плиизз

[Sla]

а что по этому поводу говорит теория?
сочетания? комбинации?
алгоритма нет, есть формула
Нет формулы - есть учебник (основы теории вероятности)

[wrangels]

Не пойму причем тут теория вероятности?
Нужны кобинаци из N цифр

[Джон]

Слава имел ввиду комбинаторику. Иногда её рассматривают как часть теории вероятности.

На самом деле всё очень просто. Кстати у тебя могут числа повторяться? например 14 15 22 11 17 15
Скорей всего нет. Ну да ладно.

Итак, в самом общем случае формула очень простая:

а в степени n   a^n, где а - база, n - число разрядов (совпадает с твоим N)

например у тебя есть последовательность 0 1 - всего два числа (а=2), ты хочешь узнать число комбинаций для n=4

те 2^4=16 всевозможных комбинаций от 0000 до 1111

0000
0001
0010
0011
...
1101
1110
1110

Знакомо? До боли.

в твоём случае база равна пяти - пять отличных друг от друга чисел, число разрядов - 3
те 5^3=125

Тебе остаётся только ввести дополнительные ограничения на повторяющиеся комбинации, если того требуют условия задачи. Например

допустимо ли повторение? 17 17 15 или 15 15 15

допустимы симметричные комбинации? 17 11 15 и 15 11 17

ну и тд

Подсказака - факториал

[Sands]

Судя по описанию задачи, тут надо найти C(k,n)=n!/k!*(n-k)! или я неправильно понял. Опять же одно дело пощитать количество, а совсем друго - писать алгоритм и программу.

[Джон]

Sands, а ты как формулу получил? Они ведь выводятся. Чем не база для алгоритма? В данном случае фразу "подскажите алгоритм" следует понимать как "сделайте за меня". А на это ни у меня, ни у Славы нет ни времени ни желания.

[wrangels]

После штудирования матчасти получилось вот так:

function Facs(n: Integer;n1: Integer): Integer;
    var NN,I1,I2,I3:integer;

  begin

    NN:=1;

for I1:=1 to N-2 do
  begin
for I2:=I1+1 to N-1 do
  begin
for I3:=I2+1 to N  do
begin

RMs1[1,NN]:=RMs[I1];
RMs1[2,NN]:=RMs[I2];
RMs1[3,NN]:=RMs[I3];

sss:=RMs1[1,NN]+RMs1[2,NN]+RMs1[3,NN];
Form1.ListB6.Items.Add(sss);

NN:=NN+1;

END;
END;
END;

end;

Это для фиксированного числа элементов, а мне нужно N. ни как не могу придумать как ?

[wrangels]

C(k,n)=n!/k!*(n-k)!
ты верно понял так и есть это вычисляется количество комбинаций, но мне нужны сами кобинации
Задачка называется "сочетания из N по K элементов"

[Sands]

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

[Джон]

wrangels,  а ты не можешь алгоритм записать. У меня от паскалевского кода, да ещё не форматированого в глазах рябит.

[Sla]

интересно, а рекурсия поможет отцу русской демократии?

[Sands]

Как один из вариантов вполне может подойти.

[Sla]

Sands, там той глубины -совсем ничего - C(k,n)

[Finch]

Я в свое время решал данную проблему так:
Колличество комбинаций ограничено. Значит каждую комбинацию можно пронумеровать от 0 и до n. Теперь самая сложность заключается в том, как по номеру, найти саму требуемую комбинацию

Допустим N равно 3, нужно найдти все возможных варианты
 ( Позиции цифр в нутри варианта не играет роли , главное найти все варианты наборов N чисел)
 список будет таким
14 15 22 11 17

Введем для ясности еше одно обозначение L это количество значений в массиве.

Я решал так
1) Берем номер комбинации и ишем остаток от деления на L, получаем элемент комбинации
2) Данный элемент помечаем, как использованный
3) Делим номер комбинации на L
4) Уменьшаем L на 1
5) Уменьшаем N на 1
6) Если N  больше 0, перейти к пункту 1

[Sands]

Finch, если не секрет, а что делать если мы попадем на уже использованный элемент(к примеру для комбинации №1 остаток от деления 1 на любое число, кроме 1, будет 1)?
Ето просто, чтоб лучше понять. Вообще твой алгоритм выглядит красивою

[Finch]

Sands, Смотри пункт 2 "2) Данный элемент помечаем, как использованный". Использованный элемент исключается как бы из массива. Я лично делал еше один массив флагов, Потом просто в цикле проходил по массиву флагов, и находил элемент, с заданным номером и не используемый. Этот метод хорош для случайного доступа к комбинациям.   

[Sands]

Finch, спасибо. Фактически - это получается рекурсивный алгоритм, только переписанный в итеративной форме Красота!!!

[wrangels]

Бльшое спасибо всем за помощь студенту
в итоге алгоритм получился таким:

Код:

 
procedure omb(Start, N, K: Integer; OldComb: string);
var i:integer;
  NewComb:string;
begin

for i := Start to N-K+1 do begin
  NewComb := OldComb + RMs[i];
  if K = 1 then 
     Form1.ListB6.Items.Add(NewComb)
  else
    omb(i + 1, N, K -1, NewComb)
end;
end;

[RXL]

wrangels, оборачивай код тегами [code]  ...  [/code] - в твоем посте [i] интерпретировалось как italic!

[Finch]

В довершении пьянки

Код:

#include <stdio.h>

#define null 0

/*
	GetKombinat - Функция из набора данных формирует уникальную комбинацию по заданным критериям
    Buf    - Набор данных, которые нужно комбинировать
	Lenght - Длина набора (Lenght>0)
	ResBuf - Набор комбинации
	ResLen - Длина Результируюнего буфера. Должна быть ((ResLen>0) & (ResLen<=Lenght))
	Num    - Номер комбинации (от 0 и до (Lenght!)/(Lenght-ResLen)!) Если будет сверх этого числа, то 
	         функция вернет значение false
    Если комбинация была получена, то функция вернет значение true, иначе false
*/
bool GetKombinat(int *Buf, int Lenght, int *ResBuf, int ResLen, int Num)
{
	bool res=false;
	if ((Buf != null) && (ResBuf != null) && (Lenght>0) && (ResLen>0) && (ResLen<=Lenght) && (Num>=0))
	{
		char *fl=new char[Lenght];
		if (fl !=null)
		{
			for (int i=0; i<Lenght; i++) fl[i]=0;
			int begRes=0;
			int tl;
			int beg;
			int zn;
			while (begRes < ResLen)
			{
				tl=Num % Lenght;
				beg=-1;
				zn=-1;
				while (zn !=tl)
				{
					beg++;
					if (fl[beg]==0) zn++;
				}
				ResBuf[begRes]=Buf[beg];
				fl[beg]=1;
				begRes++;
				Num /=Lenght;
				Lenght--;
			}
			if (Num==0) res=true;
		}
		delete []fl;
	}
	return res;
}

int main()
{
	int Buffer[36];
	for (int i=0; i<36; i++)  Buffer[i]=i+1; 
	int ResBuf[2];
	int beg=0;
	while (GetKombinat(Buffer,sizeof(Buffer)/sizeof(int), ResBuf, sizeof(ResBuf)/sizeof(int),beg))
	{
		printf("%d - ",beg);
		for (int i=0; i<(sizeof(ResBuf)/sizeof(int)); i++) printf("%d, ",ResBuf[i]);
		printf("\n");
		beg++;
	}
	return 0;
}