Господи, какие вещи спрашивают...

Я в детстве догадался за 20 минут. Здесь ответа ты будешь ждать гораздо дольше.

Да, ключевое слово: рекурсия

Рекурсия или вложенные циклы - это очевидные решения. Но ресурсоёмкие. Интересует, нет ли решений оптимальных.

Вложенными циклами ничего не сделаешь. Разве что ручками разворачивать рекурсию, но це изврат.

Вообще рекурсивный алгоритм -- самое что ни на есть православное Ъ, быстрее ничего не придумаете.

Нет решений оптимальных.

>нет ли решений оптимальных.

Оптимальных с точки зрения чего?

>Рекурсия или вложенные циклы - это очевидные решения. Но ресурсоёмкие. Интересует, нет ли решений оптимальных.

Представь себе сколько оно выдаст тебе выборок если будешь выбирать 100 из 200.

Параметр О() настолько крутой, что "перевёрнутым квиксортом на ассемблере" ситуацию не спасти.

> Рекурсия или вложенные циклы - это очевидные решения. Но ресурсоёмкие.

Ресурсоёмкие?? Не так страшен чёрт^W рекурсия, как её малюют.

>Вообще рекурсивный алгоритм -- самое что ни на есть православное Ъ, быстрее ничего не придумаете.

Сейчас напишу нерекурсивный алгоритм, который будет работать по-быстрее. Можно даже посоревноваться. :)

вот примерно так:

vyborka x 0 = []
vyborka (x:[]) n = [x]
vyborka (x:xs) n = (map (\l -> x:l) (vyborka xs (n-1))) ++ (vyborka xs n)

> Сейчас напишу нерекурсивный алгоритм, который будет работать по-быстрее. Можно даже посоревноваться. :)

Напиши, топикстартер только этого и ждет.

Пусть надо сгенерировать сочетания из n элементов по k.

1) Берём k наименьших эл-тов из тех n, отсортировав их по возрастанию.

2) Берём первый справа элемент, который можно увеличить на 1 (а нельзя увеличивать последний элемент, индекс значения которого последний возможный или предпоследний элемент, индекс значения которого предпоследний, т.е. x_k = n, x_k-1 = n-1 и т. д.).

3) Если не нашли — конец.

4) Увеличиваем на 1 этот элемент, а из следующих за ним делаем натуральный ряд (т.е. каждый следующий будет равен предыдущему + 1)

5) Возвращаемся на шаг 2.

Пример:

1 2 3 4 5, сочетания по 3

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

О, Haskell... На императивных языках тот алгоритм, что я написал, был бы скорее всего по-быстрее, а вот на Хаскелле другое дело. Интересно, что быстрее, мой на Си или твой на Хаскелле.

$ ghc perm.hs 

perm.hs:3:37:
    Occurs check: cannot construct the infinite type: a = [a]
      Expected type: [a] -> t -> [[a]]
      Inferred type: [a] -> t -> [a]
    In the second argument of `map', namely `(vyborka xs (n - 1))'
    In the first argument of `(++)', namely
        `(map (\ l -> x : l) (vyborka xs (n - 1)))'

Угу, спасибо.

Функциональщики ведь покусают.

Вот тебе для M=32. Написать для остальных случаев тебе домашнее задание :)

#include <stdio.h>
#include <assert.h>

#define N 32
#define M 10

unsigned snoob (unsigned x)
{
	unsigned smallest, ripple, ones;
	smallest = x & -x;
	ripple   = x + smallest;
	ones     = x ^ ripple;
	ones     = (ones >> 2) / smallest;
	return ripple | ones;
}

void print_vec(int * vec, unsigned mask) {
	int i;
	for (i = 0; i < N; ++i) {
		if (mask & (1 << i)) {
			printf("%d, ", vec[i]);
		}
	}
	printf("\n");
}

int main()
{
	int vec[N];
	int i;
	unsigned mask = 0;
	unsigned a, b;

	assert(N == 32);

	for (i = 0; i < N; ++i) {
		vec[i] = i;
	}

	for (i = 0; i < M; ++i) {
		mask |= (1 << i);
	}

	a = mask;
	while (1) {
		print_vec(vec, a);
		b = snoob(a);
		if (b < a) {
			break;
		}
		a = b;
	}
}

Да, точно. Это алгоритм из замечательной книги Шень А. "Программирование: теоремы и задачи". http://www.ozon.ru/context/detail/id/3250402/

Неплохо было бы в development тред с полезными ссылками на алгоритмы сделать и вообще обсуждение алгоритмов.

вы простите мою неграмотность, но как понять следующее:

> #define N 32

...

> assert(N == 32);

судя по всему, синтаксис С (чистый). мейн должен возвращать значение

> вы простите мою неграмотность, но как понять следующее:

Я же сказал, что для N!=32 это домашнее задание. Специально assert поставил, чтоб никто не вздумал менять значение без правки кода.

> судя по всему, синтаксис С (чистый). мейн должен возвращать значение

Да, должен. Какое-то случайное число там вернется. Собирал без -Wall поэтому пропустил.

nanonymous, +1. Это наилучший алгоритм порождения сочетаний (кто тут спрашивал про ключевые слова?), быстрее не придумаешь. А рекурсии и вложенные циклы идут лесом ибо убивают производительность.

>Это наилучший алгоритм порождения сочетаний

Ага - только в данном случае непонятно зачем сортировать элементы по возрастанию.

foo()
{
  if test "$2" -eq 0; then echo; return; fi
  seq "$2" "$1" | while read I; do foo $(($I - 1)) $(($2 - 1)) | sed "s/\$/ $I/"; done
}