Spre tal i lister

[nercix]

Fant ikkje på bedre emne tittel

 

Problemet er i alle fall slik:

 

Har ei liste som kan sjå slik ut:

[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 8),
(2, 9), (2, 3), (2, 4), (2, 5), (3, 6), (3, 7), (3, 8),
(3, 9), (4, 5), (4, 6), (4, 7), (4, 8), (5, 9), (5, 6),
(5, 7), (6, 8), (6, 9), (7, 8), (7, 9), (8, 9)]

Og den skal «sorterast» slik at det blir størst mulig avstand frå like tal. Dvs (1,2) og (1,3) kan ikkje stå etter kvarandre. Om talet er det første eller siste i tuplen (norsk ord?) spelar ingen rolle, dei skal også spreiiast.

 

Eksempel:

[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]

Blir til:

[(1, 2), (3, 4), (5, 6), (1, 4), (2, 5), (3, 6), (1, 5), (2, 6), (3, 5), (1, 6), (2, 4), (1, 3), (4, 5), (2, 3), (4, 6)] gjort for hand...

 

Tips til ein god måte å ordne dette på?

[zeitgeist]

Skulle gjerne ha forsøkt, men jeg forstår ikke hva du er ute etter.

[steingrim]

Skulle gjerne ha forsøkt, men jeg forstår ikke hva du er ute etter.

Jeg forsto heller ikke helt... Men hvis jeg hadde forstått problemet så kunne jeg antagelig ha laget en compare-funksjon og gitt den som cmp-argumentet til list.sort():

 

>>> help([].sort)
Help on built-in function sort:

sort(...)
   L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
   cmp(x, y) -> -1, 0, 1

 

Altså laget en funksjon som sammenlignet to tupler og returnerte -1, 0 eller 1 ettersom om x er mindre, lik eller større enn y.

 

Men skulle jeg laget det måtte jeg ha forstått problemet Og jeg studerte listene uten å helt se mønsteret...

[nercix]

Ok, prøver å forklare problemet igjen.

 

Rekna med at eg ikkje klarte å forklare dette på første forsøk

 

Har ei liste som innehelder tupler, kvar tuppel innheld to tal.

 

 

La oss tenke at ein tuppel har tala a og b.

Eg har då eit ønske å sortere denne listen på en slik måte at tupler med like tal (a=b, a=a eller b=b) får størst mulig avstand frå kvarandre.

 

Så

(a,b) skal lengst mulig vekk fra (a, x), (x, a), (b, x), (x, b).

 

Med lengst mulig vekk meinar eg plassering i lista. Got it?

 

EDIT: Dersom det fortsatt er uklart, berre sei frå, så skal eg prøve å forklare igjen.

Altså vil ikkje sortere lista etter nummerisk.

Endret 17. oktober 2007 av nercix

[ekorniminator]

Kan du komme med noen konkrete regler for hvordan du har tenkt å sortere, dette virker litt difust.. Dersom en tupler er beskrevet som (x,y), og man har tuplene a og b, vil forskjellen mellom disse to være abs(ax,bx) + abs(ay,by) hvor abs er absoluttverdien? Og om vi gir plasseringen av a og b en rangering P vil da P = (abs(ax,bx) + abs(ay,by) ) * (antall elementer mellom a og b) / (antall elementer ), altså en linært økende rangering ved avstanden?

 

Ps. Må også si at jeg lurer på hvorfor du vil dette =P

Endret 19. oktober 2007 av ekorniminator

[Dustwave]

sikkert lekser...

Endret 19. oktober 2007 av Dustwave

[ekorniminator]

Kan virke sånn ja, men samtidig er oppgaven veldig rart formulert for å være en skoleoppgave.. Med mindre nercix har latt være å av oppgaven regelrett da.

 

Uansett kan det være en interessant problemstilling om jeg bare får grep på hva det er du egentlig vil, har skjønt at du skal spre tallene mest mulig, men som jeg sa i posten 2 hakk opp, jeg må vite hvordan prioriteringen er osv..

 

*Er visst dagen for skrivefeil i dag =P

Endret 19. oktober 2007 av ekorniminator

[toddy23]

Tror han mener å spre tallene best mulig utover listen,

Ikke tenk på tallene som tall, men som symboler som skal stå lengs mulig fra hverandre. Tror spredningen går i å få flest mulig andre symboler mellom like symboler.

 

Det jeg ikke forstår er hvorfor de skal i tupler.

[ekorniminator]

1. Skal tuplene sammenlignes som enheter, eller er det bare slik at alle tall skal lengst mulig vekk fra like tall, men at tallene henger sammen i par?

 

2. Skal den totale avstanden mellom like tall i listen være størst mulig eller bare den minste avstanden mellom to like tall størst mulig?

[nercix]

1. Skal tuplene sammenlignes som enheter, eller er det bare slik at alle tall skal lengst mulig vekk fra like tall, men at tallene henger sammen i par?

 

2. Skal den totale avstanden mellom like tall i listen være størst mulig eller bare den minste avstanden mellom to like tall størst mulig?

1. Tallene henger sammen i pal, og alle tala skal lengst mulig frå kvarandre.

2. Forsto ikkje heilt.. Kanskje forklaringa under hjelper deg til å finne ut sjølv.

 

Mange lurer på kvifor eg vil ha det slik. Det er ingen skuleoppgåve;

(x, y)

Person x skal kjempe mot person y. Vil at x og y skal få størst mogleg pause før de må kjempe mot ein annan person (posisjonen i lista+1 = kampnr).

 

Trenger ikkje å vere noko ytterligare prioritering utover det

[nercix]

Ingen svar gjorde at eg måte vri hovudet mitt litt meir :S

 

compare = lambda A,X: A[0] not in X and A[1] not in X

def check(mlist, control):
   for A in mlist:
       retur = A
       for X in control:
           if compare(A,X)==False: retur = False
       if retur != False: return retur
   return None

def s_sort(mlist):
   control = []
   mlist.sort()
   control.append(mlist[0])
   mlist_len = len(mlist)
   mlist.remove(mlist[0])
   T=0
   while len(control)<mlist_len:
       info = check(mlist, control[T:])
       if info == None:
           T +=1
           continue
       if info == False: continue
       control.append(info)
       mlist.remove(info)
   return control

Trur denne dekker det eg ønsker

 

Edit: Deler av koda forsvant.

Endret 29. oktober 2007 av nercix

[ekorniminator]

Ingen har vel vondt av å vri hodet litt Men jeg har skrevet et program foreløpig, men det er alt for tregt! Tenker på en grådig algoritme, men er ikke helt kommet i mål der grunnet dårlig tid..

 

Selv har jeg ingen python kunnskaper, så tror du du kunne forklart fremgangsmåten din for å få sortert tuplene?

[nercix]

Det som skjer.

 

Første leddet i mlist blir overført til control.

Kjører deretter gjennom mlist og legger til ledda som ikkje finnast i control.

Når check ikkje finn ledd som ikkje finnast i control (return None), kutter eg ned på control-lista som check-funksjonen sjekker mot og loopen fortsetter til control blir like stor (lang) som mlist var. Koden forklarer dette bedre enn det eg klarer å forklare (no som den er rett også!).

 

Ikkje mest intelligent metoden å ordne det på, men den er god nok til mitt bruk