在javascript中获取所有有效组合

I think my title is not correct for this issue but since english is not my mother tongue i couldn't figure out a better way to title my problem.

我认为我的标题对于这个问题是不正确的,但由于英语不是我的母语,我无法想出一个更好的方法来标题我的问题。

So what i have is different Players with a few properties:

所以我拥有的是具有一些属性的不同玩家:

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

Players also have property:

玩家也有财产:

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

Property canPlay shows with who player can play with.

属性canPlay显示玩家可以玩的人。

Now players also have property called "placeInTable" which shows their current spot, for example position one, two or three etc.

现在玩家也有名为“placeInTable”的属性,显示他们当前的位置,例如位置一,二或三等。

What i would like to achieve is to check whether it is possible to make combinations from every canPlay array so that every player is able to play with another in the current round. In case there are several possible options, for example, if player one can play with player two and three and games still could be played with everyone then the player with higher "placeInTable" will be selected for an opponent.

我想要实现的是检查是否可以从每个canPlay阵列组合,以便每个玩家能够在当前回合中与另一个玩家一起玩。如果有几种可能的选择,例如,如果玩家1可以玩玩家二和三并且游戏仍然可以与所有人一起玩,那么具有较高“placeInTable”的玩家将被选择用于对手。

To sum my idea up is that i'm trying to create a swiss system table which manages the next games properly. Algorithm should check every canPlay for each player and create combinations which would result in a way that every player is able to play with another and if several options for games are available it will choose the best opponent first according to "placeInTable".

总之,我的想法是,我正在尝试创建一个瑞士系统表,正确管理下一个游戏。算法应该检查每个玩家的每个canPlay并创建组合,这将导致每个玩家能够与另一个玩家一起玩,并且如果有几个游戏选项可用,它将根据“placeInTable”首先选择最佳对手。

What i've done so far is that i have an algorithm which will start checking the table from the beginning, if player can't play with another the lower one will be selected. Although my current algorithm is faulty since if the length-1 and length-2 players have played with each other the algorithm does not know what to do. So for that i'll add two upper players from which the algorithm crashes, currently length-1 and length-2 so the players length-3 and length-4 will be added and canPlay check will be ran.

到目前为止我所做的是我有一个算法将从头开始检查表,如果玩家不能玩另一个,则会选择较低的一个。虽然我目前的算法是错误的,因为如果长度为1和长度为2的玩家互相玩耍,则该算法不知道该怎么做。所以为此,我将添加两个算法崩溃的高级玩家,当前长度为1,长度为2,因此将添加玩家长度为3和长度为4,并且将运行canPlay检查。

I hope my description for this problem was not too misleading and could be understood and really big kudos to someone who is able to help.

我希望我对这个问题的描述不会太误导,可以被理解,对能够提供帮助的人来说真是太棒了。

If any questions i'd be happy to describe more about this issue.

如有任何问题,我很乐意详细描述这个问题。

Edit no. 1:

编辑号1:

I forgot to add that in Swiss System two players can't play with each other once they've already played with each other. That's why i have canPlay and in first round the canPlay array length may be longer and in fifth or sixth it may be really small.

我忘了补充一点,在瑞士体系中,一旦他们已经相互比赛,两名球员就无法互相比赛。这就是为什么我有canPlay并且在第一轮中canPlay阵列长度可能更长,而在第五或第六轮中它可能非常小。

About answer which suggested that if A can play with B and B can play with C then A can play with C then no, it's not correct idea. Better understanding could be made with an example.

关于答案表明,如果A可以和B一起玩,B可以和C一起玩,那么A可以玩C然后不行,这是不正确的想法。通过一个例子可以更好地理解。

Let's say there are possible combinations like:

让我们说有可能的组合,如:

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

Now in such manner every player can play with every other player but there's two options. Now if the table goes that player A has spot 1, player B spot 2, player C spot 3 and player D spot 4 then it should choose the first option because players in higher place in table should be placed together.

现在以这种方式,每个玩家都可以与其他玩家一起玩,但有两种选择。现在如果桌子上的那个玩家A有现货1,玩家B现货2,玩家C现货3和玩家D现货4那么它应该选择第一个选项,因为表中较高位置的玩家应该放在一起。

There could be of course a third option, player A vs player C && player B vs player D but i left it out right now. IF there would be third option then still the first one would be selected since it places the higher spots together.

当然可以有第三个选项,玩家A对玩家C &&玩家B对玩家D但是我现在就把它留下了。如果有第三个选项,那么仍然会选择第一个选项,因为它将较高的位置放在一起。

Edit no. 2:

编辑号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);
        }
    }
}
}

The combination array could work better, right now as i tested it does:

组合阵列可以更好地工作,就像我测试它一样:

As seen from image, first round is calculated great, now second round values are entered and third round calculation messes up: It could put together 5vs6 ; 1vs4 and 2vs3, but this algorithm you provided is pretty close already, could you give a further look to check out what's wrong?

从图像看,第一轮计算得很好,现在输入第二轮值,第三轮计算混乱:它可以组合5vs6; 1vs4和2vs3,但你提供的这个算法已经非常接近了,你能进一步研究一下是什么问题吗?

Edit no 3:

编辑3:

With further inspection it seems like it's still doing something wrong. As seen from image below the correct result should be 1 & 2 and 5 vs 3 although next games shown are 1vs5 & 3vs2, which shouldn't be result.

经过进一步的检查,它似乎还在做错事。从下面的图像可以看出,正确的结果应该是1&2和5 vs 3,尽管下面显示的游戏是1vs5和3vs2,这不应该是结果。

The input for the array were Players who've had already one round of free or as in table "V". The algorithm you posted is unchanged.

阵列的输入是已经有一轮免费或表“V”的玩家。您发布的算法未更改。

As seen from console, the other option which i pointed out above is in combinations but it's not selected. Any ideas?

从控制台看,我上面指出的另一个选项是组合,但它没有被选中。有任何想法吗?

Edit no 4:

编辑4:

Added new image!

添加了新图片!

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;
}

Added Log to KOHT

添加了日志到KOHT

1 个解决方案

#1

Here is some code that displays all possible combinations in which each player gets to play. It then tries to find the best one by preferring pairings of players in high spots.

以下是一些代码,显示每个玩家可以玩的所有可能组合。然后它试图找到最好的一个,更喜欢高点的玩家配对。

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));