Генерация сочетаний из 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:
Originally posted by Dark Abyss of Yerevan:
Я знаю что эта задача имеет одно очень красивое решение.а я знаю, что стандартная библиотека c++ содержит функцию next_permutation, которая и выполняет это все ;) пардон, я напутал, эта функция генерирует перестановки...