
October 7th, 2014, 07:24 AM
#1
order statistics
hi, Have a problem where i want to write a program to find the ith order statistic of a data set consisting of character and their occurences. For example i have a data set consiting of B,A,C,A,B,C,A,D; here i have A with 3 occurences,B with 2 occurences C with 2 occurences and D with on occurrence. So they can be group in pairs (charaters,Number of occurences); so here we have (A,3),(B,2),(C,2) and (D,1). Assuming than k is the number of these pairs, how can i find the ith of the data set in O(k) where k is the number of pairs. Well i thought i could sort the element based their number of occurence and find their ith smallest elements but i am not sure that can work.
any help?

October 7th, 2014, 09:06 AM
#2
Re: order statistics
On what programming language you need to write code?
Last edited by bestellen; September 15th, 2015 at 03:40 PM.

October 7th, 2014, 11:09 AM
#3
Re: order statistics
Originally Posted by bestellen
On what programming language you need to write code?
in c#. the alogorithm will be fine. i will write the code myself

October 8th, 2014, 01:11 AM
#4
Re: order statistics
Originally Posted by sanchez_masherano
how can i find the ith of the data set
What does this means? What is it that you want to find?

October 8th, 2014, 08:48 AM
#5
Re: order statistics
Originally Posted by razzle
What does this means? What is it that you want to find?
i have to find the kth smallest element from that data set.

October 9th, 2014, 12:46 AM
#6
Re: order statistics
Originally Posted by sanchez_masherano
i have to find the kth smallest element from that data set.
I think you're too imprecise in your problem description but okay, finding the k'th smallest element in a sequence is a known problem called selection and is described here for example,
http://en.wikipedia.org/wiki/Selection_algorithm
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
