Find the most/least repeated group of N-members in given draws

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.