CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  1. #1
    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. #2

    Re: order statistics

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

  3. #3
    Join Date
    Oct 2014
    Posts
    10

    Re: order statistics

    Quote Originally Posted by bestellen View Post
    On what programming language you need to write code?
    in c#. the alogorithm will be fine. i will write the code myself

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: order statistics

    Quote Originally Posted by sanchez_masherano View Post
    how can i find the ith of the data set
    What does this means? What is it that you want to find?

  5. #5
    Join Date
    Oct 2014
    Posts
    10

    Re: order statistics

    Quote Originally Posted by razzle View Post
    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. #6
    Join Date
    Jul 2013
    Posts
    576

    Re: order statistics

    Quote Originally Posted by sanchez_masherano View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured