Генерация сочетаний из n цифр по m.

[Dark Abyss of Yerevan]

Я тут написал небольшую прогу которая последовательно выводит все сочетания
из n цифр по m. Алгоритм работает как счетчик, т.е. крутит последнее число,
потом предпоследнее итд, при этом делает кое какие проверки. Вообщем:

/*		Генерация сочетаний из n цифр по m.
		abyss 11:54 AM 5/12/02
*/

#include <stdio.h>

const n=12;
const m=5;

void main(){

    int i,j;
    int v[m+1];				// we want to use v[1]..v[m]
    bool b;					// so declare it as v[m+1]
    int count=0;


    for(i=1;i<=m;i++)v[i]=i;			// initialization

    do {

	    for (;v[m]<=n;v[m]++){		// increment the last element
		    for (j=1;j<=m;j++)printf(&quot;%d &quot;,v[j]);
		    printf(&quot;\n&quot;);
		    count++;
	    }
				
	    /*	the last element has reached the right boundary, so make
		arrangements and continue	*/
	    b=false;
	    for (i=m-1;i>0;i--)
	    	    if(b=v[i]+1<=n-(m-i)) break;
	    v[i]++;
		
	    /* v[i] incremented, now arrange elements v[j],j>i   */
	    for (j=i+1;j<=m;j++)v[j]=v[j-1]+1;

    } while (b);


    printf (&quot;Count=%d\n&quot;,count);

}

Я знаю что эта задача имеет одно очень красивое решение. Кому не лень пусть
напишет свою версию, потом сравним, оценим сложности алгоритмов итд.

[Aram Hambardzumyan]

Originally posted by Dark Abyss of Yerevan:
Я знаю что эта задача имеет одно очень красивое решение.

а я знаю, что стандартная библиотека c++ содержит функцию next_permutation, которая и выполняет это все

[-=iR0Nr@T=-]

i mojet vsetaki schetchiki nachnesh` s nulya kak prinyato v C/C++????

Eto nasledie ot paskalya???

[Grigor]

  
#include <iostream>
#include <vector>
using namespace std;

void print(const vector<int>& a)
{
	for (unsigned i = 0; i< a.size(); i++)
	{
		cout << a[i] << ' ';
	}
	cout << endl;
}

void perm(vector<int>& a, int n, int m, int first, int ind)
{
	if (ind > m)
	{
		print (a);
		return;
	}
	for (int i = first; i <= n - (m - ind); i++)
	{
		a[ind - 1] = i;
		perm (a, n, m, i + 1, ind + 1);
	}
}

void print_perm (int n, int m)
{
	vector<int> a;
	a.resize (m);
	perm(a, n, m, 1, 1);
}

int main()
{
	print_perm(12, 5);
	return 0;
}

Например так, но лучше всего использовать STL. Что касается сложности, то по порядку оба решения эквивалентны.

[Aram Hambardzumyan]

Originally posted by Aram Hambardzumyan:

а я знаю, что стандартная библиотека c++ содержит функцию next_permutation, которая и выполняет это все

пардон, я напутал, эта функция генерирует перестановки...