Hi Vicky.. Its O(n^K) as u are iterating over all the elements of array for
each of the k element subset!!
On Monday, 8 October 2012 23:53:15 UTC+5:30, ((** VICKY **)) wrote:
>
> Hi, I wrote code for generating all possible sets of length k in a array
> of length n. I did using recursion, but i'm not able to calc the
> complexity systematically [image: :-/] Kindly help me.
> 11:39 PM
>
> i.p {1,2,3,4,5} k =2
> o.p
> Vector has : 1 2 3 4 5
> 1----> 1 2
> 2----> 1 3
> 3----> 1 4
> 4----> 1 5
> 5----> 2 3
> 6----> 2 4
> 7----> 2 5
> 8----> 3 4
> 9----> 3 5
> 10----> 4 5
>
> Approach:
>
> Assume I have a selected and remaining set, now initially all will be
> remaining set and selected set= {}.
>
> In first step pick 1 and grow recursion with it as root and pick 2,3,4,5
> (n-1) as possible picks. Now print those sets since k=2(base case) is
> reached.
> Now grow recursion with 2 as root and 3,4,5 (n-2) as possible
> picks(childs) print them. Repeat till i reach 5 where i have no children
> possible as rem set is empty.
>
> void print_all(vector<int>sel,vector<int>rem, int n){
> if(sel.size() == n)
> {
> static int cnt = 1;
> cout<<cnt++<<"----> ";
> for(int i = 0; i < n; i++)
> cout<<sel[i]<<" ";
> cout<<endl;
> return;
> sel.erase(sel.begin(),sel.end());
> }
> for(int i = 0; i < rem.size(); i++)
> {
>
> vector<int>now,curr_sel;
> //for(int j = 0; j < i; j++)
> // now.push_back(rem[j]);
> for(int j = i+1; j<rem.size(); j++)
> now.push_back(rem[j]);
> // cout<<"now has : ";
> //for(int i = 0; i < now.size(); i++)
> // cout<<now[i]<<" ";
> //cout<<endl;
> for(int i = 0; i < sel.size(); i++)
> curr_sel.push_back(sel[i]);
> curr_sel.push_back(rem[i]);
> print_all(curr_sel,now,n);
> }}
>
>
> --
> Cheers,
>
> Vicky
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/GTlxcHY8JDYJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
