Link to home
Create AccountLog in
Avatar of Scott McDaniel (EE MVE )
Scott McDaniel (EE MVE )Flag for United States of America

asked on

Assigning random values from a fixed pool across 3 "columns" without duplication

I'm doing this in VB.NET with an Access database as the data store.

The project is an application which will be used to track the results of a cooking contest. Teams enter this contest and can choose multiple categories. Judges also sign up for the contest and can be assigned to judge multiple categories. For purposes of this discussion, however, I'm only working with a single category.

Each Category has 3 "rounds" of judging. Judges will visit 3 different Teams, evaluate their product, and assign scores to each Team's product.

My problem is coming up with a solid routine for routing the Judges to each Team for those 3 Rounds of Judging.

These are the parameters:

1) There are always exactly the same amount of Judges as there are Teams in a Category. If there are not, the contest cannot be completed.

2) A Judge cannot judge the same team twice for a particular category.

3) If at all possible, avoid duplication of judges between Teams, so that no Teams share more than a single Judge.

#3 is where I'm having trouble. I don't believe it's possible to avoid duplication when I have 6 or fewer teams. At that number, I will have AT LEAST two teams who will share 2 Judges. I'm not sure of the mathematical formula that will prove or disprove this, however, so I'd love to hear some input on it.

As an example, consider where we have 6 Teams (1 - 6) and 6 Judges (A - F). The Matrix below would represent a typical judging:

Team#  Round1  Round2  Round3
------------------------------
1         A      F       E
2         B      D       F
3         c      E       D
4         D      A       C
5         E      B       A
6         F      C       B

So in the matrix shown, Team1 is being judged by Judges A, F and E. Team2 is judged by Judges B, D and F.

Note that Teams 3 and 4 share Judges C and D, and Teams 1 and 5 share Judges A and E. It would be very nice if that sort of duplication could be avoided, but again I'm not sure that can happen.

It's similar to a Sudoku puzzle, except we have only Rows and Columns. I've worked with the concept of "Candidates", where we gather all legitimate "Candidates" for a Team + Round. That pool of Candidates would of course change as the matrix is filled.
Avatar of phoffric
phoffric

>>  3 "rounds" of judging
>> consider where we have 6 Teams (1 - 6) and 6 Judges (A - F)
ok

>> Judges will visit 3 different Teams
  -- For your matrix, it looks like judges visit 6 teams

For this consideration, there are 6C3 ways to pick 3 judges for a team for 3 rounds.
6C3 = 6!/(3!3!) = 20
Here are the 20 ways:
ABC
ABD
ABE
ABF  -- ab
ACD
ACE
ACF -- ac
ADE
ADF -- ad
AEF -- ae
BCD
BCE
BCF -- bc
BDE
BDF -- bd
BEF -- be
CDE
CDF -- cd
CEF -- ce
DEF -- de

Open in new window

Let's arbitrarily pick the first judge selection for team 1 for the 3 rounds (i.e., ABC). Then you do not wish to see AB, AC, or BC for any other teams. The next eligible selection is ADE. The next is AEF, and finally, BDF:
ABC --> AB  AC     BC
ADE --> AD  AE            DE
AEF -->     AE  AF            EF
---
BDF -->            BD BF  DF
---

Open in new window

And for this scenario, you see that you can only get four teams that share only one judge for the three rounds.
Avatar of Scott McDaniel (EE MVE )

ASKER

<-- For your matrix, it looks like judges visit 6 teams>

You're correct. What I meant to convey was that each Judge will vist 3 Teams. There are 6 Teams and 6 Judges, and a single judge will visit 3 distinct teams for each Category. Conversely, each Team will be visited by 3 Distinct Judges.

Thanks very much for your formula. From that formula: 6!/(3!3!) it looks as if the "magic number" would be 7, which would change the formula to 7!/(3!3!), resulting in 5040/36= 140 possible combinations. Is my thinking correct?

Thanks for taking the time to review this. If you have any other input I'd love to hear it.

My coding strategy will be to gather all Teams and Judges (via a List Of structure in VB.NET, or a simple Array), and then loop through the Team list and assign Judges from available Candidates. The first assignment will be straight forward, and just consist of randomly choosing a Judge to associate with a Team.

In the second round, each team would choose from the same pool of Judges, with the obvious caveat that the Judge assigned to that Team in Round 1 would be excluded.

The Third round would be the same, and if we get more than 7 teams (which is almost always the case) there could be situations where I have to backtrack and redo the assignments for Round 2, since it's entirely possible that I could end up with NO viable candidates as I get to the end of my Teams for Round 3 (it happens now, with the current system that is being replaced).

The formula would not be 7!/(3!3!), it would be 7!/(3!4!),
It's like this: x!/(3!(x-3)!) where x is the number of teams/judges and 3 is the number of rounds
Here is my understanding of your problem:

A contest consists of 3 rounds.
Given: There are N teams, N judges (N = 6,7,...)

1. A Judge cannot judge the same team twice in the three rounds.
2. Each judge scores 3 teams.
3. No Teams share more than a single Judge in the three rounds.

For the case, N=7, there are 7C3 = 7!/(3!(7-3)!) = 7!/(3!4!) = 35  ways to select three judges.

Here is an enumberation of the 35 ways:
ABC
ABD
ABE
ABF
ABG  -- ab  
ACD  
ACE  
ACF
ACG -- ac  
ADE
ADF
ADG -- ad  
AEF
AEG -- ae  
AFG -- af
BCD  
BCE  
BCF
BCG -- bc  
BDE
BDF  
BDG -- bd  
BEF
BEG -- be  
BFG -- bf
CDE  
CDF
CDG -- cd  
CEF
CEG -- ce  
CFG -- cf
DEF
DEG -- de
DFG -- df
EFG -- ef

Open in new window



One solution for N=7 is:

ABD 124
BCE 235
CDF 346
DEG 457
EFA 561
FGB 672
GAC 713

Open in new window


The right hand table with numbers correspond as: 1~A, 2~B, etc.
In general you can randomize the correlation to distribute the judges differently for each category.
What I would do is determine one static solution/schedule for possible number of teams. Then for each category, randomly assign each team a number and each judge a letter. That way the scedule is different each time but you don't need to recalculate anything.

If you want to leave them all with the same numbers and letters, then you could take the solutions and randomly swap letters (change all As to Bs and Bs to As etc).
Thanks very much for your input. I'm reviewing now and will comment further in a bit.
Firstly, although the conclusion that for n=6, there is no solution satifying your point #3, I included AEF which is inconsistent with the previous entry of ADE. Here is the correct formulation. You see that four teams are covered OK, but the remaining choice, DEF has both DE and EF, so it is invalid.
ABC AB AC       BC
ADE      AD AE               DE
---  
BDF               BD BF        DF
---
CEF                    CE CF     EF
---

Open in new window

So, there are not solutions for all values of n. The above is formulated as a matrix of 6 rows (for the 6 teams), and 15 columns (for all combinations of two judges selected from 6 judges).

As already noted, there are nC3=n!/(3!(n-3)!) ways to choose 3 judges from n judges.
Since you do not want to have the same two judges scoring two teams, we are also interested in the number of ways of selecting 2 judges out of n; and this is just:
     nC2=n!/(2!(n-2)!)
See attached spreadsheet to see how a matrix is formed (for n=7) with
#Rows = nC3 =  7C3 = 35
#Columns = nC2 = 7C2 = 21

Please review this matrix. You can program this matrix with an auxiliary boolean indicator array having #Columns elements. Here is the methodical approach to solving the n=7 problem (again starting with ABC):
123 ABC AB  AC          BC
145 ADE       AD AE                          DE 
167 AFG            AF AG                               FG
---
246 BDF                   BD     BF            DF
257 BEG                     BE     BG                EG
---
347 CDG                              CD     CG   DG
356 CEF                                CE CF       EF

Open in new window

The numbers correspond to the judges as follows: 1~A, 2~B, etc.
In general you can randomize the correlation to distribute the judges differently for each category. The number of mappings of judges to numbers is just the number of permutations of n, which is n!. For n=7, there are 7! = 5040 ways to arrange 7 numbers. For example, using a ranomizer, suppose your selected permutation is 4736215. In this case the correlation is:
4~A  7~B  3~C  6~D  2~E  1~F  5~G

Open in new window

So, the first entry in the above solution, instead of being ABC (~123) is FEC. (But since FEC is basically the same as EFC - just a change in ordering - the number of permutations with ordering should be adjusting by dividing by 3!; so, we have 5040/6 = 840.)

Your algorithm always starts with ABC. Then set the boolean indicator variables for AB, AC, and BC. Then go to the next string, ABD and consider the digraphs, AB, AD, and BD. Since AB indicator indicates it is used, then discard ABD. (Likewise, all ABx can be discarded.) Discard rows if this rule is a judge is now scoring more than 3 teams. Continue down the rows until every row has been evaluated. Now look at the bottom right-hand corner of the spreadsheet - it has a running total of the number of judges selected for the three rounds. It should add up to 3*n. If it does not = 3*n (as it does not for n=6), then you need more judges.
teams.xls
Note that when you try N=8, all the valid solutions for N=7 still apply. So, all that is needed is one more triplet. Since I looked at N=8 manually, perhaps I made a mistake; however, the best I could do was to include:
678 ~ FGH, which conflicts with  167 ~ AFG. In this last case, having a 9th judge replacing 7~G may be acceptable (although possibly biased).
For your convenience, here is the N=8 spreadsheet. If your check of it indicates that it is correct, then there is no solution that satisfies your requirements (i.e., you would need an extra judge, or another set of rules).
teams8.xls
I really appreciate your input into this. I'm busy examining the spreadsheets and am working through the discussion.

So that you're aware: Replacement judges are not allowed. The number of judges is always equal to the number of teams. If this cannot be done, then we'll have to change the rules and allow duplicates, which is the way the current (but *very* antiquated) system works. My goal with this question was to explore whether the concept of "no duplication after n number of Teams/Judges" is mathematically possible and, if so, implement it in the new system. The current system simply uses a pre-defined matrix, and doesn't randomize things at all (it's also writting in QBasic). If you enter the same teams and judges in the same order, you'll get exactly the same matrix + pairings each time. Obviously that is to be avoided, and is the ultimate goal of my question.
SOLUTION
Avatar of TommySzalapski
TommySzalapski
Flag of United States of America image

Link to home
membership
Create an account to see this answer
Signing up is free. No credit card required.
Create Account
Oh, I see that you are familiar with VBA. I could have used VBA-like pseudo-code, but since you are a genius, I doubt that's needed.
For N=8, what triplet would you add to the N=7 solution (see 2nd table in http:#34468518)?
As a brief aside, not sure what you meant by a "lot of randomizing". The shuffle, which is fine, is just an implementation approach to yield a random permutation. Anyway, the permutation issue is really OT.
Oops. Slight adjustment. For even numbers, you can't use all the unique pairings since one gets wasted for each level. So for even x you need x!/(2!(x-2)!) - x >= 3x
->
x^2 - x - 2x >= 6x
->
x - 3 >= 6
->
x >= 9

So odd numbers >=7 will work and even numbers >= 10 will work. For 8 and < 7, you will need to adjust somehow.
>>not sure what you meant by a "lot of randomizing"

Just that from initial analysis, it seems like it would take quite a bit of work to randomize while solving. Shuffling is easy and efficient. That's all. Just seems like it'd be easier to take that approach. Actually, now that I'm thinking about it, shuffling should give you every possible permutation.
Shuffling does give every possible permutation. It should be used only after the first solution is determined. Agree that there is no need to complicate the algorithm by randomizing while solving - never meant to imply that.
The above analysis also tells you how many duplicates you will end up with.
Recall for odd x, x >= 7, for even x, x>=9
So if x is 6 then since 9-6 = 3, you will need three pairings that cause duplicates.
If x is 5 then since 7-5 = 2, you will need two duplicate pairs.

As long as you specify that no judge is paired twice, then the shuffling at the end will give every possible arrangement of teams and judges. (If you allow it then shuffling won't change whether or not that has happened in the assigning so some outcomes would not happen)

If x is 3 or 4 then you would have a lot or duplication.
So if I take as fact that the following equation will give me the number of uniqe triplet combinations for a given number of Teams:

x!/(3!(x-3)!)

Then it would seem that 8 Teams would have a total of 56 unique triplets, which is > 8*3 - or am I misunderstanding the equation? If I understand it, then it would make sense that I could have unique triplet combinations at 8 Teams (??)

I've moved a LOT further along in my quest, thanks entirely to the efforts of both of you. Thanks again ... I truly appreciate it!

>> 8 Teams would have a total of 56 unique triplets, which is > 8*3
true, 56 > 24. So far, so good.

>> it would make sense that I could have unique triplet combinations at 8 Teams
again, true; but some of these unique triplet combinations violate your rule #3, which is that the 3 digraphs within a triplit also be unique across the 8 teams.

To illustrate the issue (which you actually identified in your OP), look at the posted teams8.xls. "123" and "124" are distinct triplets, but they share the digraph "12".
You got my equations a little mixed I think. The number of triplets is fine. You'll never need the same TRIPLET twice since 56 > 8. But you are concerned with duplicate pairs. There are x!/(2!(x-2)!) unique pairs. So that's 28. But since it's an even number that means 1 can be paired with an odd number of other numbers so after you've made 3 triples with 1 (1,2,3) (1,4,5) (1,6,7) you can never pair 1 with 8 without making a duplicate. So you loose x pairs with even numbers.
So you have x!/(2!(x-2)!)  - x which is 20 which is of course < 24.

I reduced it in a previous post.
For odd x: x>=7 works
For even x: x>=9 works.
So these numbers wil work: 7, 9, 10, 11, 12, 13 etc.
These numbers will require duplicates:
8: 1 duplicate pair
6: 3 duplicate pairs
5: 2 duplicate pairs
4: 5 duplicate pairs (work it out if you don't believe me) but 4!/(3!1!) = 4>=4 so no duplicate TRIPLES
3: Oops 3!/(3!0!)=1 which is not >= 3 so you would have duplicate triples (obviously, since there is only one)
And of course it breaks down completely for anything less than 3.
<again, true; but some of these unique triplet combinations violate your rule #3, which is that the 3 digraphs within a triplit also be unique across the 8 teams.>

That's where I was confused. I again reviewed the Excel sheet several times, and it became more clear. Thanks for clearing that up.

So I can safely assume this, with regard to my Rule #3:

If the contest includes 7 Teams, or 9 or more teams I can proceed with a "no duplicate" strategy. If the contest includes less than 7 Teams, or exactly 8 Teams, then we will have some level of duplication.



Correct.
Again. If you find one solution and shuffle the numbers and letters it will give you every possible solution with identical probability for each one.
ASKER CERTIFIED SOLUTION
Link to home
membership
Create an account to see this answer
Signing up is free. No credit card required.
Create Account
From looking at phoffric's 8 matrix, it looks to me as if I can route 8 judges to 8 teams over 3 rounds with nothing more than single judge duplicates:
                  
1	2	4	
2	3	5	
3	4	6	
4	5	7	
5	6	8	
6	7	1	
7	8	2	
8	1	3	

Open in new window

I don't see any duplicates in there (other than single-judge duplicates) but perhaps I'm missing something

Here's another matrix with 20 entries:                  
	1	2	4
	2	3	5
	3	4	6
	4	5	7
	5	6	8
	6	7	9
	7	8	10
	8	9	11
	9	10	12
	10	11	13
	11	12	14
	12	13	15
	13	14	16
	14	15	17
	15	16	18
	16	17	19
	17	18	20
	18	19	1
	19	20	2
	20	1	3

Open in new window

It seems that if take an approach like this:

1) Build the first column starting at 1 and ending at [Number of Teams]
2) Build the second column starting at 2, proceeding through to [Number of Teams] and then start back at 1
3) Build the third column starting at 4, proceeding through to [Number of Teams], then start back at 1

That so long as I have more than 7 teams, I can build ANY matrix very quickly, and then just randomly assign teams/judges to those matrix elements as needed. This would avoide doubling up on judges across any two triplets. If I have less than 7, I'll definitely have doubles across one or more triplets.


                  


Ah, yes. I see the issue. For even x, you can only pair each number with an odd number of others as already stated. However, if you choose the skipped ones carefully, then you only lose x/2 pairs. Just pick the pairs to skip so that no number is in two skipped pairs. Since there are and even number, this will always be possible.

So the modified formula is (for even x):
x!/(2!(x-2)!) - x/2 >= 3x. So for 8 that's 24 >= 24 which means you can barely skate by. Sorry for missing that earlier.

Of course that reduces to x>=8 for even x.
It can also be proven that phoffric's design works for >7
I'm going to use x%y to mean x modulo y (from C syntax)

Lets say we have x teams/judges
The three judges in a set are always a, (a+1)%x, (a+3)%x

So all the judges that can be paired with a are (a+1)%x, (a+2)%x (when a+1 is the first in the set), (a+3)%x, (a-1)%x, (a-2)%x, and (a-3)%x.

An easer way of looking at this is to imagine the judges sitting in a circle in order (so 1 is next to x) the judge can only be paired with the ones three spaces to the left or the right. So if the circle has 7 or more judges then there will naver be a duplicate.
It also can be observed that for x < 7 the following good things are true.
Every single pairing is used.
There are no repeated duplicates.
Each judge is in the exact same number of duplicate sets.

Nice job, phoffric. This is definitely the solution. I can prove that there is no better solution given the constraints set in this question.

Thanks :)

>> there could be situations where I have to backtrack
I initially used the spreadsheet to be informative. But I became too comfortable with it w.r.t. the pairing problem while losing sight of your other goal to have each judge score 3 teams (and ideally, exactly 3 teams). I found solutions that solved the pairing issue, but which did not evenly distribute the judges amongst the teams. I was going to consider a backtrack approach to achieve this latter goal; but whenever beginning to change an algorithm's basic structure (i.e., more than another tweak), it is time to take a step back to look for a simpler one. Naturally, I also didn't like the N=8 exclusion principle which would be kind of hard too explain (and leading to potential embarrassment) to the contest organizers. That motivation led to my previous post.


Observations about the http:#34483924 pattern:
Here is a view as to why it works (proof by pattern observation with concrete example - abstractions and rigor later if you need to write a paper):
The even distribution of judges should be apparent. Each judge appears 3 times in the table.
2 adjacent rows have one shared judge (namely, Rnd2 of a row matches Rnd1 of next row), where last row wraps around to first row.
Numbered Judges are in ascending order in each row (except for the last 3, so consider them separately).
Rnd1/Rnd2 obviously have no duplicate pairs across all rows when considering only Rnd1 and Rnd2.
---
Below is a copy of the table where N=20.
Consider Row 4 - "457" has pairs: 4/5, 4/7 and 5/7
4/5: 5 appears 3 times (Row 4, 5, and 2)
Row 5: 5 is in Rnd1, so Rnd2 & Rnd3 are > 5, so cannot have a 4
Two rows up, Row 2: 5 is in Rnd3, but Rnd3 number is not sequential with Rnd2, so the 4 is not in Row 2.
 So 4/5 only exists in Row 4

4/7:
4 is 3 rows up in Rnd3, so other numbers < 4
4 is in previous row in Rnd2, but Rnd3 cannot have the 7 since Rnd3 is sequential.
 This accounts for the three 4's, and only one is paired with a 7.

5/7:
5 is 2 rows up in Rnd3, so other numbers < 5
5 is in next row in Rnd1, and Rnd1/Rnd2 is sequential (giving a 6 for Rnd2) and again, Rnd3 is sequential down the table (so it must be 8)
   So, 5/7 only exists in Row 4

Similar words for the last 3 rows, but now you have to consider wrap-around to the first couple of rows.

BTW - I saw your name on an EE email Newsletter - congratulations on making The Philanthropist list! So, I looked up your profile. I also worked at GSFC for about 6 months a long time ago. My family is considering a move to the MD area this year. If you are still in that area, maybe I'll contact you.
1       2       4  
2       3       5  
3       4       6  
4       5       7  
5       6       8  
6       7       9  
7       8       10  
8       9       11  
9       10      12  
10      11      13  
11      12      14  
12      13      15  
13      14      16  
14      15      17  
15      16      18  
16      17      19  
17      18      20 
18      19      1  
19      20      2  
20      1       3

Open in new window

Thanks for the confirmation, and thanks again for your diligence in helping me come to this conclusion. I don't need to write a paper, just need to be able to convince the "powers that be" that the pairings are as unique as possible :) .

As far as the similiarities between adjacent rows (i.e. Team1 shares a judge with Team2, Team2 with Team3, etc) - I don't see that as in issue in regard to the final outcome. So long as we have unique triplets of judges where possible, I plan on using the .NET Randomize function to shuffle the order of my Teams and Judges immediately prior to assigning the Judges to each Team.

<BTW - I saw your name on an EE email Newsletter - congratulations on making The Philanthropist list! So, I looked up your profile. I also worked at GSFC for about 6 months a long time ago. My family is considering a move to the MD area this year. If you are still in that area, maybe I'll contact you.>

Thanks for that. I've made the list a few times in that category and it's something I'm quite proud of! Many of the Experts in my preferred Zones (Microsoft Access) are quite point-conscious, so I long ago decided to just answer the question without even considering point values. It's made my experience on EE much better.

I live far south of GSFC, but do a fair amount of work with several aerospace firms in the area, and with GSFC proper. I haven't visited there in about a year (which is good, I guess - means all the systems I put in place are working!) but will likely be in the area sometime in the next 9 - 12 months. If I end up visiting I'll certainly contact you.

Thanks again for your help. It's been invaluable, and has allowed me to jumpstart the project and remain on track for deadline.

I'll close this out later today/tomorrow. Had a workstation crash, and the new one is ready now so I'll be putting that back together for the duration of the day.
You are very welcome. :)

>> As far as the similiarities between adjacent rows (i.e. Team1 shares a judge with Team2, Team2 with Team3, etc) - I don't see that as in issue in regard to the final outcome.
    Right, not an issue. This remark was part of the loosely worded proof that you will get a unique triplets of judges for all N>6. It is part of the distance idea that I used to come up with the pattern. We want each judge to appear 3 times, and I wanted them to be clustered as close as possible for easy analysis of the pattern.

    Well, good luck completing the task!
Thanks again, and sorry for taking so long to close this out. My workstation was gasping for breath, and my new one was finished up just as this question was being finalized.

Thank you both again for your efforts. Hope I've awarded points fairly, and you have my undying gratitude!
Glad to have helped. :)