我如何才能创建一个Java算法，使任意数量的播放器能够唯一地配对任意次数？

Question

我希望在Java中创建一个算法，它可以占用任意数量的“播放器”，并将它们分组，每一次都有指定的次数。然而，两对不可能是相同的。因此，如果用户提供了9名玩家(配音为0、1、2等)，并且每个玩家应该配对3次，这意味着该算法需要能够生成一个配对列表，其中每个玩家被配对3次。

因此，4名玩家可配对两次：{{0，1}，{2，3}，{0，2}，{1，3}。

很明显，在某些情况下，这是不可能的(比如4名玩家被唯一配对20次)，但我有输入限制来解决这个问题。

{0，1}和{1，0}是相等的对。数字的顺序并不重要，它们并不是唯一的。

输入的最佳方式是只给出两个数字(玩家数，每个播放器对数)，输出的更好方式是在一个二维整数数组中(每个玩家都被一个整数配音)，就像我给出的一个例子。

有没有人对怎么做有任何想法？伪代码，实际代码，任何想法都欢迎。谢谢!

Answer 1

我认为你的问题在代码中是有效和有趣的。

这就是为什么我对整件事进行编码的原因。

我的解决方案有一个缺点，或者说:问题。在某些情况下，一些球员之间可以有很多比赛，而其他球员几乎没有比赛。因此，最终，一些球员可能得不到适当的匹配。

在这种情况下，您需要一个数学技巧，或者一个回溯算法，它可以在部分解决方案上后退一步，并尝试其他组合(蛮力)。我的算法两者都没有，但它表示异常和有效性。

还可以检查代码中的注释。

package snippet;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

public class BadPairingStuff6 {



    static class Player {

        public final int                mID;
        private final BadPairingStuff6  mParentLogic;

        public int mMatches;

        public Player(final int pID, final BadPairingStuff6 pBadPairingStuff5) {
            mID = pID;
            mParentLogic = pBadPairingStuff5;
        }

        @Override public int hashCode() {
            return mID;
        }
        @Override public boolean equals(final Object obj) {
            if (this == obj) return true;
            if (obj == null) return false;
            if (getClass() != obj.getClass()) return false;
            final Player other = (Player) obj;
            if (mID != other.mID) return false;
            return true;
        }
        @Override public String toString() {
            return "Player[" + mID + "]";
        }

        public void incMatches() {
            ++mMatches;
        }
        public int getMatches() {
            return mMatches;
        }
        public boolean canPlayAnotherMatch() {
            return getMatches() < mParentLogic.mPairingsAllowed;
        }
    }

    static class Pairing {
        public final Player mPlayer1;
        public final Player mPlayer2;

        public Pairing(final Player pPlayer1, final Player pPlayer2) {
            if (pPlayer1.mID < pPlayer2.mID) {
                mPlayer1 = pPlayer1;
                mPlayer2 = pPlayer2;
            } else {
                mPlayer1 = pPlayer2;
                mPlayer2 = pPlayer1;
            }
        }

        @Override public String toString() {
            return mPlayer1 + "+" + mPlayer2;
        }

        @Override public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + mPlayer1.mID;
            result = prime * result + mPlayer2.mID;
            return result;
        }

        @Override public boolean equals(final Object obj) {
            if (this == obj) return true;
            if (obj == null) return false;
            if (getClass() != obj.getClass()) return false;
            final Pairing other = (Pairing) obj;
            if (mPlayer1 != other.mPlayer1) return false;
            if (mPlayer2 != other.mPlayer2) return false;
            return true;
        }
    }

    static class PartnerMap {
        private final HashMap<Player, ArrayList<Player>> mMap = new HashMap<>();

        public PartnerMap(final Iterable<Player> pPlayers) {
            for (final Player player : pPlayers) {
                final ArrayList<Player> partners = new ArrayList<>();
                for (final Player partner : pPlayers) {
                    if (player != partner) partners.add(partner);
                }
                mMap.put(player, partners);
            }
        }

        public Player getPartner(final Player pPlayer) {
            final ArrayList<Player> possiblePartners = mMap.get(pPlayer);
            if (possiblePartners.size() < 1) throw new NotEnoughPartnersException(pPlayer);
            return possiblePartners.get((int) (Math.random() * possiblePartners.size()));
        }
        public void removePartners(final Player pPlayer, final Player pPartner) {
            System.out.println("\t\tBadPairingStuff5.PartnerMap.removePartners(" + pPlayer + ", " + pPartner + ")");

            System.out.println("\t\t\tRemoving for " + pPlayer);
            System.out.println("\t\t\t\tBEFORE: " + toString(mMap.get(pPlayer)));
            mMap.get(pPlayer).remove(pPartner);
            System.out.println("\t\t\t\tAFTER: " + toString(mMap.get(pPlayer)));

            System.out.println("\t\t\tRemoving for " + pPartner);
            System.out.println("\t\t\t\tBEFORE: " + toString(mMap.get(pPartner)));
            mMap.get(pPartner).remove(pPlayer);
            System.out.println("\t\t\t\tAFTER: " + toString(mMap.get(pPartner)));
        }

        static String toString(final Iterable<Player> pPlayers) {
            final StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (final Player player : pPlayers) {
                sb.append(player.mID + " ");
            }
            sb.append("]");
            return sb.toString();
        }

        public void removePlayerCompletely(final Player pPlayer) {
            System.out.println("\t\t\tBadPairingStuff5.PartnerMap.removePlayerCompletely(" + pPlayer + ")");
            for (final ArrayList<Player> partnerMap : mMap.values()) {
                partnerMap.remove(pPlayer);
            }
            mMap.get(pPlayer).clear();
        }

        public void print() {
            System.out.println("Partner Map");
            for (final Entry<Player, ArrayList<Player>> e : mMap.entrySet()) {
                System.out.println("\t" + e.getKey());
                for (final Player v : e.getValue()) {
                    System.out.println("\t\t" + v);
                }
            }

        }
    }

    public static class NotEnoughPartnersException extends IllegalStateException {
        private static final long   serialVersionUID    = -7249807214069096317L;
        private final Player        mPlayer;
        public NotEnoughPartnersException(final Player pPlayer) {
            super("Not enough partners available for " + pPlayer + "!");
            mPlayer = pPlayer;
        }
        public Player getPlayer() {
            return mPlayer;
        }
    }

    static class PairingResult {
        public final ArrayList<Pairing>     mCreatedPairings;
        public final ArrayList<Exception>   mExceptions;
        public PairingResult(final ArrayList<Pairing> pCreatedPairings, final ArrayList<Exception> pExceptions) {
            mCreatedPairings = pCreatedPairings;
            mExceptions = pExceptions;
        }
        public boolean isValid() {
            return mExceptions.size() < 1;
        }
    }



    public static void main(final String[] args) {
        final int players = 10;
        final int pairingsAllowed = 4;
        final PairingResult result = new BadPairingStuff6(players, pairingsAllowed).createPairings();

        System.out.println("All pairings:");
        final HashMap<Long, Long> playCounter = new HashMap<>();
        for (final Pairing p : result.mCreatedPairings) {
            System.out.println("\t" + p);

            {
                final Long oldCount = playCounter.get(Long.valueOf(p.mPlayer1.mID));
                playCounter.put(Long.valueOf(p.mPlayer1.mID), Long.valueOf(oldCount == null ? 1 : (oldCount.longValue() + 1)));
            }
            {
                final Long oldCount = playCounter.get(Long.valueOf(p.mPlayer2.mID));
                playCounter.put(Long.valueOf(p.mPlayer2.mID), Long.valueOf(oldCount == null ? 1 : (oldCount.longValue() + 1)));
            }
        }

        System.out.println("Pairings per Player: ");
        for (final Entry<Long, Long> e : playCounter.entrySet()) {
            System.out.println("\t" + e.getKey() + " -> " + e.getValue());
        }

        System.out.println("Exceptions:");
        System.out.flush();
        sleep();
        for (final Exception e : result.mExceptions) {
            e.printStackTrace();
        }
        System.err.flush();
        sleep();

        System.out.println("Valid result: " + result.isValid());
        System.out.println("All done.");
    }



    /*
     * OBJECT
     */



    final int mPairingsAllowed;

    private final ArrayList<Player> mPlayers = new ArrayList<>();

    public BadPairingStuff6(final int pPlayersCount, final int pPairingsAllowed) {
        mPairingsAllowed = pPairingsAllowed;

        // create players
        for (int i = 0; i < pPlayersCount; i++) {
            mPlayers.add(new Player(i, this));
        }
    }



    public PairingResult createPairings() {
        final ArrayList<Pairing> createdPairings = new ArrayList<>();
        final ArrayList<Exception> exceptions = new ArrayList<>();
        final PartnerMap possiblePairings = new PartnerMap(mPlayers);

        final HashSet<Player> playersToHandle = new HashSet<>(mPlayers);
        while (!playersToHandle.isEmpty()) {

            final ArrayList<Player> removePlayersPerRound = new ArrayList<>();
            for (final Player player : playersToHandle) {
                if (!player.canPlayAnotherMatch()) {
                    possiblePairings.removePlayerCompletely(player);
                    removePlayersPerRound.add(player);
                    continue;
                }

                try {
                    System.out.println("Creating matches for " + player + " (" + player.getMatches() + ")");

                    final Player partner = possiblePairings.getPartner(player);
                    if (!partner.canPlayAnotherMatch()) continue;

                    final Pairing newPairing = new Pairing(player, partner);
                    if (createdPairings.contains(newPairing)) System.out.println("WARNING! Double hit for " + newPairing);
                    createdPairings.add(newPairing);
                    possiblePairings.removePartners(player, partner);
                    player.incMatches();
                    partner.incMatches();
                    System.out.println("\tMatched with " + partner);

                    if (!partner.canPlayAnotherMatch()) {
                        possiblePairings.removePlayerCompletely(partner);
                        removePlayersPerRound.add(partner);
                    }

                } catch (final NotEnoughPartnersException e) {
                    // the flushes and sleeps are only a cheap shot to keep System.out and System.err outputs in somewhat chronological order.
                    // this is for proof/debug/answer only, and should NOT be used in production!
                    System.out.flush();
                    sleep();

                    e.printStackTrace();
                    //              throw e; // if you want to abort early
                    removePlayersPerRound.add(e.getPlayer());
                    exceptions.add(e);

                    System.err.flush();
                    sleep();
                }
            }

            playersToHandle.removeAll(removePlayersPerRound);
        }

        possiblePairings.print();

        return new PairingResult(createdPairings, exceptions);
    }



    // the sleeps are only a cheap shot to keep System.out and System.err outputs in somewhat chronological order.
    // this is for proof/answer only, and should NOT be used in production
    static void sleep(final long pMilliSec) {
        try {
            Thread.sleep(pMilliSec);
        } catch (final InterruptedException e1) { /* */ }
    }
    static void sleep() {
        sleep(100);
    }



}

我使用了很多内部静态类。这只是为了演示的目的。如果您想实际使用这些类，请将它们放入单独的文件中(删除“静态类”，并在缺少的地方添加"public类“)。

还要注意，这种复杂性对于随机赋值是必需的。如果算法总是能产生相同的组合，那么大约是代码的十分之一。