Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 13.05.2002, 13:51   #1
Дошкольник
 
Dark Abyss of Yerevan's Avatar
 
Join Date: 01 2002
Location: hell
Posts: 124
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post Генерация сочетаний из n цифр по m.

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

Code:
/*		Генерация сочетаний из 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);

}
Я знаю что эта задача имеет одно очень красивое решение. Кому не лень пусть
напишет свою версию, потом сравним, оценим сложности алгоритмов итд.
Reply With Quote
Old 13.05.2002, 14:59   #2
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Post

Quote:
Originally posted by Dark Abyss of Yerevan:
Я знаю что эта задача имеет одно очень красивое решение.
а я знаю, что стандартная библиотека c++ содержит функцию next_permutation, которая и выполняет это все
Reply With Quote
Old 14.05.2002, 05:43   #4
Младенец
 
Join Date: 05 2002
Location: Yerevan
Posts: 5
Downloads: 1
Uploads: 0
Reputation: 0 | 0
Post

Code:
  
#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. Что касается сложности, то по порядку оба решения эквивалентны.
Reply With Quote
Old 18.05.2002, 20:09   #5
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Post

Quote:
Originally posted by Aram Hambardzumyan:
Quote:
Originally posted by Dark Abyss of Yerevan:
Я знаю что эта задача имеет одно очень красивое решение.
а я знаю, что стандартная библиотека c++ содержит функцию next_permutation, которая и выполняет это все
пардон, я напутал, эта функция генерирует перестановки...
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 00:46.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.