yeah , my algo wont work for these cases :(.
On Mon, Oct 31, 2011 at 6:32 PM, sunny agrawal <[email protected]>wrote:
> @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.
>
--
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.
