CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Oct 2014
Posts
10

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?

2. Member
Join Date
Oct 2014
Posts
40

Re: order statistics

On what programming language you need to write code?
Last edited by bestellen; September 15th, 2015 at 03:40 PM.

3. Junior Member
Join Date
Oct 2014
Posts
10

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

4. Member +
Join Date
Jul 2013
Posts
576

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?

5. Junior Member
Join Date
Oct 2014
Posts
10

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.

6. Member +
Join Date
Jul 2013
Posts
576

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

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•