--------------------------------------------------------------------------------
Здравствуйте уважаемые Пожалуйста подскажите алгоритм поиска, возможных кобинаций в массиве из n чисел
В общем есть такая задача.
Есть массив случайных целых чисел
14 15 22 11 17
Дано число N,
Требуется в массиве найдти, все возожные варианты комплектов состоящих из N цифр
Допустим N равно 3, нужно найдти все возможных варианты
( Позиции цифр в нутри варианта не играет роли , главное найти все варианты наборов N чисел)
список будет таким
14 15 22 11 17
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
19-04-2007 02:07
Теперь можно оценить алгоритм из 18-04-2007 12:25:
1) Алгоритм ограничен разрядностью процессора и при N>32 возникают проблемы с вычислением.
2) Алгоритм при больших значениях N работает крайне неэффективно. Например, для получения сочетаний из 32 по 3 приходится перебирать более 4 миллиардов комбинаций, хотя нужных не более 5000.
А я использовал для подобных задач двоичный счётчик - общий смысл такой:
Общее количество элементов = N
Число выбираемых вариантов = K
Вычисляется 2^N (2 в степени N) - для определения продолжитнльности цикла
основной цикл такой(псевдокод):
totalIterations := Power(2,N);
for i := 1 to totalIterations do
begin
onesCount = CalculateOnesCount(i, N);
if onesCount = K then PrintCombination(i);
end;
CalculateOnesCount - подсчитывает количество ненулевых битов в числе
function CalculateOnesCount(currentValue : Integer; maxDigits : Integer): Integer;
var
i: Integer;
twoInPower : Integer;
begin
result := 0;
for i := 1 to N do
begin
twoInIPower = Power(2, i);
if twoInPower > currentValue then
break;
if (currentValue and twoInPower) = twoInPower then
Inc(result);
end;
end;
А PrintData - печатает текущую комбинацию - на месте единичного бита в текущей комбинации выводит необходиое число. работает сходным образом с
CalculateOnesCount(к сожалению нет времени написать её). Надеюсь, поможет.
Можно предложить следующий алгоритм перебора сочетаний из n по k. Все сочетания размещаются в двумерном динамическом массиве CombArray:array of array of Integer. Первый индекс нумерует сами сочетания и меняется от 0 до C(n,k)-1, где C(n,k) - число сочетаний из n элементов по k. Сочетание записывается упорядоченным набором k чисел, изменяющихся от 1 до n. Второй индекс нумерует числа выборки одного сочетания и меняется от 1 до k (нулевой индекс зарезервирован).
Для вычисления числа сочетаний можжно использовать рекуррентную формулу:
function C(n,k:Integer):Int64;
var
i:Integer;
begin
if k=0 then Result:=1 else
begin
Result:=n;
for i:=2 to k do Result:=(Result*(n-i+1)) div i;
end;
end;
Алгоритм основан на анализе группы сочетаний с фиксированным значением одного из выбранных элементов. Выделим группу, у которой элемент, стоящий на (m-1)-ом месте, равен a. Тогда число элементов в подгруппе, для которой элемент, стоящий на m-ом месте равен b, равно C(n-b,k-m). Всего имеется n-k+m-a подгрупп, а величина b меняется в переделах от a+1 до n-k+m. Заполнение m-ой позиции одинаковыми элементами удобно начинать с конца, так как последняя подгруппа состоит ровно из одного элемента и для вычисления числа элементов в предыдущей подгруппе можно не вычислять явно биномиальный коэффициент, а использовать рекуррентное соотношение. Если s - номер подгруппы, отсчитываемый с конца, а count - число элементов в предыдущей поддгруппе, то число элементов в s-ой группе расчитывается функцией:
function Recount(count,s:Cardinal;m:Integer):Cardinal;
begin
if s=1 then Result:=1
else Result:=(count*(k-m+s-1)) div (s-1);
end;
Заполнение блока данных осуществляет следующая процедура:
procedure MakeBlock(var start:Cardinal;m:Integer);
var
a:Integer;
i,count,s,last:Cardinal;
begin
a:=CombArray[start-2,m-1];
count:=1;
for s:=1 to n-k+m-a do
begin
last:=start-1;
count:=Recount(count,s,m);
start:=last-count+1;
for i:=start to last do
CombArray[i-1,m]:=n-k+m-s+1;
end;
end;
Здесь: start - увеличенный на 1 номер сочетания, который является последним в блоке. Вместо параметра b используется номер s подгруппы, отсчитываемый с конца блока. Внутри процедуры start и last используются для хранения первого и последнего номеров сочетаний в подгруппе. Эта процедура заполняет также правильно все элементы, стоящие на первом месте (m=1) если все элементы CombArray с m=0 равны нулю.
Весь алгоритм выглядит следующим образом:
var
Cnt:Int64;
i,start:Cardinal;
Step:Integer;
j:Integer;
begin
Cnt:=C(n,k);
SetLength(CombArray,Cnt);
for i:=0 to Cnt-1 do Setlength(CombArray[i],k+1);
for Step:=1 to k do
begin
start:=Cnt+1;
while start>1 do MakeBlock(start,Step);
end;
end;
>Но это для трех элементов , а мне нужно N. ни как не могу придумать как
Поэтому я и сказал про рекурсию
примерный псевдокод
proc DoComb(Start, N, K: Integer; OldComb)
for i := Start to N-K+1 do begin
NewComb := OldComb + Arr[i];
if K = 1 then
PrintComb(NewComb)
else
DoComb(i + 1, N, K -1, NewComb)
end;
вызов DoComb(1, 5, 3, пустой набор)
в качестве набора может выступать массив, строка, множество или что удобнее
Это называется "сочетания из N по K элементов", в данном случае будет C(5,3) наборов
Рекурсивный вариант написать достаточно легко, итеративный немног посложнее, если не получится, то можно нагуглить.
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
