1

我正在尝试制作一个排序程序来对锦标赛比赛进行排序。

通过输入参赛者的姓名，我希望以特定的方式对这些进行排序。标准是没有人可以一个接一个地去看比赛，但每个人都必须面对对方。

例子：

1 - 2

1 - 3

1 - 4

1 - 5

2 - 3

2 - 4

2 - 5

3 - 4

3 - 5

4 - 5

这些都是比赛，必须以这样一种方式对它们进行排序/组织，以使尽可能接近的人不能在彼此之后进行比赛。

我知道一个数学事实是不可能解决的，所以每个人都不会接连进行两场比赛。但我希望“排序”尽可能接近。

从这个意义上说，它必须有点“聪明”，才能尽力而为。排序必须是动态的，所以如果我输入 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

“我知道一个数学事实是不可能解决的，所以每个人都不会连续参加两场比赛。”

这是一个没有参赛者连续两场比赛的情况：[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

我为你的配对提出了一个“随机”的解决方案，这样参赛者就无法预测他们每年的位置（假设活动是一年一度的）。

我的解决方案首先是对所有配对进行组合。randomizer 函数交换两个随机配对。

“count-back-to-backs”功能计算参赛者背靠背配对的次数。这是您判断配对数组的指标……或标准……。

主循环运行大量随机化循环并记住背靠背比赛最少的配置。您可以改变循环的数量。

您还可以添加其他函数来收集有关一组特定配对的指标，并根据这些指标保留/拒绝。

因此，该解决方案是：（1）生成随机配对，（2）根据一个或多个标准保留/拒绝配对数组，（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 回答