Все наборы из n элементов по k

> Нужно выбрать все сочетания не повторяющихся элементов по k из n.
> 111 211 311 411 511 521 531 541 551 552 553 554 555

не возьмут.

так я уже понял:)

интересно просто

Я хотел выбрать вообще все, потом с ними что-то делать(функцию отслеживания перестановки и повторений написал), но не получается. Читайте внимательней

Ты теорвер вообще проходил? Это обычно в первых лекциях.

man Теория вероятностей и man Комбинаторика

> сочетания не повторяющихся
111 - это точно не оно

> Читайте внимательней

пиши понятней.

#include <stdio.h>
#include <memory.h>

int main() {
        const int n = 5;
        const int k = 3;
        int m[k];
        memset(m, 0, sizeof m);
        for (int i = 0; i < k;) {
                for (i = 0; i < k; ++i)
                        printf("%d", m[i] + 1);
                putchar('\n');
                for (i = 0; i < k; ++i)
                        if (++m[i] == n)
                                m[i] = 0;
                        else
                                break;
        }
        return 0;
}

на STL все просто

std::next_parmutation

sorry, of course - std::next_permutation

ORLY?

[code] def comb(x,l): if x==0 or len(l) < x: raise Exception elif len(l) == x: yield l elif x==1: for e in l: yield [e,] else: # len(l) > x: for i in xrange(len(l)-x+1): for m in comb(x-1,l[i+1:]): yield [l[i]]+m [/code]

Я не могу перебрать все варианты с повторениями.

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

#include <iostream>
#include <vector>

using namespace std;

void backtrack(int n, int k, int prev, vector<int> &v)	{
	if (k == 0)	{
		cout << "{" << v[v.back()];
		for (size_t i = v.size()-1; i > 0; i--)
			cout << ", " << v[i-1];
		cout << "}" << endl;
	}	else	{
		for (int i = prev+1; i <= n; i++)	{
			v[k-1] = i;
			backtrack(n, k-1, i, v);
		}
	}
}

int main()	{
	int n, k;
	cin >> n >> k;
	vector<int> v(k);
	backtrack(n, k, 0, v);
}

> пиши понятней.
И тем не менее ваша программа неверна. Запустите и посмотрите.
//Код не читал. Запустил и посмотрел.

чем табуляция в 8 пробелов лучше 4х-пробельной?

less /usr/src/linux/Documentation/CodingStyle

In short, 8-char indents make things easier to read, and have the added benefit of warning you when you're nesting your functions too deep. Heed that warning.

;)

а если серьезно... этот пример писал в мц, у меня там 8-символьная табуляция для индента. обычно использую индент 4-мя пробелами.

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combination...

Нужно выбрать все сочетания не повторяющихся элементов по k из n.

Если я правильно понял, что нужно, то вот результат недолгих раздумий.

#include <iostream>
#include <vector>

using std::vector;
using std::cin;
using std::cout;
using std::endl;

int n, k;
vector<int> v;

void comb(int num)
{
	if(num > k)
	{
		for(int i=1; i<=k; i++)
			cout << v[i];
		cout << endl;
		return;
	}
	v[num] = v[num-1]+1;
	while(v[num] <= n)
	{
		comb(num+1);
		v[num]++;
	}
	return;
}


int main(void)
{
	cin >> n >> k;
	v.resize(k+1);
	v[0]=0;
	comb(1);
	return 0;
}

Результат работы:

lord@localhost:~> c++ tmp.cpp 
lord@localhost:~> ./a.out 
5 3
123
124
125
134
135
145
234
235
245
345
lord@localhost:~> 

> > Я не могу перебрать все варианты с повторениями.

А я могу. :-)

[code] $ ./a.out 3 2 {1, 2} {1, 3} {0, 3}

$ ./a.out 5 5 {4, 2, 3, 4, 5}

$ ./a.out 4 2 {1, 2} {1, 3} {1, 4} {0, 3} {0, 4} {0, 4}

$ ./a.out 3 1 {0} {0} {0}

[/code]

Orly? Я не знаю, как это назвать.

Orly? Я не знаю, как это назвать.

Я знаю. Нечего вносить правки в вывод во время постинга.)

#include <iostream>
#include <vector>

using namespace std;

void backtrack(int n, int k, int prev, vector<int> &v)   {
   if (k == 0)   {
      cout << "{" << v.back();
      for (size_t i = v.size()-1; i > 0; i--)
         cout << ", " << v[i-1];
      cout << "}" << endl;
   }   else   {
      for (int i = prev+1; i <= n; i++)   {
         v[k-1] = i;
         backtrack(n, k-1, i, v);
      }
   }
}

int main()   {
   int n, k;
   cin >> n >> k;
   vector<int> v(k);
   backtrack(n, k, 0, v);
}

эх, рекурсия, так и знал. Тем не менее все возможные сочетания по-прежнему не показываются:

5
3
{2, 2, 3}
{2, 2, 4}
{2, 2, 5}
{3, 3, 4}
{3, 3, 5}
{4, 4, 5}
{2, 3, 4}
{2, 3, 5}
{2, 4, 5}
{0, 4, 5}

Как я понял, функция backtrack вызывается со следующими аргументами: общее количество элементов массива, кол-во эл-тов в группе, текущий элемент(в группе или массиве?),вектор(почему его нужно менять внутри?)

эх, рекурсия, так и знал.

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

Тем не менее все возможные сочетания по-прежнему не показываются:

Все показывается в последней версии, это вы первый код запустили. В первой просто на вывод в качестве первого числа идет не v.back(), а v[v.back()], очепятался, но бдительный анонимус мне уже об этом сказал.

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}

Как я понял, функция backtrack вызывается со следующими аргументами

Да, эти аргументы: общее число n, количество k, которое осталось выбрать и выбранное на предыдущем шаге prev (это помогает, т.к. ответ выводится в виде упорядоченного набора, значит на следующем шаге перебирать будем большие prev). Ну и вектор, в котором формируется текущий ответ. Писал по схеме перебора, которую вдалбливали перед школьными олимпиадами, никакой вдумчивости, спешил. :) У товарища unikoid вроде написано то же, но аккуратнее.

Писал по схеме перебора, которую вдалбливали перед школьными олимпиадами, никакой вдумчивости, спешил.

Да, а мы в школе только флешки «для сайта» рисовали:( Если со сложностью алгоритмов нормально разбираться, это «алгоритмы м структуры данных» нужно прочитать, или здесь просто из комбинаторики все выходит?

Чем дальше после вуза, тем чаще убеждаюсь, что ничего не знаю. Хотя они это и не обязаны были давать