Получение всех допустимых комбинаций в javascript

Question

Я думаю, что мое название неверно для этой проблемы, но поскольку английский не является моим родным языком, я не мог найти лучшего способа назвать свою проблему.

Так что у меня есть это разные игроки с несколькими свойствами:

Player_one.name = "A"; 
Player_two.name = "B"; 
Player_three.name = "C"; 
Player_four.name = "D"; 

Игроки также имеют свойство:

Player_one.canPlay = ["B","D"]; 
Player_two.canPlay = ["A","D"]; 
Player_three.canPlay = ["A","C"]; 
Player_four.canPlay = ["B","D"] 
//note that this is example and may not be accurate right now 

недвижимости canPlay показывает, с кем игрок может играть.

Теперь игроки также имеют свойство «placeInTable», который показывает свое текущее место, например, положение один, два или три и т.д.

Что я хотел бы добиться того, чтобы проверить, можно ли сделать комбинации из каждый массив canPlay, чтобы каждый игрок мог играть с другим в текущем раунде. В случае, если есть несколько возможных вариантов, например, если игрок может играть с игроком два и три, а игры все равно могут быть сыграны со всеми, тогда игрок с более высоким «placeInTable» будет выбран для противника.

Чтобы выразить свою мысль, я пытаюсь создать таблицу системных журналов, которая правильно управляет следующими играми. Алгоритм должен проверять каждый canPlay для каждого игрока и создавать комбинации, которые приведут к тому, что каждый игрок сможет играть с другим, и если доступно несколько вариантов игр, он сначала выберет лучшего противника в соответствии с «placeInTable».

Что я сделал до сих пор, так это то, что у меня есть алгоритм, который начнет проверять таблицу с самого начала, если игрок не может играть с другим, будет выбран нижний. Хотя мой текущий алгоритм неисправен, поскольку, если игроки с длиной-1 и длиной-2 играли друг с другом, алгоритм не знает, что делать. Поэтому для этого я добавлю два верхних игрока, из которых сбой алгоритма, в настоящее время длина-1 и длина-2, поэтому будут добавлены игроки длиной-3 и длиной-4, а проверка canPlay будет запущена.

Надеюсь, что мое описание этой проблемы не слишком вводило в заблуждение и могло быть понято и действительно великолепием для того, кто может помочь.

Если возникнут какие-либо вопросы, я с удовольствием расскажу подробнее об этой проблеме.

Редактировать Нет. 1:

Я забыл добавить, что в швейцарской системе два игрока не могут играть друг с другом, как только они уже играли друг с другом. Вот почему у меня есть canPlay, и в первом раунде длина массива canPlay может быть длиннее, а в пятом или шестом она может быть очень маленькой.

О ответе, который предположил, что если A может играть с B и B, может играть с C, тогда A может играть с C, тогда нет, это неверная идея. Лучшее понимание может быть сделано с примером.

Допустит, есть возможные комбинации, как:

A vs B 
C vs D 
//and 
A vs D 
B vs C 

Теперь таким образом, каждый игрок может играть с любым другим игроком, но есть два варианта. Теперь, если в таблице указано, что у игрока А есть место 1, игрок B пятно 2, игрок C пятно 3 и игрок D пятно 4, тогда он должен выбрать первый вариант, потому что игроки в более высоком месте в таблице должны быть размещены вместе.

Может быть, конечно, третий вариант, игрок A против игрока C & & игрок B против игрока D, но я оставил его прямо сейчас. Если бы был третий вариант, то все же первый был бы выбран, поскольку он помещает более высокие точки вместе.

Редактировать Нет. 2:

function reastaArray(){ 
var newArr = jQuery.extend(true,[],playerLst); //copy of original players 
var original = jQuery.extend(true,[],playerLst); 
var inPlay = []; //siia hakkame lisama 
var firstRound = true; 
var visitedCount = 1; 
var i = 0; 
var count = 0; 
while (newArr.length != 0){ 
    //this goes on until there are players left in playerList 
    count = i; 
    hereiam = false; 
    if (inPlay.length % 2 == 0){ //if the players in play are even amount then the first one gets pushed without a check 
     inPlay.push(newArr[i]); 
     newArr.splice(i,1); 
    } 
    else{ //now we need to search for opponent 
     var lastEl = inPlay[inPlay.length-1]; 
     var element = newArr[i]; 
     var played = hasPlayed(element,lastEl); //true/false, can we play with last element in inPlay, if it's true then while cycle begins 
     while (played == true){ 
      count += 1; 
      if (count == newArr.length){ //if we've reached at the end of the newArr and still haven't found an opponent 
       //take in last played games into new array 
       takeLast(inPlay,newArr); 
       for (var y = 0; y<visitedCount;y++){ 
        takeLast(inPlay,newArr); 
        takeLast(inPlay,newArr); 
       } 
       canWePlayNow(newArr); 
       //populize canPlay-s. 

       //IDEA FROM STACK 

       var combinations = findCombinations(newArr); 
       console.log("possible combinations"); 
       combinations.forEach(function(comb) { 
       console.log(comb); 
       }); 
       console.log(findBest(combinations,newArr)); 
       visitedCount += 1; 


      } 
      else{ 
       element = newArr[count]; 
       played = hasPlayed(element,lastEl); 
      } 
     } 
     if (hereiam == false){ 
     inPlay.push(element); 
     newArr.splice(count,1); 
     } 


    } 
} 
return inPlay; 
} 

function canWePlayNow(newArr){ 
for (var i = 0; i<newArr.length;i++){ 
    var player = newArr[i]; 
    player.canPlay = []; 
    var hasPlayed = player.playedNames; 
    for (var j = i+1; j<newArr.length;j++){ 
     playerFromPlayed = newArr[j]; 
     var inArr = isInArray(hasPlayed,playerFromPlayed.name); 
     if (inArr == false){ 
      player.canPlay.push(playerFromPlayed.name); 
     } 
    } 
} 
} 

Сочетания массив может работать лучше, прямо сейчас, как я тестировал делает:

Как видно из изображения, первый раунд рассчитывается большим, теперь второй раунд значение вводится и третий раунд расчета беспорядок вверх: он мог бы собрать 5vs6; 1vs4 и 2vs3, но этот алгоритм, который вы предоставили, уже довольно близок, не могли бы вы еще раз взглянуть на то, что не так?

Редактировать нет 3:

При дальнейшем осмотре не кажется, что он все еще делает что-то не так. Как видно из изображения ниже, правильный результат должен быть 1 & 2 и 5 против 3, хотя следующие показанные игры: 1vs5 & 3vs2, что не должно быть результатом.

Вход для массива был игроком, у которого уже был один раунд свободного или как в таблице «V». Алгоритм, который вы опубликовали, не изменился.

Как видно из консоли, другой вариант, который я указал выше, находится в комбинациях, но не выбран. Есть идеи?

Редактировать нет 4:

Добавлен новый образ!

function findBest(combinations, players) { 
    if(combinations.length === 0) throw new Error(); 
    var koht = {}; 
    function score(comb) { 
    return comb.reduce(function(score, pair) { 
     //console.log("New calc:"); 
     //console.log(score+koht[pair[0]]*koht[pair[1]]); 
     return score + koht[pair[0]] * koht[pair[1]]; 
    }, 0); 
    }; 
    players.forEach(function(p) { 
    koht[p.name] = p.koht; 
    }); 
    var best = combinations[0]; 
    combinations.slice(1).forEach(function(comb) { 
    console.log(score(comb) + " = combs & best = "+score(best)); 
    console.log("Checked combs: "); 
    console.log(comb); 
    if(score(comb) > score(best)) { 
     best = comb; 
    } 
    }); 
    console.log("Returned array: (best)"); 
    console.log(best); 
    return best; 
} 

Добавлено Вход в KOHT

Answer 1

Вот код, который отображает все возможные комбинации, в которой каждый игрок получает играть. Затем он пытается найти лучший, предпочитая пары игроков в высоких точках.

function findCombinations(players) { 
    var combinations = []; 

    function removePlayer(a, name) { 
    for(var i = 0; i < a.length; i++) { 
     if(a[i].name === name) return a.slice(0, i).concat(a.slice(i+1)); 
    } 
    return a; 
    } 

    function find(players, comb) { 
    if(players.length === 0) { 
     combinations.push(comb); 
     return; 
    }; 
    var player = players[0]; 
    player.canPlay.forEach(function(other) { 
     var newPlayers = removePlayer(players, other); 
     if(newPlayers !== players && other !== player.name) { 
     find(newPlayers.slice(1), comb.concat([[player.name, other]])); 
     } 
    }); 
    } 

    find(players, []); 
    return combinations; 
} 

function findBest(combinations, players) { 
    if(combinations.length === 0) throw new Error(); 
    var placeInTable = {}; 
    function score(comb) { 
    return comb.reduce(function(score, pair) { 
     return score + placeInTable[pair[0]] * placeInTable[pair[1]]; 
    }, 0); 
    }; 
    players.forEach(function(p) { 
    placeInTable[p.name] = p.placeInTable; 
    }); 
    var best = combinations[0]; 
    combinations.slice(1).forEach(function(comb) { 
    if(score(comb) > score(best)) best = comb; 
    }); 
    return best; 
} 

var p1 = {name: "A", canPlay: ["B", "D", "C"], placeInTable: 1}, 
    p2 = {name: "B", canPlay: ["A", "D"], placeInTable: 2}, 
    p3 = {name: "C", canPlay: ["A", "C", "D"], placeInTable: 3}, 
    p4 = {name: "D", canPlay: ["B", "D", "C"], placeInTable: 4}; 

var players = [p1, p2, p3, p4], 
    combinations = findCombinations(players); 

console.log("possible combinations"); 
combinations.forEach(function(comb) { 
    console.log(comb); 
}); 

console.log("\nbest:"); 
console.log(findBest(combinations, players));