Go4Expert - combinations programm

Go4Expert (http://www.go4expert.com/)

- C (http://www.go4expert.com/forumdisplay.php?f=20)

- - combinations programm (http://www.go4expert.com/showthread.php?t=24155)

combinations programm

hello again..

i want to make a programm to find all the combinations of n numbers choosing the k of them

for example

[1 2 3 4 5]

the combinations of two of them are

1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

the combinations of 3 numbers of them are

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

i have made this programm that it is close to find the write solution but i cannot go farther

please i want help..
if you can improve my programm or suggest me something already done..

Code:



#include"stdafx.h"

#include"iostream"

#include<vector>

usingnamespace std;

vector<vector<int>> v;

int arithmos_comb_sinolikos;

void comb(vector<int> A,int k,vector<vector<int>> &v,int column_v,int row);

int arithmos_comb_epomeno(int n,int k);

int factorial(int number) ;

ostream & print(const vector<int> & v);

ostream & print(const vector<vector<int> > & v);

int _tmain(int argc, _TCHAR* argv[])

{

int arr[]={1,4,6,7,9};

//cout<<arr[0];

vector<int> A(arr,arr+5);

v.push_back(vector<int>());

//cout<<v.size();

//cout<<A[3];

arithmos_comb_sinolikos=arithmos_comb_epomeno(A.size(),2);

//cout<<arithmos_comb_epomeno(4,2);

//cout<<arithmos_comb_sinolikos;

comb(A,2,v,0,0);

//print(v);

cin>>arr[0];

}

void comb(vector<int> A,int k,vector<vector<int>> &v,int column_v,int row)

{

if(row>=arithmos_comb_sinolikos)

{

//cout<<"epistrefei_giati_row>=arithmos_comb"<<endl;

//return;

}

else

{

}

cout<<endl<<endl<<"mpike_sto_comb";

print(v);

for(int i=column_v;i<=A.size()-k+column_v;i++)

{

cout<<"mpike_sto_proto_for i="<<i<<endl;

for(int y=0;y<arithmos_comb_epomeno(A.size()-column_v-i-1,k-column_v-1);y++)

{

cout<<"mpike_sto_deytero_for y="<<y<<endl;

v[v.size()-1].push_back(A[i]);

print(v);

cout<<"edaxei"<<endl;

cout<<"column_v="<<column_v<<endl;



if(column_v+1<k)

{

cout<<"mpike_sto_mikrotero_k"<<endl;

comb(A,k,v,column_v+1,row);

//return;





}

else

{

cout<<"mpike_sto_megalitero_k"<<endl;

//v[v.size()-1].push_back(A[i+column_v]);

v.push_back(vector<int> ());

column_v=0;

return;



//comb(A,k,v,0,stili_A,row+1);

//return;



}







}



}

}

int arithmos_comb_epomeno(int n,int k)

{ 



return (factorial(n)/(factorial(k)*factorial(n-k)));

}

int factorial(int number) {

int temp;

if(number <= 1) return 1;

temp = number * factorial(number - 1);

return temp;

}

ostream & print(const vector<int> & v)

{

for (int i=0; i<v.size(); i++)

cout << v[i] << ' ';

return cout;

}

ostream & print(const vector<vector<int> > & v)

{

for (int i=0; i<v.size(); i++)

{

for (int j=0; j<v[i].size(); j++)

cout << v[i][j] << ' ';

cout << endl;

}

return cout;

}

Re: combinations programm

Does your program compile without errors/warnings?

If not please post the complete error/warning messages.

If it does compile, what is your program doing wrong?

What were your inputs? What did the program output?

What did you expect?

Jim

Re: combinations programm

it compiles but here is the difference of what i want and what i get

must be ------and i find
1 4--------------1 4
1 6--------------1 4
1 7--------------1 4
1 9--------------1 4
4 6--------------4 4
4 7--------------4 4
4 9--------------4 4
6 7--------------6 4
6 9--------------6 4
7 9--------------7 4

it is difficult to do this
it is difficult the logic..i think only a very good programmer could do that..
and i am not

Re: combinations programm

the numbers are 1,4,6,7,9 and i want the combinations with k=2

Re: combinations programm

If you want a fixed depth then do it with nested for loops which is by far the simplest solution, e.g.

Code:

for (int i=0; i<5; i++)

{

  for (int j=0; j<5; j++)

  {

    if (i!=j)

    {

      printf("%d %d\n",arr[i], arr[j]);

    }

  }

}

I'll leave it to you to work out how to eliminate duplicates from this; it's not difficult.

Variable depth is more tricky but can be solved with recursion and a second array to mark whether or not a number has been "seen":

Code:

int arr[]={1,4,6,7,9};

int seen[5];

int maxdepth=3;



void recurse(int depth)

{

        if (depth>=maxdepth)

        {

                for (int i=0; i<5; i++)

                {

                        if (seen[i])

                                printf("%d ",arr[i]);

                }

                printf("\n");

        }

        else

        {

                for (int i=0; i<5; i++)

                {

                        if (!seen[i])

                        {

                                seen[i]=1;

                                recurse(depth+1);

                                seen[i]=0;

                        }

                }

        }

}



void test38()

{

        for (int i=0; i<5; i++)

        {

                seen[i]=0;

        }



        for (int i=0; i<5; i++)

        {

                seen[i]=1;

                recurse(1);

                seen[i]=0;

        }

}

Again this includes duplicates, and similarly I'll leave it as an exercise for you to determine how best to eliminate them. Another solution is to use an array of counters, which is essentially the same as this code where the "array" is effectively stored on the stack.

Re: combinations programm

i found this that works..

Code:



template <class RanIt, class Func>

void recursive_combination(RanIt nbegin, RanIt nend, int n_column,

RanIt rbegin, RanIt rend, int r_column,int loop, Func func,vector<vector<int>> &comb)

{

int r_size=rend-rbegin;

int localloop=loop;

int local_n_column=n_column;

//A different combination is out

if(r_column>(r_size-1))

{

comb.push_back(vector<int>());

func(rbegin,rend,comb);

return;

}

//===========================

for(int i=0;i<=loop;++i)

{

RanIt it1=rbegin;

for(int cnt=0;cnt<r_column;++cnt)

{

++it1;

} 

RanIt it2=nbegin;

for(int cnt2=0;cnt2<n_column+i;++cnt2)

{

++it2;

} 

*it1=*it2;

++local_n_column;

recursive_combination(nbegin,nend,local_n_column,

rbegin,rend,r_column+1,localloop,func,comb);



--localloop;

}

}

typedef vector<int>::iterator vii;

void display(vii begin,vii end,vector<vector<int>> &comb)

{

for (vii it=begin;it!=end;++it)

{

//cout<<*it;

comb[comb.size()-1].push_back(*it);

}

//cout<<endl;

}

 

int main()

{

           

vector<int> linspace;

for(int i=0;i<Mem_in.size();i++) linspace.push_back(i+1); 



vector<int> cb;

for(int i=0;i<k;i++) cb.push_back (i+1);



vector<vector<int>> v;

recursive_combination(linspace.begin (),linspace.end(),0,cb.begin(),cb.end(),0,linspace.size()-k,display,v);

//and we find v that has the combinations..

 

}

Re: combinations programm

So you:

Quote:

i found this that works..

Do you know why it works?

Quote:

it is difficult to do this
it is difficult the logic..i think only a very good programmer could do that..
and i am not

Since the program you "found" is using advanced language features, don't you think your instructor will recognize that this is not your work?

Jim

Re: combinations programm

my friend my work is not to do this but i must use this to do my work..
thank you for your time and for your help!!