I have 16 teams that have already played 6 games. There are data with which teams they have already played. Here is:

enter image description here

The task is to generate unique pairs of teams that will play the following games or at least the game. It is important that these teams have not played Durg with a friend before.

I write everything in JS, but if there is a solution in another language, this is not a problem. What will be the algorithm? How to solve this problem?)

  • Take a list of teams and remove from there the teams that have already played. This will give you "at least a game" - Vladimir Martyanov
  • This is understandable, but it does not solve the problem in any way, it only simplifies a little) - Dimmi
  • How does this "not solve"? If this operation is repeated for all teams, you will receive a list of possible partners for all teams. - Vladimir Martyanov
  • Now I will try for each team. But so far I still do not understand the decision. - Dimmi
  • @ Vladimir Martianov I think that the author has in mind under the game - 8 pairs of teams, but in general there may not be such people. For the time being, it seems to me that there is something in the problem of a bipartite graph - type, from the originally complete graph on each game a bundle of ribs is removed, after which you need to make the graph bipartite again ... - Harry

1 answer 1

As an option, I can offer this solution on JS:

const playedMatches = [ [8, 3, 10, 1, 13, 11], [7, 6, 13, 0, 11, 5], [3, 8, 5, 7, 12, 9], [2, 0, 8, 14, 9, 10], [11, 5, 14, 13, 7, 6], [6, 4, 2, 9, 14, 1], [5, 1, 9, 10, 8, 4], [1, 9, 12, 2, 4, 14], [0, 2, 3, 15, 6, 13], [10, 7, 6, 5, 3, 2], [9, 11, 0, 6, 15, 3], [4, 10, 15, 12, 1, 0], [13, 14, 7, 11, 2, 15], [12, 15, 1, 4, 0, 8], [15, 12, 4, 2, 5, 7], [14, 13, 11, 8, 10, 12] ]; const maxTeams = playedMatches.length; // ВсСго ΠΊΠΎΠΌΠ°Π½Π΄ const teamNumbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; // Π’ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ массив - Π½ΠΎΠΌΠ΅Ρ€Π° ΠΊΠΎΠΌΠ°Π½Π΄ const aviableMatches = []; // Массив доступных сопСрников для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹ const pairsFlat = []; // Плоский массив Π½Π°ΠΉΠ΄Π΅Π½Π½Ρ‹Ρ… ΠΏΠ°Ρ€ const pairs = []; // Π˜Ρ‚ΠΎΠ³ΠΎΠ²Ρ‹Π΅ ΠΏΠ°Ρ€Ρ‹ // ЗаполняСм массив с доступными сопСрниками для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹ for(let i = 0; i < maxTeams; i++){ const aviableTeams = teamNumbers.filter(function(team){ return (team !== i) && (playedMatches[i].indexOf(team) === -1); }); aviableMatches.push(aviableTeams); } // РСкурсивная функция поиска ΠΏΠ°Ρ€ function findMatches(){ let teamIndex; if(pairsFlat.length >= maxTeams) return true; // Нашли всС ΠΏΠ°Ρ€Ρ‹ for(teamIndex = 0; teamIndex < maxTeams; teamIndex++){ if(pairsFlat.indexOf(teamIndex) === -1){ const aviableTeams = aviableMatches[teamIndex]; const teamPair = aviableTeams.find(function(team){ return pairsFlat.indexOf(team) === -1; }) if(teamPair === undefined) continue; // НСту доступной ΠΏΠ°Ρ€Ρ‹, ΠΈΡ‰Π΅ΠΌ дальшС pairsFlat.push(teamIndex); pairsFlat.push(teamPair); if(findMatches()){ // Π˜Ρ‰Π΅ΠΌ рСкурсивно return true; } else { // ΠŸΡ€ΠΈ Ρ‚Π°ΠΊΠΎΠΉ ΠΏΠ°Ρ€Π΅ Π½Π΅ нашли Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ. УдаляСм ΠΏΠ°Ρ€Ρƒ ΠΈ ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅ΠΌ поиск pairsFlat.pop(); pairsFlat.pop(); } } } return false; // НС нашли Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ } // ΠŸΡ€ΠΎΠ²Π΅Ρ€ΡΠ΅ΠΌ! if(findMatches()){ for(let i = 0; i < maxTeams; i += 2){ // Нашли! Π—Π°ΠΏΠΎΠ»Π½ΠΈΠΌ массив ΠΏΠ°Ρ€ pairs.push([pairsFlat[i], pairsFlat[i+1]]); } console.log('Found pairs of teams:'); console.dir(pairs) } else { console.log('No pairs!') }