21 svar
106 visningar
Micimacko är nöjd med hjälpen!
Micimacko 2095
Postad: 19 okt 2020

Ordlek

Sitter helt fast på hur man kan lösa det här. Jag kan testa om en lista är som de vill ha den eller inte, så tänkte att jag kanske kan sätta ihop alla permutationer och testa, men har ingen aning om hur jag skulle få fram alla dem isf.

emilg 355
Postad: 19 okt 2020

Du skulle kunna använda rekursion för att söka igenom alla kombinationer.

Alternativ så kan du göra det enkelt för dig och använda permutations i itertools.

Visa spoiler

from itertools import permutations

for perm in permutations(['the','list','of','words']):

    print(perm)

Micimacko 2095
Postad: 19 okt 2020

Får inte importera saker. Hur hade du gjort med rekursion?

emilg 355
Postad: 19 okt 2020 Redigerad: 19 okt 2020

Aha. Då hade jag kopierat implementation av permutations()...:) Nej skämt åsido.

 

Först hade jag nog faktiskt skapat en dictionary så att jag snabbt kan se om det finns något ord som passar.

Men typ (pseudokod):

find(list, [])

function find(list, curr_list):

    if list is not ok: return false

    if list is empty:

        return curr_list

    for word in list:

        move word from list to curr_list

        ans = find(list, curr_list)

        if ans not false: return ans

        move word from curr_list to list

 

Kan mycket väl ha missat något...

 

 

    

Micimacko 2095
Postad: 19 okt 2020

Är listan du kallar list den man får från början och vill möblera om? Den kommer väl nästan alltid vara fel från början så då borde det bara stå falskt jämt om man testar det först?

Är tanken att orden ska byta ordning i for-loopen på något sätt?

emilg 355
Postad: 19 okt 2020

Oj, det skulle vara 

if curr_list is not ok: return false (det blir väl att kolla att om listan innehåller >= 2 ord så att sista ordet passar med näst sista).

Tanken med for-loopen är att testa alla varianter av ord som är kvar i listan (ju längre ner du kommer i rekursionen, desto färre är kvar i listan, till slut är den tom, om man nu kommer så långt).

Micimacko 2095
Postad: 19 okt 2020

Jag kan inte riktigt se vad som händer. Vad är tanken med curr_list?

emilg 355
Postad: 19 okt 2020

Nej det brukar vara lite svårt med rekursion att tänka ut exakt vad som händer. Rekommender att du implementerar det och skriver ut för att se.

curr_list är listan av ord i rätt ordning, som flyttats från list. Om du flyttat alla ord från list -> curr_list och curr_list är ok, så är du klar.

(Behövs en return false på slutet förresten, efter for-loopen)

Micimacko 2095
Postad: 19 okt 2020

Testade göra, men den kastar inte om någon ordning. Den släpper igenom listor som redan är rätt iaf. Vad har jag klantat till?

def bralista(x):
if len(x)<=1:
return True
t=x[0][-1]
for s in x[1:]:
if not s[0]==t:
return False
t=s[-1]
return True

def hittare(lst,ny):
if bralista(ny)==False:
return False
if not lst:
return ny
for x in lst:
ny += [x]
lst.remove(x)
ans=hittare(lst,ny)
if not ans==False:
return ans
lst+=ny[-1]
return False

print(hittare(['abc','efg','dce'],[]))

emilg 355
Postad: 20 okt 2020 Redigerad: 20 okt 2020

Först och främst är det väl inget superbra testfall eftersom det inte finns en lösning där.

Har du testat så att bralista(x) fungerar som du tänker? (ledning: det tror jag inte den gör)

Lägg till print('Listor: ', lst, ny) innan ans=hittare(lst,ny) så kan du se vad som händer.

Använd lista.append(x) när du lägger till i en lista. Sen på slutet måste du ta bort ny[-1] (som ju är samma som x) från ny också, inte bara lägga till i lst.

Laguna 11645
Postad: 20 okt 2020

Om man vill använda en effektiv algoritm kan man titta här: https://en.wikipedia.org/wiki/Eulerian_path.

Mycket jobb för en ynka poäng, tycker jag, även om man bara använder brute force med rekursivitet.

emilg 355
Postad: 20 okt 2020

Hur menar du? Tänker du orden som en kant på något sätt, annars blir det inte så bra att besöka en nod mer än en gång.

Micimacko 2095
Postad: 20 okt 2020 Redigerad: 20 okt 2020

Åhh, jag älskar grafteori 😍 Men jag har aldrig kombinerat det med programering förut..

Fattar grejen med eulervägen och det, men hur gör man en graf i python? En lista med ordnade par?

Laguna 11645
Postad: 20 okt 2020

Här har kanten en egenskap också, nämligen sitt ord, så man kan använda en lista av tre-tupler, med första bokstaven, sista bokstaven, samt hela ordet. Man kanska vill använda dictionaries i stället.

emilg 355
Postad: 20 okt 2020

Fortfarande inte riktigt klart för mig hur det blir effektivt :)

Men problemet går ju bra att formulera som ett grafproblem. Tänker att orden är noder, sen skapa kanter genom att följa regeln med bokstäverna. Gör man DFS (depth first search) blir det ju ungefär som ovan, en BFS (breadth first search) kanske kan vara något effektivare (starta från alla noder), men tveksamt?

Micimacko 2095
Postad: 20 okt 2020

Sak samma om det är effektivt, jag har aldrig testat graf så bara det funkar. 

Jag tror bralista gör vad jag tänker?

emilg 355
Postad: 20 okt 2020 Redigerad: 20 okt 2020

Aha, när jag kopierade inte din kod intenderade jag t=s[-1] fel (går ju inte att skriva kod här alltså, suck).

Men då ser det ju bra ut! Så här ändra jag din for-loop:

for x in lst:
  ny.append(x)
  lst.remove(x)
  ans=hittare(lst,ny)
  if not ans==False:
    return ans
  lst.append(x)
  ny.remove(x)

Micimacko 2095
Postad: 20 okt 2020

Vad är det för fel på att plussa listor? Och det verkar bli något konstigt efter ett tag, den hoppar över steg..

emilg 355
Postad: 20 okt 2020

Ah sorry, det är inte en bra idé att ta bort något från en lista medan det itereras över samma lista.

Du kan lösa det genom att göra en kopia.

iter_list = lst.copy()

for x in iter_list:

   ...

Micimacko 2095
Postad: 20 okt 2020

Nu funkar det ju 😃👏👏

Ska se om jag hittar någon lättare uppgift att öva grafer med, men det måste definitivt testas också. Tack!

Micimacko 2095
Postad: 22 okt 2020
emilg skrev:

Aha. Då hade jag kopierat implementation av permutations()...:) Nej skämt åsido.

    

Går det här att göra utan tillgång till internet?

emilg 355
Postad: 22 okt 2020 Redigerad: 22 okt 2020
Micimacko skrev:
emilg skrev:

Aha. Då hade jag kopierat implementation av permutations()...:) Nej skämt åsido.

    

Går det här att göra utan tillgång till internet?

Nja, om du bara har ett standardsystem så lär det väl inte finnas där. Men om du laddade ner källkoden till python och sen kompilerade det själv, ja då har du det på din dator.

(cPython är dock implementerat i C tror jag)

Svara Avbryt
Close