两两轮流随机不放回匹配算法

最近在做1v1的pk竞技。玩法是有n个人进入一场比赛，这n个人互相之间分别对战，每两人之间只进行一次比赛，最后根据玩家的胜场和所需时间来排名，相同胜利场次，用时较少者胜。

如果8个人进行比赛，两两随机不放回匹配，即每名选手都会和另外的7个人分别对战一次。如果只有7个人比赛，那么每名选手都会和另外的6个人分别对战一次，但是每一轮比赛会有人轮空休息。

我是这样解决这个问题的，比较简单。

首先对整个数组进行随机排序。然后按照下图来完成匹配过程。

单数情况

%% 随机排序数组
get_rand_list([], Acc) -> Acc;
get_rand_list(List, Acc) -> 
    Len = length(List),
    Index = util:rand(1, Len),
    Item = lists:nth(Index, List),
    List1 = [ItemP || ItemP <- List, ItemP =/= Item],
    get_rand_list(List1, [Item | Acc]).

%% 每轮匹配过程
match_kvs([], Acc, Match) ->
    {Acc, Match};
match_kvs(List, Acc, Match) when length(List) =:= 1 ->
    [PlayerId] = List,
    {[{fail, PlayerId} | Acc], Match};
match_kvs([PlayerId | T], Acc, Match) ->
    case lists:keyfind(PlayerId, 1, Match) of   
        {_, ListIds} ->
            KvsPList = [Item || Item <- T, lists:member(Item, ListIds) =:= false],
            case KvsPList of
                [] -> match_kvs(T, [{fail, PlayerId} | Acc], Match);
                _ ->
                    [PlayerId3 | _] = KvsPList,
                    P3List = get_match_list(PlayerId3, Match),
                    Match1 = lists:keydelete(PlayerId3, 1, Match) ++ [{PlayerId3, [PlayerId | P3List]}],
                    Match2 = lists:keydelete(PlayerId, 1, Match1) ++ [{PlayerId, [PlayerId3 | ListIds]}],
                    T3 = [ItemPlayerId || ItemPlayerId <- T, ItemPlayerId =/= PlayerId3],
                    match_kvs(T3, [{ok, PlayerId, PlayerId3} | Acc], Match2)
            end;
        _ ->
            [PlayerId2 | T2] = T,
            P2List = get_match_list(PlayerId2),
            Match1 = lists:keydelete(PlayerId2, 1, Match) ++ [{PlayerId2, [PlayerId | P2List]}],
            match_kvs(T2, [{ok, PlayerId, PlayerId2} | Acc], Match1 ++ [{PlayerId, [PlayerId2]}])
    end.

%% 获取历史匹配记录
get_match_list(PlayerId, Match) ->
    case lists:keyfind(PlayerId, 1, Match) of
        {_, List} -> List;
        _ -> []
    end.

%% 匹配
match(List, Match) ->
    List1 = get_rand_list(List, []),
    match_kvs(List1, [], Match). 

嗯，这样就使用Erlang实现了两两随机不放回匹配算法。是不是很简单？

我们在匹配中还有各种筛选条件的，比如：区间匹配 、全局匹配，按 等级 、 战斗力及各种条件按优先级筛选匹配，这里不做讨论，感兴趣欢迎和我讨论。