我正试着做一个排序程序来对比赛进行排序。
通过输入参赛者的名字,我希望以一种特定的方式对这些人进行排序。标准是没有人可以互相比赛,但每个人都必须面对对方。
示例:
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,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
发布于 2013-01-26 16:53:10
我对你的配对提出了一个“随机”的解决方案,这样参赛者就无法预测他们的位置。(假设这个项目是每年举行的)。
我的解决方案从所有配对的组合开始。随机化函数交换两个随机配对。
“倒数-背对背”功能计算参赛者背靠背的配对次数。这是一个度量..。或者标准..。你可以根据对的排列来判断。
主循环运行大量随机化循环,并以最少的背靠背竞赛记住配置。您可以改变循环的数目。
您还可以添加其他函数来收集有关特定配对的度量,并根据这些指标保持/拒绝。
这个解决方案是:(1)生成随机配对;(2)根据一个或多个准则保留/拒绝配对数组;(3)让计算机生成大量这些随机集供您判断。
输出是对的数组,末端有背靠背的数目,如下所示
3- 5,2- 4,1- 5,2- 3,1- 4,2- 5,3- 4,1- 2,4- 5,1-3
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-26 16:41:53
“我知道一个数学事实,这是不可能解决的,这样每个人都不会互相比赛两场。”
在这个案例中,没有参赛者有两场背靠背的比赛:3- 5,2- 4,1- 5,2- 3,1- 4,2- 5,3- 4,1- 2,4- 5,1-3。
https://stackoverflow.com/questions/14538592
复制相似问题