Armenian Knowledge Base  

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

Reply
 
LinkBack Thread Tools
Old 13.05.2002, 12: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, 13: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 13.05.2002, 15:01   #3
Игроман Заядлый - 1шт. ;)
 
-=iR0Nr@T=-'s Avatar
 
Join Date: 03 2002
Location: Armenia
Posts: 303
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

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

Eto nasledie ot paskalya???
Reply With Quote
Old 14.05.2002, 04: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, 19: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
Old 30.12.2019, 20:59   #6
Secret coder
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Yerevan
Posts: 3,638
Downloads: 22
Uploads: 0
Reputation: 228 | 4
Default

PHP Code:
#include <vector>
#include <iostream>
#include <algorithm>

using std::cin;
using std::cout;
using std::endl;
using std::copy;
using std::vector;
using std::back_inserter;
using std::ostream_iterator;
using std::next_permutation;

typedef unsigned int uint;

template <typename BidItbool next_combination(BidIt n_beginBidIt n_endBidIt r_beginBidIt r_end) {
    
BidIt r_marked;
    
bool boolmarked false;
    
    
BidIt n_it1 n_end;
    --
n_it1;
    
    
    
BidIt tmp_r_end r_end;
    --
tmp_r_end;
    
    for(
BidIt r_it1 tmp_r_endr_it1 != r_begin || r_it1 == r_begin; --r_it1, --n_it1) {
        if(*
r_it1 == *n_it1 ) {
            
//to ensure not at the start of r sequence
            
if(r_it1 != r_begin) {
            
                
boolmarked true;
                
r_marked = (--r_it1);
                
//add it back again 
                
++r_it1;
                continue;
            }
            
//it means it is at the start the sequence, so return false      
            
else return false;
        }
        else {
            
//marked code
            
if(boolmarked) {
                
//for loop to find which marked is in the first sequence

                //mark in first sequence
                
BidIt n_marked;
                for (
BidIt n_it2 n_beginn_it2 != n_end; ++n_it2)
                    if(*
r_marked == *n_it2) {n_marked n_it2; break;}
                    
                
BidIt n_it3 = ++n_marked;    
                for(
BidIt r_it2 r_markedr_it2 != r_end; *r_it2 = *n_it3, ++r_it2, ++n_it3);    
                return 
true;
            }
            for(
BidIt n_it4 n_beginn_it4 != n_end; ++n_it4)
                if(*
r_it1 == *n_it4) {
                    *
r_it1 = *(++n_it4);
                    return 
true;           
                }
        }
    }  
    
//will never reach here
    
return true;
}

//the function returns true if the k-th combination is found 
//from r elements of n, otherwise false, the found combination
//is filled in the input destionation vector.
bool combination(vector<uint>& srcvector<uint>& dstuint ruint k) {
    if(
src.size()) return false;
    
int c 1;
    
vector<uinttmp(src.begin(), src.begin() + r);
    
dst.clear();
    do {
        if(
== k) {
            
copy(tmp.begin(), tmp.begin() + rback_inserter(dst));
            return 
true;
        }
        ++
c;
    }
    while(
next_combination(src.begin(), src.end(), tmp.begin(), tmp.end()));
    return 
false;
}

//the function returns true if the k-th permutation is found 
//from r elements of n, otherwise false, the found permutation
//is filled in the input destionation vector.
bool permutation(vector<uint>& srcvector<uint>& dstuint ruint k) {
    
int c 1;
    
dst.clear();
    do {
        if(
== k) {
            
copy(src.begin(), src.begin() + rback_inserter(dst));
            return 
true;
        }
        ++
c;
    }
    while(
next_permutation(src.begin(), src.begin() + r));
    return 
false;
}
int main() {
    
//declaring needed variables for testing
    
bool ret;
    
vector<uintvecSrcvecDst;

    
vecSrc.push_back(1);
    
vecSrc.push_back(2);
    
vecSrc.push_back(3);
    
vecSrc.push_back(4);
    
    
//getting the k-th permutation
    
ret permutation(vecSrcvecDst32);
    
    
//output the result
    
if(retcopy(vecDst.begin(), vecDst.end(), ostream_iterator<uint>(cout" "));
    else 
cout << "No permutation found.";

    
cout << endl;

    
//fill the values again
    
vecSrc.push_back(1);
    
vecSrc.push_back(2);
    
vecSrc.push_back(3);
    
vecSrc.push_back(4);

    
//getting the k-th combination
    
ret combination(vecSrcvecDst32);
    
    
//output the result
    
if(retcopy(vecDst.begin(), vecDst.end(), ostream_iterator<uint>(cout" "));
    else 
cout << "No combination found.";

    
cout << endl;

    
system("pause");
    return 
EXIT_SUCCESS;

Reply With Quote
Sponsored Links
Reply

Thread Tools


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

All times are GMT. The time now is 01:33.


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