Генерация сочетаний из 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, которая и выполняет это все

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

[AvDav]

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 BidIt> bool next_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt 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_end; r_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_begin; n_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_marked; r_it2 != r_end; *r_it2 = *n_it3, ++r_it2, ++n_it3);    
                return true;
            }
            for(BidIt n_it4 = n_begin; n_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>& src, vector<uint>& dst, uint r, uint k) {
    if(r > src.size()) return false;
    int c = 1;
    vector<uint> tmp(src.begin(), src.begin() + r);
    dst.clear();
    do {
        if(c == k) {
            copy(tmp.begin(), tmp.begin() + r, back_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>& src, vector<uint>& dst, uint r, uint k) {
    int c = 1;
    dst.clear();
    do {
        if(c == k) {
            copy(src.begin(), src.begin() + r, back_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<uint> vecSrc, vecDst;

    vecSrc.push_back(1);
    vecSrc.push_back(2);
    vecSrc.push_back(3);
    vecSrc.push_back(4);
    
    //getting the k-th permutation
    ret = permutation(vecSrc, vecDst, 3, 2);
    
    //output the result
    if(ret) copy(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(vecSrc, vecDst, 3, 2);
    
    //output the result
    if(ret) copy(vecDst.begin(), vecDst.end(), ostream_iterator<uint>(cout, " "));
    else cout << "No combination found.";

    cout << endl;

    system("pause");
    return EXIT_SUCCESS;
}