Weekly Group Distribution Algorithm

Question

My friend who has a teacher has 23 students in the class. They need an algorithm that assigns students to groups of 2 and one group of 3 (process an odd number of students) after 14 weeks, so that two pairs do not repeat for 14 weeks (a pair is assigned for one week).

The brute force approach would be too inefficient, so I thought about other approaches, the matrix representation sounds attractive and graph theory. Does anyone have any idea? The problems that I could find concerned only 1 week and this answer I could find out.

Answer 1

The Round-robin algorithm will do the trick I think.

Add the remaining student to the second group, and you're done.

First run 1 2 3 4 5 6 7 8 9 10 11 12 23 22 21 20 19 18 17 16 15 14 13 Second run 1 23 2 3 4 5 6 7 8 9 10 11 22 21 20 19 18 17 16 15 14 13 12 

...

Answer 2

Another option might be schedule matching ; 14 different chart comparisons will be required.

Answer 3

If you are looking for more fun group exercises, you can try this below. He asks students to calculate the logarithmic likelihood.

one

  suppressMessages(library(tidyverse)) load("tennis.Rda") tennis.data$log.ra.rb <- log(tennis.data$RankA/tennis.data$RankB) tennis.data$y <- ifelse(tennis.data$Winner=="A",1,0) tennis.data <- tennis.data[complete.cases(tennis.data[,c("y","log.ra.rb")]),] loglik <- function(p,z){ b0 <- p[1] b1 <- p[2] y <- z[,1] x <- z[,2] pa <- 1/(1+exp(-b0-b1*x)) pb <- 1-pa likelihood <- ifelse(y==1,pa,pb) sum(log(likelihood)) } 

This version of the logos does not check for insufficient numbers. The log-like function is optimized in the following code. Standard errors and confidence interval are derived from the Hessian.

  z <- as.matrix(tennis.data[,c("y","log.ra.rb")]) m <- optim(c(b0=0,b1=1),loglik,control=list(fnscale=-1),hessian=TRUE,z=z) m sd <- sqrt(diag(solve(-m$hessian))) cbind(beta=m$par,sd=sd,lower=m$par+qnorm(0.025)*sd,upper=m$par+qnorm(0.975)*sd) 

Note that the optimization routine does converge. As expected, β0 ≈ 0 and β1 <0.

2

if pA = 0.25, do we find that the winning frequency is approximately 0.25?

  load("tennis.Rda") tennis.data$pA <- 1/tennis.data$B365A tennis.data$pB <- 1/tennis.data$B365B tennis.data$pr.total <- tennis.data$pA + tennis.data$pB summary(tennis.data$pr.total) tennis.data <- subset(tennis.data,pr.total>=1 & pr.total<=1.30 & !is.na(pr.total)) tennis.data$pA <- tennis.data$pA/tennis.data$pr.total tennis.data$pB <- tennis.data$pB/tennis.data$pr.total tennis.data025 <- subset(tennis.data,pA>=0.20 & pA <=0.30) mean(tennis.data025$pA) mean(tennis.data025$Winner=="A") 

make buckets 0.10, and aggregate

  tennis.data$bucket <- cut_width(tennis.data$pA,width=0.10, center=0.05) table(tennis.data$bucket) by_p.A <- group_by(tennis.data,bucket) summarise(by_p.A, mean.freq.A = mean(Winner=="A"),mean.pA = mean(pA)) freqs <- tennis.data %>% group_by(bucket) %>% summarise(mean.freq.A = mean(Winner=="A"),mean.pA = mean(pA),n=n()) freqs ggplot(freqs) + geom_point(aes(x=mean.pA,y=mean.freq.A,size=n)) + geom_abline(intercept=0,slope=1,colour="red") + labs(x="implied winning probability",y="observed winning frequency") 

Apparently, in each segment, the average probability of winning, as the odds of a bookmaker implies, is a very good predictor of the average frequency of winning.

Answer 4

Try to describe the problem in terms of constraints.

Then pass restrictions on a tool such as ECLiPSe (not Eclipse), see http://eclipseclp.org/ .

In fact, your problem seems similar to your problem with Golf on this site ( http://eclipseclp.org/examples/golf.ecl.txt ).

Answer 5

Start with a set (possibly a bit set for students for less memory consumption) for each student who has all the other students. You spend it 14 times, each time selecting 11 students (for 11 groups that you will form) for which you will choose partners. For each student, select a partner with whom they have not yet been in the group. For one random student out of these 11, choose a second partner, but make sure that the student has fewer partners than iterations. Adjust the sets for each selection.

Answer 6

Here is an example in Haskell that will create groups of 14 non-repeating 11-pair combinations. The parameters of the “pair” are all combinations of pairs from 1 to 23 (for example, [1,2], [1,3], etc.). Then the program builds lists in which each list consists of 14 lists of 11 pairs (a choice of a pair of values), so that no pair is repeated and no number is repeated in one list of 11 pairs. You just need to place the missing last student every week, as you see fit. (It took about three minutes to calculate before it starts to output the results):

 import Data.List import Control.Monad pairs = nubBy (\xy -> reverse x == y) $ filter (\x -> length (nub x) == length x) $ replicateM 2 [1..23] solve = solve' [] where solve' results = if length results == 14 then return results else solveOne [] where solveOne result = if length result == 11 then solve' (result:results) else do next <- pairs guard (notElem (head next) result' && notElem (last next) result' && notElem next results') solveOne (next:result) where result' = concat result results' = concat results 

One sample output:

 [[[12,17],[10,19],[9,18],[8,22],[7,21],[6,23],[5,11],[4,14],[3,13],[2,16],[1,15]], [[12,18],[11,19],[9,17],[8,21],[7,23],[6,22],[5,10],[4,15],[3,16],[2,13],[1,14]], [[12,19],[11,18],[10,17],[8,23],[7,22],[6,21],[5,9],[4,16],[3,15],[2,14],[1,13]], [[15,23],[14,22],[13,17],[8,18],[7,19],[6,20],[5,16],[4,9],[3,10],[2,11],[1,12]], [[16,23],[14,21],[13,18],[8,17],[7,20],[6,19],[5,15],[4,10],[3,9],[2,12],[1,11]], [[16,21],[15,22],[13,19],[8,20],[7,17],[6,18],[5,14],[4,11],[3,12],[2,9],[1,10]], [[16,22],[15,21],[14,20],[8,19],[7,18],[6,17],[5,13],[4,12],[3,11],[2,10],[1,9]], [[20,21],[19,22],[18,23],[12,13],[11,14],[10,15],[9,16],[4,5],[3,6],[2,7],[1,8]], [[20,22],[19,21],[17,23],[12,14],[11,13],[10,16],[9,15],[4,6],[3,5],[2,8],[1,7]], [[20,23],[18,21],[17,22],[12,15],[11,16],[10,13],[9,14],[4,7],[3,8],[2,5],[1,6]], [[19,23],[18,22],[17,21],[12,16],[11,15],[10,14],[9,13],[4,8],[3,7],[2,6],[1,5]], [[22,23],[18,19],[17,20],[14,15],[13,16],[10,11],[9,12],[6,7],[5,8],[2,3],[1,4]], [[21,23],[18,20],[17,19],[14,16],[13,15],[10,12],[9,11],[6,8],[5,7],[2,4],[1,3]], [[21,22],[19,20],[17,18],[15,16],[13,14],[11,12],[9,10],[7,8],[5,6],[3,4],[1,2]]]