@Mohit
that will also not work
example: {1,1,1,2,2,2,3,3,3}
i think all the methods that try to fill the matrix(considering k sets as k
rows) either horizontally or vertically will fail
we need to fill these both horizontally and vertically at the same time
depending upon the frequency of elements.
On Mon, Oct 31, 2011 at 6:16 PM, mohit verma <[email protected]> wrote:
> 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.
>
--
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.
