Hi SAMM,
The above code is not clear enough to understand . Sorry for that.
My idea was , like for above example : map will contain frequency of all
distinct elements.
so freq[1] = 6
freq[3]= 1
freq[5]=1
freq[6]=1
Now for n=9 and k=3
P1={1,3,5};
and now after this partition frequency of each element gets reduced by
1.Now you can eliminate elements having 0 frequency or just skip them.
In second run
P2={1,6,1}
and P3={1,1,1}.
On Mon, Oct 31, 2011 at 4:20 AM, SAMM <[email protected]> wrote:
> Ur algo will not work for this case :-
>
> 1 1 1 1 1 1 3 5 6 ---- For the array .. And for K=3
>
> Ur algo will give (1 1 1) (1 1 1 ) (3 5 6)
>
> On 10/30/11, mohit verma <[email protected]> wrote:
> > sort the array : O(nlogn)
> >
> > keep an array/map containing frequency of each element in sorted array :
> > O(n)
> >
> > v[n/k][k] - 2-D array of ints containing final partitions.
> >
> > for i=1 to n/k
> > {
> > int count=0;
> > for(j=0;j<n && count < k;j++)
> > { if( freq(a[i])==0) continue; //say array is used
> > v[i][count]=a[i];
> > freq(a[i])--; //just an idea , not actual implementation
> > count++;
> > }
> > }
> >
> > you can improve internal for loop by using map : if freq[a[i]] becomes 0
> > delete the node from array.
> > On Sun, Oct 30, 2011 at 10:35 PM, SAMM <[email protected]> wrote:
> >
> >> No there is no such condition ...just hav to make sure all the
> >> partitions are unique .
> >> The partitions can hav some elements (< K) in common but not the
> >> entire elements in a partition (Should be UNIQUE) .
> >>
> >> On 10/30/11, sunny agrawal <[email protected]> wrote:
> >> > Is there any condition like all sets should have same no. Of elements
> >> >
> >> > On 10/30/11, SAMMM <[email protected]> wrote:
> >> >> But how does it ensure tht the elements been removed wouldnot give
> >> >> the same set again ????
> >> >>
> >> >> --
> >> >> You received this message because you are subscribed to the Google
> >> Groups
> >> >> "Algorithm Geeks" group.
> >> >> 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.
> >> >>
> >> >>
> >> >
> >> >
> >> > --
> >> > Sunny Aggrawal
> >> > B.Tech. V year,CSI
> >> > Indian Institute Of Technology,Roorkee
> >> >
> >> > --
> >> > You received this message because you are subscribed to the Google
> >> > Groups
> >> > "Algorithm Geeks" group.
> >> > 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.
> >> >
> >> >
> >>
> >>
> >> --
> >> Somnath Singh
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> 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.
> >>
> >>
> >
> >
> > --
> > Mohit
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > 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.
> >
> >
>
>
> --
> Somnath Singh
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> 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.
>
>
--
Mohit
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
