首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >在列表中查找所有可能的配对的最快方法是什么?

在列表中查找所有可能的配对的最快方法是什么?
EN

Stack Overflow用户
提问于 2011-02-19 02:28:36
回答 4查看 3.3K关注 0票数 3

基本上我有一个玩家列表,我想把它们配对,这样每个玩家就可以和每个人玩一次。查找此数据的最快方法是什么?

EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2011-02-19 02:34:52

假设玩家不会在列表中出现两次,那么双for循环会非常快:

代码语言:javascript
运行
复制
for (int i=0, i <= playerList.Count - 2, i++)
    for (int j=i+1, j <= playerList.Count - 1, j++)
        //add a new pairing of player i and j
票数 5
EN

Stack Overflow用户

发布于 2011-02-19 02:31:22

这种锦标赛日程安排通常被称为round-robin。在维基百科中,也有一个可能的scheduling algorithm的例子。

票数 2
EN

Stack Overflow用户

发布于 2011-02-19 03:02:32

我将两个实现放在一起进行性能比较。非常简单的版本1比版本2慢大约50%,这并不是说没有更快的版本存在。

代码语言:javascript
运行
复制
class Program
{
    class Player
    {
        public string Name { get; set; }

        public Player(string name)
        {
            Name = name;
        }
    }

    class Match
    {
        public readonly Player Player1;
        public readonly Player Player2;

        public Match(Player player1, Player player2)
        {
            Player1 = player1;
            Player2 = player2;
        }

        public override string ToString()
        {
            return string.Format("{0} vs. {1}", Player1.Name, Player2.Name);
        }
    }

    static readonly List<Player> _players = new List<Player>()
    {
        new Player("John"),
        new Player("Lisa"),
        new Player("Matt"),
        new Player("Dan"),
        new Player("Steve"),
        new Player("Sarah"),
        new Player("Tim")
    };

    static void Main(string[] args)
    {
        const int count = 1000000;

        {
            var v1 = V1();
            var sw = Stopwatch.StartNew();
            for (int i = 0; i < count; i++)
            {
                v1 = V1();
            }
            Console.WriteLine(v1);
            Console.WriteLine(sw.Elapsed);
        }

        {
            var v2 = V2();
            var sw = Stopwatch.StartNew();
            for (int i = 0; i < count; i++)
            {
                v2 = V2();
            }
            Console.WriteLine(v2);
            Console.WriteLine(sw.Elapsed);
        }


        Console.ReadLine();
    }

    static List<Match> V1()
    {
        var challengers = new List<Player>(_players);
        var matches = new List<Match>();
        foreach (var player in _players)
        {
            challengers.Remove(player);
            foreach (var challenger in challengers)
            {
                matches.Add(new Match(player, challenger));
            }
        }
        return matches;
    }

    static List<Match> V2()
    {
        var matches = new List<Match>();
        for (int i = 0; i < _players.Count; i++)
        {
            for (int j = i + 1; j < _players.Count; j++)
            {
                matches.Add(new Match(_players[i], _players[j]));
            }
        }
        return matches;
    }
}
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5045137

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档