generering af turneringsplan

Et eksempel på en turneringsplan kunne være:
4 hold
1-2, 3-4, 1-3, 2-4, 1-4, 2-3 = 6 kampe.
2 kampe pr. runde.

Skal du bare have oversat Birgers Perl-script til Java?

jeps that will do the trick

Skal du bare have 1 løsning eller alle løsninger ?

Her er et simpelt forslag, der giver dig alle løsninger. Udskift værdien
af n i toppen, hvis det ikke lige er 6 hold.

import java.util.*;

public class Turnering {
  static final int n = 6;  // antal hold i turneringen
  static final int nrrunde = (n%2==1)?(n-1)/2:n/2;
  static final int antalrunder = n-1;
  static List c = new ArrayList();
  static boolean used[];
  static boolean r[][]  = new boolean[antalrunder][n];

  private static class Kamp {
    public int hold1,hold2;
    public Kamp(int hold1,int hold2) {
      this.hold1=hold1;
      this.hold2=hold2;
    }
    public String toString() {
      return hold1+"+"+hold2;
    }
  }

  static void init() {
    for (int i=0;i<n;i++) {
      for (int j=0;j<n;j++) {
        if (i<j) {
          c.add(new Kamp(i,j));
        }
      }
    }
    used = new boolean[c.size()];
    for (int i=0;i<used.length;i++) {
      used[i]=false;
    }
    for (int i=0;i<antalrunder;i++) {
      for (int j=0;j<n;j++) {
        r[i][j]=false;
      }
    }
  }


  private static void tryit(int k,int runde,String losning) {
    if (k>=c.size()) {
      System.out.println("LØSNING: "+losning);
      return;
    }
    for (int i=0;i<c.size();i++) {
      if (!used[i]) {
        Kamp ci=(Kamp)c.get(i);
        if (r[runde][ci.hold1]==false && r[runde][ci.hold2]==false) {
          used[i]=true;
          r[runde][ci.hold1]=true;
          r[runde][ci.hold2]=true;
          if ((k+1)%nrrunde==0) {
            tryit(k+1,runde+1,losning+" "+ci+" | ");
          } else {
            tryit(k+1,runde,losning+" "+ci);
          }
          r[runde][ci.hold2]=false;
          r[runde][ci.hold1]=false;
          used[i]=false;
        }
      }
    }
  }

  public static void main(String[] args)     {
    init();
    tryit(0,0,"");
  }
}

Jeg har lavet en mere objekt orienteret løsning:

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

public class Plan {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int nr = ((n + 1) / 2) * 2 - 1;
        int nm = n / 2;
        Match[] mtch = new Match[nr * nm];
        genmatches(mtch, n);
        //for(int i = 0; i < mtch.length; i++) {
        //    System.out.println(mtch[i]);
        //}
        List rnd = new ArrayList();
        genrounds(rnd, new Round(nm), mtch, 0, 0, nm);
        //for(int i = 0; i < rnd.size(); i++) {
        //    System.out.println((Round)rnd.get(i));
        //}
        List plan = new ArrayList();
        boolean[] used = new boolean[rnd.size()];
        for(int i = 0; i < used.length; i++) {
            used[i] = false;
        }
        genplans(plan, new Plan(nr), rnd, used, 0, nr);
        //for(int i = 0; i < plan.size(); i++) {
        //    System.out.println((Plan)plan.get(i));
        //}
        System.out.println(plan.size());
    }
    private static void genplans(List plan, Plan wrk, List rnd, boolean[] used, int ix, int nr) {
        if(ix < nr) {
            for(int i = 0; i < used.length; i++) {
                if(!used[i]) {
                    used[i] = true;
                    wrk.setRound(ix, (Round)rnd.get(i));
                    genplans(plan, wrk, rnd, used, ix + 1, nr);       
                    used[i] = false;
                }
            }
        } else {
            if(wrk.isvalid()) {
                plan.add(wrk.clone());   
            }
        }
    }
    private static void genmatches(Match[] mtch, int n) {
        int ix = 0;
        for(int i = 0; i < n; i++) {
            for(int j = (i + 1); j < n; j++) {
                mtch[ix] = new Match(i + 1, j + 1);
                ix++;
            }
        }
    }
    private static void genrounds(List rnd, Round wrk, Match[] mtch, int ix, int pos, int nm) {
        if(pos < nm) {
            for(int i = ix; i < mtch.length; i++) {
                wrk.setMatch(pos, mtch[i]);
                genrounds(rnd, wrk, mtch, i + 1, pos + 1, nm);
            }
        } else {
            if(wrk.isValid()) {
                rnd.add(wrk.clone());
            }
        }
    }
    private static int fac(int v) {
        int res = 1;
        for(int i = 2; i <= v; i++) {
            res *= i;
        }
        return res;
    }
    private Round[] rounds;
    public Plan(int nr) {
        rounds = new Round[nr];
        for(int i = 0; i < rounds.length; i++) {
            rounds[i] = null;
        }
    }
    public void setRound(int ix, Round r) {
        rounds[ix] = r;
    }
    public Round getRound(int ix) {
        return rounds[ix];
    }
    public String toString() {
        StringBuffer sb = new StringBuffer("");
        for(int i = 0; i < rounds.length; i++) {
            sb.append(rounds[i]);
            sb.append("\n");
        }
        return sb.toString();
    }
    public boolean isvalid() {
        for(int i = 0; i < rounds.length; i++) {
            for(int j = (i + 1); j < rounds.length; j++) {
                if(rounds[i].overlap(rounds[j])) {
                    return false;
                }
            }
        }
        return true;
    }
    public Object clone() {
        Plan res = new Plan(rounds.length);
        res.rounds = (Round[])rounds.clone();
        return res;
    }
}

class Round {
    private Match[] matches;
    public Round(int nm) {
        matches = new Match[nm];
        for(int i = 0; i < matches.length; i++) {
            matches[i] = null;
        }
    }
    public void setMatch(int ix, Match m) {
        matches[ix] = m;
    }
    public Match getMatch(int ix) {
        return matches[ix];
    }
    public String toString() {
        StringBuffer sb = new StringBuffer("");
        for(int i = 0; i < matches.length; i++) {
            if(i > 0) {
                sb.append(" ");
            }
            sb.append(matches[i]);
        }
        return sb.toString();
    }
    public boolean isValid() {
        for(int i = 0; i < matches.length; i++) {
            for(int j = (i + 1); j < matches.length; j++) {
                if(matches[i].getTeam1() == matches[j].getTeam2() ||
                matches[i].getTeam1() == matches[j].getTeam1() ||
                matches[i].getTeam2() == matches[j].getTeam2() ||
                matches[i].getTeam2() == matches[j].getTeam1()) {
                    return false;
                }
            }
        }
        return true;
    }
    public boolean overlap(Round o) {
        for(int i = 0; i < matches.length; i++) {
            for(int j = 0; j < o.matches.length; j++) {
                if(matches[i].equals(o.matches[j])) {
                    return true;
                }
            }
        }
        return false;   
    }
    public Object clone() {
        Round res = new Round(matches.length);
        res.matches = (Match[])matches.clone();
        return res;
    }
}

class Match {
    private int team1;
    private int team2;
    public Match(int team1, int team2) {
        this.team1 = team1;
        this.team2 = team2;
    }
    public int getTeam1() {
        return team1;
    }
    public int getTeam2() {
        return team2;
    }
    public String toString() {
        return team1 + "-" + team2;
    }
    public boolean equals(Object o) {
        if (o instanceof Match) {
            if (team1 == ((Match) o).team1 && team2 == ((Match) o).team2) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
}

Men det ser altså ikke helt ud til at mit og Eriks program
finder samme resultat.

For 4 hold finder jeg 6 kombinationer men han finder 48 (og forskellen
er stor for 6 !).

Men det er formentlig fordi jeg betrager 1-2 og 2-1 som det samme.

Mange tak for kommentarene! Det er bare super de eventuelle rettelser som skal laves laver jeg selv, men mange tak for hjælpen til jer begge!

Hvis I vil have nogle point, så er jeg nødt til at få et svar fra jer i stedet for en kommentar.

Jeg ville godt have givet jer flere point, men det er desværre ikke muligt. Og siden at jeg nok kommer til at benytte arnes kode mest har jeg valgt at give pointen som følgende: arne 115 og erik 85.

(Erik, da jeg kørte din kode med 6 hold terminerede koden ikke ????)

svar

Eriks kode afslutter skam med 6 !

Efter at have fundet 5598720 løsninger !!

(jeg erstattede print med en counter)

Det er iøvrigt ikke 1-2 versus 2-1 der gør forskellen men
0+3 1+2 versus 1+2 0+3 (kampenes rækkefølge har fået signifikans).

Ok så var det bare min tålmodighed det var galt med. :-)

I det jeg skal bruge genereringen til skal jeg blot præsentere en mulig løsning ad gangen for en bruger, som så skal vælge hvilken turneringsplan vedkommen ønsker.

Jeg regner med at kunne lave det sådan at han får præsenteret den mulige løsning og hvis han ikke vil have den, så kører koden videre og finder den næste løsning. osv.
Jeg håber på at kunne nedsætte genereringstiden på denne måde.

Ja, der er ikke taget højde for disse symmetrier i min Q&D løsning.
Det ville ikke være så svært, men med Arnes løsning ikke umagen værd.

Bruger du Arnes løsning skal han selvfølgelig have pointene.

nej Erik der er også point til dig, da jeg vil benytte mig af begge kode blokke, da jeg vil søge inspiration i din kode også!

Men hvis ikke du vil have point er det op til dig!

er der en der kan jeg stakkels fæ?
hvad og hvordan skal jeg gøre for at få det til at virke?

håber på hjælp.

MVH
DKR