两组组合的排列

Question

在 C# 中，我正在尝试编写一种算法来平衡两个给定每个球员的整数球员评分的球队。

数据集如下所示：

Player 1:  1330
Player 2:  1213
Player 3:  1391
Player 4:  1192
Player 5:  1261
Player 6:  1273
Player 7:  1178
Player 8:  1380
Player 8:  1200
Player 10: 1252

我想建立两组五名球员，其中两队的总评分差异尽可能小，以实现公平比赛。

现在要执行此操作，我想生成所有团队排列（每个排列是两队，每队 5 名球员）。但是所有 c# 排列示例都是为了组合诸如幂集之类的东西，而不是团队。

最有效的方法是什么？

Answer 1

您真的不需要生成所有排列。查看 0 到 2^10-1 之间的所有整数 i 并查看整数中有多少位设置为 1。每当这是 5 时，您就可以将 10 个团队分成两组，每组 5 个。

Answer 2

您可以使用 Linq 来解决您的问题

在这个例子中是两队两人

使用我对

的理解

.net fiddler run

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Player
    {
        public int PlayerId { get; set; }
        public int PlayerBit { get; set; }
        public int PlayerScore { get; set; }

        public override string ToString()
        {
            return string.Format("Player: {0} Score: {1}\n",PlayerId,PlayerScore);
        }
    }

    public class Program
    {
        public static void Main(string[] args)
        {
            const int maxDiff = 15;

            var players = new List<Player> { new Player() {PlayerId = 1, PlayerBit = 1<<0, PlayerScore = 1330},
                                             new Player() {PlayerId = 2, PlayerBit = 1<<1, PlayerScore = 1213},
                                             new Player() {PlayerId = 3, PlayerBit = 1<<2, PlayerScore = 1391},
                                             new Player() {PlayerId = 4, PlayerBit = 1<<3, PlayerScore = 1192},
                                             new Player() {PlayerId = 5, PlayerBit = 1<<4, PlayerScore = 1261},
                                             new Player() {PlayerId = 6, PlayerBit = 1<<5, PlayerScore = 1273},
                                             new Player() {PlayerId = 7, PlayerBit = 1<<6, PlayerScore = 1178},
                                             new Player() {PlayerId = 8, PlayerBit = 1<<7, PlayerScore = 1380},
                                             new Player() {PlayerId = 9, PlayerBit = 1<<8, PlayerScore = 1200},
                                             new Player() {PlayerId = 10, PlayerBit = 1<<9, PlayerScore = 1252}};

            var maxTeam = players.Max(x => x.PlayerBit);
            var maxBit = maxTeam * 2 - 1;

            var team = from t1 in Enumerable.Range(0, maxTeam) where getBitCount(t1) == 5 select t1;

            var match = team.Select(x => new { t1 = x, t2 = maxBit - x });

            foreach (var m in match)
            {
                var t1 = players.Where(x => (x.PlayerBit & m.t1) == x.PlayerBit);
                var t2 = players.Where(x => (x.PlayerBit & m.t2) == x.PlayerBit);
                var t1Score = t1.Sum(x => x.PlayerScore);
                var t2Score = t2.Sum(x => x.PlayerScore);

                if (Math.Abs(t1Score - t2Score) < maxDiff)
                {
                    Console.WriteLine("Team 1 total score {0} Team 2 total score {1}", t1Score, t2Score);
                    Console.WriteLine("{0} versu \n{1}\n\n", string.Join("", t1.Select(x => x.ToString()).ToArray()), string.Join("", t2.Select(x => x.ToString()).ToArray()));
                }
            }

            Console.Read();
        }

        private static int getBitCount(int bits)
        {
            bits = bits - ((bits >> 1) & 0x55555555);
            bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
            return ((bits + (bits >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
        }
    }
}

Answer 3

您想要 combinations，而不是排列。使用标准公式，我们知道有 252 种可能的组合，即 10 名玩家一次选 5 人。有一种非常简单的方法来生成组合，vib 在他的回答中提到了这一点，我在这里展开。

有 10 位玩家。如果您将球员视为一个 10 位数字，那么每个球员都对应于该数字中的一位。任何恰好设置了 5 位的 10 位数字都是有效的团队。所以 0101010101 是一个有效的团队，但 0011000100 不是一个有效的团队。

此外，任何有效的球队只有一个对手球队。也就是说，给定10个玩家和一个5人的团队，那么只有5个人才能select。所以 0101010101 队与 1010101010 队配对。

2^10 是 1024。所以我们只需要检查 1024 种可能的组合。实际上，我们只需要检查 512，因为我们知道任何号码高于 511 的球队都将拥有号码最高的球员（即最后一位已设置），而任何号码小于 512 的球队都不会拥有该球员。

所以想法是，对于每个小于 512 的数字：

如果数字中没有设置五位，则转到下一位
反转数字。这会给你对方的队伍
计算球队和对方球队的评分

执行此操作的简单 C# 代码：

private readonly int[] _playerRatings = new[] {1330, 1213, 1391, 1192, 1261, 1273, 1178, 1380, 1200, 1252};

private int CalculateTeamScore(int team)
{
    var score = 0;
    for (var i = 0; i < 10; ++i)
    {
        if ((team & 1) == 1)
        {
            score += _playerRatings[i];
        }
        team >>= 1;
    }
    return score;
}

private bool IsValidTeam(int team)
{
    // determine how many bits are set, and return true if the result is 5
    // This is the slow way, but it works.
    var count = 0;
    for (var i = 0; i < 10; ++i)
    {
        if ((team & 1) == 1)
        {
            ++count;
        }
        team >>= 1;
    }
    return (count == 5);
}

public void Test()
{
    // There are 10 players. You want 5-player teams.

    // Assign each player a bit position in a 10-bit number.
    // 2^10 is 1024.
    // Start counting at 0, and whenever you see a number that has 5 bits set,
    // you have a valid 5-player team.
    // If you invert the bits, you get the opposing team.

    // You only have to count up to 511 (2^9 - 1), because any team after that
    // will already have been found as the opposing team.

    for (var team = 0; team < 512; ++team)
    {
        if (IsValidTeam(team))
        {
            var opposingTeam = ~team;
            var teamScore = CalculateTeamScore(team);
            var opposingTeamScore = CalculateTeamScore(opposingTeam);
            var scoreDiff = Math.Abs(teamScore - opposingTeamScore);
            Console.WriteLine("{0}:{1} - {2}:{3} - Diff = {4}.", 
                team, teamScore, opposingTeam, opposingTeamScore, scoreDiff);
        }
    }
}

您必须提供从球队号码中提取球员号码的代码。从设置的位中输出位号是一件简单的事情。您可以修改分数计算代码来执行此操作。

请注意，我用来查找设置了多少位的代码根本不是最佳的。但它有效。如果您想要更快的方法，请查看 BitHacks page，它有许多不同的方法。

Answer 4

它基本上是 Partition Problem 的优化版本，它是 NP-hard

然而，由于 n = 10 非常小，您仍然可以找到所有排列并找到答案，对于更大的 n，您可以使用维基页面上显示的快速且易于实现的贪婪近似也。下面我只展示了一个示例代码，用蛮力 n = 10 的情况来找到答案。虽然它是用C++写的，但里面没有什么特别的，所有的运算符/数组在C#中都是一样的，你应该自己做翻译工作，复杂度是O(2^10 * 10)

#include<bits/stdc++.h>
using namespace std;

int a[10] = {1330,1213,1391,1192,1261,1273,1178,1380,1200,1252};
vector<int> team1, team2;
int ans = 1<<28, T1, T2;

int bits(int x){
 int cnt = 0; 
 while(x){ cnt += x&1; x>>=1;}
 return cnt;
}

int main(){
 for(int i=0; i< 1<<10; i++){
  if(bits(i) == 5){
   int t1 = 0, t2 = 0;
   for(int x = i,y=(1<<10)-1-i, j=0; x; x>>=1,y>>=1, j++) {
    t1 += (x&1)*a[j];
    t2 += (y&1)*a[j];
   }
   if(ans > abs(t1-t2)){ ans = abs(t1-t2); T1 = i; T2 = (1<<10)-1-i;}
  }
 }
 for(int i=1; T1 || T2; T1>>=1, T2>>=1, i++) {
  if(T1&1) team1.push_back(i);
  if(T2&1) team2.push_back(i);
 }
 printf("Team 1: ");
 for(int i=0; i<5;i++) printf("%d ", team1[i]); 
 puts("");
 printf("Team 2: ");
 for(int i=0; i<5;i++) printf("%d ", team2[i]); 
 puts("");
 printf("Difference: %d\n", ans);
 return 0;
}

两组组合的排列

Permutations of combinations of two groups

c#

algorithm

permutation