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

<pre><code>1: 2
2: 0
3: 1
4: 2
etc ...
</code></pre>

<p>Next, we want to find the most common pairs. We know that any pairs C(x, y) &lt;= 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.</p>

<p>We can extend this to sets of three: C(x, y, z) &lt;= 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.</p>

<p>It's basically a heuristic guided search of the possible solutions.</p>

CC BY-SA 3.0
2012-02-13T22:25:44.353Z
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
CC BY-SA 3.0
2012-02-13T22:00:46.970Z
2012-02-13T22:00:46.970Z
Chris Pitman
<p>I'll try to weasel out of a proper answer - they don't specify the algorithm performance, so this will be <em>horrible</em>.</p>

<p>Just brute force a count for each combination of N items found.  For each 20 item draw choose <em>all</em> 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.</p>

<p>If N=10 <em>each</em> 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. </p>

CC BY-SA 3.0
2012-02-13T23:04:59.373Z
That is quite reasonable, you should be able to generate and count 184K combinations in less than one second per draw.
kevin cline
CC BY-SA 3.0
2012-02-13T22:14:43.167Z
2012-02-13T22:29:56.330Z
psr
<p>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. </p>

<p>In pseudocode:</p>

<pre><code>list&lt;list&lt;int&gt;&gt; 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)
</code></pre>

<p>After that, you get the key with the highest value.</p>

CC BY-SA 3.0
2012-02-14T01:32:32.177Z
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
CC BY-SA 3.0
2012-02-14T13:12:24.687Z
How is `list<list<int>>` pseudocode?
Janoma
CC BY-SA 3.0
2012-02-14T13:54:42.087Z
@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.
Steven Evers
CC BY-SA 3.0
2012-02-14T14:07:54.197Z
@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
CC BY-SA 3.0
2012-02-14T14:18:20.210Z
@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.
Steven Evers
CC BY-SA 3.0
2012-02-14T00:51:42.393Z
2012-02-14T00:51:42.393Z
Steven Evers
<p>Can someone suggest a good algorithm for the following problem (or a reference to look up)?</p>
<p>You have a set of numbers from 1 to <span class="math-container">$m$</span> (m=80) (inclusive). <span class="math-container">$n$</span> (=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 (<span class="math-container">$N$</span>-members) of numbers in the draws.</p>
<blockquote>
<p>Sample draws</p>
<pre><code>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
</code></pre>
</blockquote>
<h3>Further explanation</h3>
<p>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 <span class="math-container">$N$</span>-members, but it is quite as possible that there won't.</p>

CC BY-SA 3.0
2012-02-13T21:54:41.643Z
@Chris No, order doesn't matter. It would count for both of them.
Shef
CC BY-SA 3.0
2012-02-13T22:08:38.493Z
@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
CC BY-SA 3.0
2012-02-13T23:41:56.973Z
The question was migrated after asking if it would be suitable for cstheory. I agreed since designing fast algorithms for finding similar statistics is an interesting research area in algorithms.
Kaveh
CC BY-SA 3.0
2012-02-13T23:46:02.253Z
@Kaveh Thanks. There are some answers already, I need to test them to see where we are at. However, I need to get some off time before I can do that. Let's hope in the meantime someone else will jump in and steer the ship some more. :)
Shef
CC BY-SA 3.0
2012-02-14T00:40:52.863Z
you are welcome. :) I am a little bit concerned that the question might not be as research-level as people would like here but I am hoping that will not be the case. In the worse case we can migrate it back. I think the question would be more on-topic if it was asking for a more restricted class of algorithms, say [streaming algorithms](http://en.wikipedia.org/wiki/Streaming_algorithm) for huge amounts of data. Just one clarification question: is the group of the numbers required to be consecutive?
Kaveh
CC BY-SA 3.0
2012-02-14T04:39:02.880Z
@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
CC BY-SA 3.0
2012-02-14T09:10:06.487Z
The problem statement is unclear.  Is N the number of trials, the size of the target subset, or both?  Which parameters are fixed in advance, and which are given as part of the input?  (And since all paramaters are constants, why isn't "O(1) by brute force" the obvious correct answer?)
Jeffε
CC BY-SA 3.0
2012-02-14T12:08:31.747Z
@JɛﬀE The capital N is the size of the target subset. The set (1 - 80) is fixed in advance. N and the draws are given as part of the input.
Shef
CC BY-SA 3.0
2012-02-14T13:00:56.630Z
@Tsuyoshi, I did see the copy on cstheory and your comment there before agreeing. I didn't see the copy on [math.se]. The OP had deleted the copy on cstheory so not migrating because of a previous cross-posting didn't seem to be a good reason.
Kaveh
CC BY-SA 3.0
2012-02-27T13:56:10.070Z
@Shef Did you get the answers you are looking for, or are they missing something?
Chris Pitman
CC BY-SA 3.0
2012-03-01T08:47:18.587Z
@Chris I didn't have the time to test this scenario yet. However, your answer seems to be the most logical one, so I am accepting that as the answer.
Shef
<ds.algorithms>
Find the most/least repeated group of N-members in given draws
Shef
# Find the most/least repeated group of N-members in given draws

(Asked by: username_0 on 2012-02-13)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_0**: @Chris No, order doesn't matter. It would count for both of them.  
> **username_0**: @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.  
> **username_1**: The question was migrated after asking if it would be suitable for cstheory. I agreed since designing fast algorithms for finding similar statistics is an interesting research area in algorithms.  
> **username_0**: @username_1 Thanks. There are some answers already, I need to test them to see where we are at. However, I need to get some off time before I can do that. Let's hope in the meantime someone else will jump in and steer the ship some more. :)  
> **username_1**: you are welcome. :) I am a little bit concerned that the question might not be as research-level as people would like here but I am hoping that will not be the case. In the worse case we can migrate it back. I think the question would be more on-topic if it was asking for a more restricted class of algorithms, say [streaming algorithms](http://en.wikipedia.org/wiki/Streaming_algorithm) for huge amounts of data. Just one clarification question: is the group of the numbers required to be consecutive?  
> **username_2**: @username_1: 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.  
> **username_3**: The problem statement is unclear.  Is N the number of trials, the size of the target subset, or both?  Which parameters are fixed in advance, and which are given as part of the input?  (And since all paramaters are constants, why isn't "O(1) by brute force" the obvious correct answer?)  
> **username_0**: @JɛﬀE The capital N is the size of the target subset. The set (1 - 80) is fixed in advance. N and the draws are given as part of the input.  
> **username_1**: @Tsuyoshi, I did see the copy on cstheory and your comment there before agreeing. I didn't see the copy on [math.se]. The OP had deleted the copy on cstheory so not migrating because of a previous cross-posting didn't seem to be a good reason.  
> **username_4**: @username_0 Did you get the answers you are looking for, or are they missing something?  
> **username_0**: @Chris I didn't have the time to test this scenario yet. However, your answer seems to be the most logical one, so I am accepting that as the answer.  

---

## 3 answers

### Answer by username_4 on 2012-02-13. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2012-02-13. Score: 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.

> **Comments:**
> **username_6**: That is quite reasonable, you should be able to generate and count 184K combinations in less than one second per draw.  

---

### Answer by username_7 on 2012-02-14. Score: 0

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

> **Comments:**
> **username_4**: 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)  
> **username_8**: How is `list<list<int>>` pseudocode?  
> **username_7**: @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.  
> **username_4**: @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)?  
> **username_7**: @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.  

---

