1

トーナメントの試合を並べ替える並べ替えプログラムを作成しようとしています。

出場者の名前を入力して、特定の方法で並べ替えたいと思います。基準は、誰もがお互いに試合に行くことができないということですが、誰もがお互いに向き合わなければなりません.

例：

1 - 2

1 - 3

1 - 4

1 - 5

2 - 3

2 - 4

2 - 5

3 - 4

3 - 5

4 - 5

これらはすべての試合であり、できるだけ近い人が次々に試合に出ないように並べ替え/整理する必要があります。

誰もが 2 回連続で試合に出ないように解決することは不可能であることは、数学的な事実としてわかっています。しかし、私は「ソート」をできるだけ近づけたいと思っています。

最善を尽くすという意味で、少し「賢く」なければなりません。並べ替えは動的でなければならないので、7 人の競技者を最大 30 人の競技者に入力すると、並べ替えは最善を尽くします。

今、私は競技者を正しい順序で配列リストに1〜17と言うか、1、2、1、3、1、4、2、3、2のような配列リストのすべての順列でそれらを持っています。 4、3、4。

数値を比較して、さまざまな方法で繰り返してみましたが、水中で死んでいます。私は助けを求めています、または私が向きを変えることができるように私を正しい方向に向けることができる人

これ：

1 - 2

1 - 3

1 - 4

1 - 5

2 - 3

2 - 4

2 - 5

3 - 4

3 - 5

4 - 5

これに：

5-4

1-2

3-4

1-5

2-3

1-4

2-5

3-1

5-4

3-5   <--here number 5 has to go 2 matches in a row
4

2 に答える 2

2

「数学的な事実として、誰もが次々と2試合を行わないように解決することは不可能であることを知っています。」

これは、2つの試合が連続して行われている競技者がいない場合です。[3-5、2-4、1-5、2-3、1-4、2-5、3-4、1-2、4 -5、1-3]

于 2013-01-26T16:41:53.410 に答える
1

参加者が毎年の配置を予測できないように、ペアリングに「ランダムな」ソリューションを提案します（イベントが毎年行われると仮定します）。

私の解決策は、すべての組み合わせを組み合わせることから始まります。ランダマイザー機能は、2つのランダムなペアを交換します。

「連続カウント」機能は、競技者が連続して戻るペアリングの数をカウントします。これは、ペアリングの配列を判断するためのメトリック...または基準...です。

メインループは多数のランダマイザーループを実行し、連続したコンテストが最も少ない構成を記憶しています。ループの数を変えることができます。

他の関数を追加して、特定のペアリングのセットに関するメトリックを収集し、それらのメトリックに基づいて保持/拒否することもできます。

したがって、この解決策は次のとおりです。（1）ランダムなペアリングを生成し、（2）1つ以上の基準に基づいてペアリングの配列を保持/拒否し、（3）コンピューターに判断のためにこれらのランダムなセットを多数生成させます。

出力は、次のように最後に連続した数のペアリングの配列です。

[3-5、2-4、1-5、2-3、1-4、2-5、3-4、1-2、4-5、1-3] 0

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Contest {

static Random rand = new Random();

static class Pairing {
    int contestantA;
    int contestantB;
    public Pairing(int a, int b) {
        contestantA = a;
        contestantB = b;
    }
    public String toString() {
        return ""+contestantA+" - "+contestantB;
    }
}

static int countBackToBacks(List<Pairing> pairs) {
    int backs = 0;
    for(int x=0;x<pairs.size()-1;++x) {
        Pairing a = pairs.get(x);
        Pairing b = pairs.get(x+1);
        if(a.contestantA==b.contestantA || a.contestantA==b.contestantB || 
                a.contestantB==b.contestantA || a.contestantB==b.contestantB)
        {
            ++backs;                
        }
    }           

    return backs;
}

static void randomize(List<Pairing> pairs) {
    int a = rand.nextInt(pairs.size());
    int b = rand.nextInt(pairs.size());
    Pairing pa = pairs.get(a);
    Pairing pb = pairs.get(b);
    pairs.set(a, pb);
    pairs.set(b, pa);       
}

public static void main(String [] args) {

    List<Pairing> pairs = new ArrayList<Pairing>();
    int numEntries = 5;//Integer.parseInt(args[0]);
    for(int x=0;x<numEntries-1;++x) {
        for(int y=x+1;y<numEntries;++y) {               
            Pairing p = new Pairing(x+1,y+1);
            pairs.add(p);               
        }
    }

    int bestVal = Integer.MAX_VALUE;
    String best = "";
    for(int x=0;x<1000000;++x) {
        randomize(pairs);
        int backs = countBackToBacks(pairs);
        if(backs<bestVal) {
            bestVal = backs;
            best = pairs.toString();
        }
    }

    System.out.println(best + bestVal);

}   

}
于 2013-01-26T16:53:10.627 に答える