Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   combinations programm (http://www.go4expert.com/forums/combinations-programm-t24155/)

vagelis 12Dec2010 19:18

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;
}


jimblumberg 13Dec2010 02:00

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

vagelis 13Dec2010 13:37

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

vagelis 13Dec2010 13:39

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

xpi0t0s 13Dec2010 18:24

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.

vagelis 13Dec2010 21:03

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..

}


jimblumberg 13Dec2010 22:51

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

vagelis 14Dec2010 03:19

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!!


All times are GMT +5.5. The time now is 01:41.