Avatar billede dj.iceman Nybegynder
17. september 2008 - 15:45 Der er 6 kommentarer og
3 løsninger

Matematisk hjælp til Pubcrawl

Hej Eksperter,

- Jeg har 6 hold der skal på Pubcrawl.
- Hvert hold skal besøge 5 værtshuse.
- Holdene må ikke være et sted alene (dvs. der skal være 2 hold hver gang et sted besøges)
- Holdene skal møde ét hold én gang på turen. (dvs. et hold må ikke drikke med et andet hold 2 steder)

Er det noget I kan få til at gå op - for jeg kan ikke?

Mvh.
Dj Iceman
Avatar billede roenving Novice
17. september 2008 - 16:06 #1
Det tror jeg ikke der er nogen, der kan få til at gå op !-)

-- men jeg vil ikke forsværge det !o]
Avatar billede brianlindhardt Praktikant
17. september 2008 - 19:38 #2
Prøver lige med denne her:

pub1    hold1    hold2
pub1    hold3    hold4
pub1    hold5    hold6
       
pub2    hold1    hold3
pub2    hold2    hold5
pub2    hold4    hold6
       
pub3    hold1    hold4
pub3    hold2    hold6
pub3    hold3    hold5
       
pub4    hold1    hold5
pub4    hold2    hold4
pub4    hold3    hold6
       
pub5    hold1    hold6
pub5    hold2    hold3
pub5    hold4    hold5
Avatar billede bauerdata Nybegynder
17. september 2008 - 21:01 #3
værtshus        18:00  19:00  20:00  21:00  22:00  23:00
A              1,2    3,4                            5,6
B              4,6    2,5    1,3
C              3,5                    1,4    2,6
D                              2,4    3,6    1,5
E                      1,6    4,5                    2,3
Avatar billede pazau Nybegynder
17. september 2008 - 22:31 #4
Jeg siger det samme som Brianlindhardt. Det er logisk efter min mening.
Avatar billede bauerdata Nybegynder
18. september 2008 - 10:47 #5
Jeg siger det samme som Brianlindhardt. Det er logisk efter min mening.
og så fordeler jeg besøgene over tid.
1 hold kan jo ikke være på to eller flere værtshuse på en gang :-)
Avatar billede bauerdata Nybegynder
18. september 2008 - 20:57 #6
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
Dette python program laver en pubcrawl tabel efter
antal hold
antal hold på samme værtshus
antal værtshuse
"""

# variable til optimerings formål
Last_range = {}

def combinations( n, p ):
    """ k (n, p)
    n antal udfald
    p størrelse af delmængde
      n!
    --------
    p!(n-p)!
    """
    last = Last_range.get(( n, p ),False)
    if last:
        print "kilroy was here"
        return last
    current = range( 1, p + 1 )
    max = range( n - p + 1, n + 1 )
    resultat = []
    while current != max:
        res = []
        for number in current:
            res.append( number-1 )
        resultat.append( res )
        index = -1
        if current[ index ] != max[ index ]:
            current[ index ] = current[ index ] + 1
        else:
            for indices in range( -2, -p - 1, -1 ):
                if current[ indices ] != max[ indices ]:
                    current[ indices ] = current[ indices ] + 1
                    for other_indices in range( indices + 1, 0 ):
                        current[ other_indices ] = current[ indices ] + other_indices - indices
                    break
    res = []
    for number in max:
        res.append( number-1 )
    resultat.append( res )
    Last_range[(n, p)] = resultat
    return resultat   

if __name__ == "__main__":

    h = input("antal hold ialt: ")
    hp = input("antal hold pr pub: ")
    p = input("antal pub's: ")

    teamListe = combinations( h, hp)
    antal_team = len(teamListe)
    pub  = {}
    pubs = [ chr(P) for P in range(ord("A"),ord("A")+p) ]
    hold = {}
    holdene = [ x for x in range(h)]
    for x in range(h):
        hold[x] = { "tider":[], "pubs":[] }
    tider = [ x for x in range(max(antal_team, h)) ]
    for tid in tider:
        for P in pubs:
            pub[ P,tid]=[]
    Q = 0
    while teamListe != []:
        for tid in tider:
            for P in pubs:
                for team in teamListe[:]:

                    # check om hold er på pub på dette tidspunkt
                    x =[]
                    for z in team:
                        x.extend( hold[z]["tider"] )
                    if tid in x:
                        continue

                    # check om alle hold har være på denne pub
                    x = []
                    for z in team:
                        x.extend(z for z in hold[z]["pubs"] if P == z)
                    if len(x) > Q:
                        continue

                   
                    pub[ P, tid ] = team

                    for x in team:
                        hold[x]["tider"].append(tid)
                        hold[x]["pubs"].append(P)

                    del teamListe[ teamListe.index(team) ]
                    break
        Q += 1
    print "Pub/tid  18:00  19:00  20:00  21:00  22:00  23:00  00:00  01:00"
    for P in pubs:
        print "%(P)6s\t" % vars(),
        for tid in tider:
            team = pub[ P, tid ]
            if team == []:
                team = ""
            print "%(team)6s\t" % vars(),
        print "\n"
Avatar billede roenving Novice
19. september 2008 - 10:50 #7
Tjah, det var lge det program, jeg ikke gad at lave for at checke det !-)

Problemet er nemlig at det er asymmetrisk, så enten er der for få kombinationer eller for mange til at opfylde betingelserne, og jeg troede (åbenbart fejlagtigt !-) at der var for få ...

-- men der kan så laves flere mulige løsninger !o]
Avatar billede dj.iceman Nybegynder
05. november 2008 - 13:36 #8
Tak for alle jeres input.

Nogen der vil have point for forsøget.
Avatar billede bauerdata Nybegynder
05. november 2008 - 13:55 #9
Ja dak
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Computerworld tilbyder specialiserede kurser i database-management

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester