4
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ 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)? $\endgroup$
    – Chris
    Feb 13, 2012 at 21:52
  • $\begingroup$ @Chris No, order doesn't matter. It would count for both of them. $\endgroup$
    – Shef
    Feb 13, 2012 at 21:54
  • $\begingroup$ 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. $\endgroup$
    – Tyanna
    Feb 13, 2012 at 22:05
  • $\begingroup$ @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. $\endgroup$
    – Shef
    Feb 13, 2012 at 22:08
  • 3
    $\begingroup$ @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. $\endgroup$ Feb 14, 2012 at 4:39

5 Answers 5

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Shef
    Feb 13, 2012 at 22:25
2
$\begingroup$

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.

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

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

$\endgroup$
8
  • $\begingroup$ 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". $\endgroup$
    – Shef
    Feb 13, 2012 at 21:47
  • $\begingroup$ 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. $\endgroup$
    – psr
    Feb 13, 2012 at 21:52
  • $\begingroup$ @Shef this makes it much clearer what they want, I'll have to edit my answer. $\endgroup$
    – Ryathal
    Feb 13, 2012 at 21:54
  • $\begingroup$ @psr Yes, you are right. The most common group should be found, not the most common individual set-members. $\endgroup$
    – Shef
    Feb 13, 2012 at 21:56
  • $\begingroup$ @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. $\endgroup$
    – Shef
    Feb 13, 2012 at 22:00
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 } ? $\endgroup$ Feb 13, 2012 at 23:00
  • $\begingroup$ yes, only repeated sequences. I missed the comment about the ordering. $\endgroup$
    – akostajti
    Feb 13, 2012 at 23:11
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$ Feb 14, 2012 at 1:32
  • $\begingroup$ How is list<list<int>> pseudocode? $\endgroup$
    – Janoma
    Feb 14, 2012 at 13:12
  • $\begingroup$ @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. $\endgroup$ Feb 14, 2012 at 13:54
  • $\begingroup$ @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)? $\endgroup$ Feb 14, 2012 at 14:07
  • $\begingroup$ @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. $\endgroup$ Feb 14, 2012 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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