Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Can someone suggest a good algorithm for the following problem (or a reference to look up)?

You have a set of numbers from 1 to $m$ (m=80) (inclusive). $n$ (=20) non-repeating numbers will be drawn from the set in an increasing order in a single draw. There will be 2 to N draws, and you will have the results of those draws. Design an algorithm, which will find the most and the least repeated group ($N$-members) of numbers in the draws.

Sample draws

1) 4   5   7   19  28  32  39  40  43  44  46  47  48  49  55  56  59  69  73  79
2) 1   10  11  19  20  27  32  35  41  42  46  49  51  54  58  61  63  67  68  76
3) 3   4   5   8   11  16  24  25  27  34  37  48  49  50  57  58  59  68  71  73
4) 1   8   10  13  18  26  27  30  32  35  45  46  49  52  53  61  66  72  75  78
5) 7   14  20  21  25  26  38  40  43  46  49  53  54  58  60  61  66  68  74  80

Further explanation

The algorithm should find the most repeating group of N-numbers (say 3 numbers). So, basically a tuple of three numbers that is repeated the most in the draws must be found. it is also possible that there will be a most/least common group of $N$-members, but it is quite as possible that there won't.

share|improve this question

migrated from programmers.stackexchange.com Feb 13 '12 at 23:23

This question came from our site for professional programmers interested in conceptual questions about software development.

    
Does order matter in the three-tuple? For example, would the first set count towards (4, 19, 28), or only count for (5, 7, 19)? –  Chris Feb 13 '12 at 21:52
    
@Chris No, order doesn't matter. It would count for both of them. –  Shef Feb 13 '12 at 21:54
    
I feel the question is oddly worded. Is that the question verbatim, or are you reciting it from memory? If I had of been given this interview question I would have asked for some clarification. –  Tyanna Feb 13 '12 at 22:05
    
@Tyanna I am reciting it from memory, but I think I am recalling it as it was. They clarified what I have added there in the clarification, and they also said that it is also possible that there will be a most/least common group of N-members, but it quite as possible that there won't. –  Shef Feb 13 '12 at 22:08
3  
@Kaveh: This question was crossposted at least on cstheory (question 10188) and math (question 109036) before this one was migrated here from programmers. I do not know what made you think the migration was reasonable. –  Tsuyoshi Ito Feb 14 '12 at 4:39

5 Answers 5

up vote 3 down vote accepted

First, count the occurences of each number overall, and call it C(x):

1: 2
2: 0
3: 1
4: 2
etc ...

Next, we want to find the most common pairs. We know that any pairs C(x, y) <= Min(C(x), C(Y)). Using this we can find the Y "most likely" pairs. We then run through the sequences and count these most likely pairs. As long as the C(most likely pair) is greater than the estimate for the Y'th most likely pair, we know we have found the most common pair. If it isn't, we generate the next Y most likely pairs and then count those as well.

We can extend this to sets of three: C(x, y, z) <= Min(C(x, y), C(x, z), C(y, z)). So for this to work, we need to keep calculating the most common pairs until we find three pairs that we can chain into a triplet. We then need to keep going until we prove that all other triples must have a lower count, following the same logic as used by pairs.

It's basically a heuristic guided search of the possible solutions.

share|improve this answer
    
Hmm... thanks for the answer. I am too tired to wrap my head around this at the moment. I will take a bite at it in 8 hours most probably. –  Shef Feb 13 '12 at 22:25

I'll try to weasel out of a proper answer - they don't specify the algorithm performance, so this will be horrible.

Just brute force a count for each combination of N items found. For each 20 item draw choose all subsets of N items. Each such set is fixed once the N items are chosen, so you could use a hash-table to store them - say as the key of a dictionary data-type, where the value is the number of times it appears in a draw (so each time you see that subset, look for the key, if it's not there create it and if it is increment it). When you are done with all draws, sort by value.

If N=10 each draw produces (20*19*18*17*16*15*14*13*12*11)/10! such subsets (184756) so, not great. But they asked for an algorithm, not a good algorithm. They can send me the job offer via programmer's chat.

share|improve this answer
    
Order doesn't matter, so that number sould be 20 choose 10, or 20!/(10!10!) = 184756. Still a large number, but more tractable. –  Chris Feb 13 '12 at 22:22
    
@Chris - thank you. In theory I knew that. I'll edit. –  psr Feb 13 '12 at 22:28
1  
That is quite reasonable, you should be able to generate and count 184K combinations in less than one second per draw. –  kevin cline Feb 13 '12 at 23:04

find the most and the least repeated group (N-members) of numbers in the draws.

E.g. if the most repeated number is 35, and the 2nd most repeated is 4, the 3rd most repeated is 72, then for N=3, the group of the 3 most repeated numbers is {35, 4, 72}.

share|improve this answer
    
Thanks for the answer. Hmm... that's easy! I asked if it was that, but the answer was no. They wanted to find a group that repeats in all the draws. Let's take an example with 10 numbers drawn. Say if N=3, then if we had the draws: 1st = "1 2 5 9 15 50 66 70 72 79", 2nd = "3 5 7 8 9 12 15 25 36 54", 3rd = "5 6 9 11 15 29 31 42 51 80", 4th = "2 4 5 9 13 15 63 72 77 78", ... Then, the most repeated group of 3-members would be "5 9 15". –  Shef Feb 13 '12 at 21:47
    
Uh, I think you are both not quite right. The group doesn't have to repeat in all the draws, but the entire group must be in the draw the count. So, in 1 million draws, 500,000 could have 1 and 2, and the other 500,000 could have 3, making 1,2, and 3 the 3 most common, individually. But 4,5,6 might appear as a group 400,000 times, but none of them might ever appear separately, so they are the most common group but not individually the most common. –  psr Feb 13 '12 at 21:52
    
@Shef this makes it much clearer what they want, I'll have to edit my answer. –  Ryathal Feb 13 '12 at 21:54
    
@psr Yes, you are right. The most common group should be found, not the most common individual set-members. –  Shef Feb 13 '12 at 21:56
    
@PéterTörök They want the most common group of N-members, there could also be no group at all of N-members that repeats in two or more draws. –  Shef Feb 13 '12 at 22:00

Although I didn't try it I think the problem can be solved using the lempel-ziv-welch algorithm. This is a compression algorithm that uses a dictionary. I think you can work out the solution with two slight modifications on the algorithm:

  • you have to apply the algorith to each row separately but with keeping the dictionary
  • you have to count the number of occurrences of each entry in the dictionary

You can find the description of the algorithm here And this is an animation that makes it easier to understand 2

share|improve this answer
    
Won't this technique find only repeated sequences, not repeated subsets? How would it find { 1, 3, 5 } given { 1, 2, 3, 5 } and { 1, 3, 4, 5 } ? –  kevin cline Feb 13 '12 at 23:00
    
yes, only repeated sequences. I missed the comment about the ordering. –  akostajti Feb 13 '12 at 23:11

The most straightforward method I can think of is to just iterate over the list and add the tuples to a hashtable where the key is the tuple, and the value is the count of how many times it's been found.

In pseudocode:

list<list<int>> draws
foreach draw in draws
    for i = 0 to draw.length - 3
        tuple = new tuple(draw[i], draw[i+1], draw[i+2])
        if tuples.Contains(tuple)
            tuples[tuple]++;
        else
            tuples.add(tuple, 1)

After that, you get the key with the highest value.

share|improve this answer
    
The problem is supposed to find the most common N element subset of all the draws, so a valid tuple from 1 through 20 would include (1, 2, 3) as well as (1, 5, 19) –  Chris Pitman Feb 14 '12 at 1:32
    
How is list<list<int>> pseudocode? –  Janoma Feb 14 '12 at 13:12
    
@Chris: Yes I know. The implementation doesn't use the index in the tuple, it uses the numbers in the draw at those indexes (i, i+1, i+2). Note: I've written the implementation, and it works. –  SnOrfus Feb 14 '12 at 13:54
    
@SnOrfus You are solving thr wrong problem. It is not to find the most common sequence in the draws. In the first draw in the problem, how would your solution find the tuple (5, 39, 43)? –  Chris Pitman Feb 14 '12 at 14:07
    
@Chris: Hmm... Looking at the comments on the question, it seems you're right. From the question, as it was posted on programmers, it sounded like they were looking for in-order tuples. –  SnOrfus Feb 14 '12 at 14:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.