-
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
|