首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >排序/迭代/置换问题

排序/迭代/置换问题
EN

Stack Overflow用户
提问于 2013-01-26 15:51:17
回答 2查看 197关注 0票数 1

我正试着做一个排序程序来对比赛进行排序。

通过输入参赛者的名字,我希望以一种特定的方式对这些人进行排序。标准是没有人可以互相比赛,但每个人都必须面对对方。

示例:

代码语言:javascript
运行
复制
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。

我试着比较数字,用不同的方式迭代,但我死在水里。我在寻求帮助,或者是有人能指引我朝正确的方向走,这样我才能转向

这是:

代码语言:javascript
运行
复制
1 - 2

1 - 3

1 - 4

1 - 5

2 - 3

2 - 4

2 - 5

3 - 4

3 - 5

4 - 5

对此:

代码语言:javascript
运行
复制
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
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 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

代码语言:javascript
运行
复制
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);

}   

}
票数 1
EN

Stack Overflow用户

发布于 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。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/14538592

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档