подскажите алгоритм нахождения всех сочетаний без повторений

Krevetka

С из n по к
n - натур числа, от 1 до 24 например
k = 8

kachokslava

один из самых простых и неэффективных способов:

#include <stdio.h>

// считает количество единиц в двоичном представлении n
int bits(int n)
{
int r=0;
for(;n!=0;n>>=1) r+=n&1;
return r;
}
//печатает номера позиций, где есть единица
void printbits(int n)
{
for(int i=0;i<32;i++) if( n& (1<<i printf("%d ",i+1);
printf("\n");
}

void print_C_n_k(int n,int k)
{
for(int i=0;i<1<<n;i++)
if (bits(i)==k) printbits(i);
}

int main
{
int n,k;
printf("n,k?");
scanf("%d%d",&n,&k);
print_C_n_k(n,k);
return 0;
}

Krevetka

спасибо)
этот способ я знал
хотелось бы что- то вроде
Сочетанием (combination) из n элементов по m называется множество (неупорядоченный набор) из m различных чисел, принадлежащих множеству 1:n.
Для перебора сочетаний выберем удобное стандартное представление сочетаний, например в виде монотонно возрастающего набора из m чисел, лежащих в диапазоне 1:n и будем перебирать только такие стандартные записи сочетаний.
Состояние вычислительного процесса. Массив x1,...,xm номеров, включенных в сочетание.
Начальное состояние. Принять xi = i для всех i, принадлежащих множеству 1:m.
Стандартный шаг. Просматривать компоненты вектора x, начиная с xm, и искать первую компоненту, которую можно увеличить (нельзя увеличить xm = n, xm - 1 = n-1,...). Если такой компоненты не найдется, закончить процесс. В противном случае, пусть k — наибольшее число, для которого xk < n + m - k. Увеличить xk на единицу, а для всех следующих за k-ой компонентой продолжить натуральный ряд от нового значения xk, т.е. положить xi = xk + (i - k) для i > k.

kachokslava

ну вот и алгоритм, что надо-то?

Xephon

Книга А.Х.Шеня "Программирование. Теоремы и задачи."
http://doors.infor.ru/allsrs/math/gl2.html

Krevetka

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

seregaohota

Если алгоритм генерации самих перестановок какого-либо множества, то ботай Липский. Комбинаторика для программистов
Если тебе значения нужны, то в 2-мерной матрице в первом квадранте целочисленной плоскости (для x=k>=0, y=n-k>=0) выставляются на осях единицы, и каждое число в клетке равно сумме тех что под ним и слева. До k=8 вертикали дойдёшь - и дело в шляпе.
PS лень вдумываться под вечер в твои объяснения...
Ты скажи, ты скажи,
Чо те надо, чо надо,
Может дам, может дам
Что ты хошь

stm7543347

surface :: Int -> Int -> [[Int]]
surface k n = surface' k [1 .. n] where
surface' 0 _ = [[]]
surface' k s = concatMap (\(c:cs) -> map (c:) $surface' (k - 1) cs) $take (length s - k + 1) $tails s

natunchik

Я написал неправильный комментарий и удалил его.
Эффективная последовательная генерация комбинаций есть тут: http://docs.python.org/library/itertools.html#itertools.comb...
Ещё в принципе есть алгоритм для генерации энтой комбинации: http://stackoverflow.com/questions/1776442/nth-combination/1... (только этот неэффективный, потому что использует функцию choice, однако идея там правильная, надобно взять из википедии формулки для количества комбинаций и считать через них).

Krevetka

спасибо конечно но так сложно решать такую не сложную задачу - это сильно
в итоге, реализовал все по своему алгоритму, который выложил выше
цель была - пробежаться по всем сочетаниям без повторений
Оставить комментарий
Имя или ник:
Комментарий: