Permutationer och rekursion
Hej. Idag har jag suttit med en och samma uppgift hela dagen, jag har väl kommit 2/3 av vägen men sen tar det stopp.
Än så länge har jag kommit fram till:
Och här är feedbacken programmet ger:
Jag har försökt en den men jag får inte fram BAC och BCA.
Jag tror också att min kod kommer att fallera om de inför en sträng på 4 bokstäver.
Är det någon som har tankar eller tips?
All feedback uppskattas.
Tack!
Det står "skriv färdigt". Hur såg det ut från början?
Så här såg det ut från början:
Jaha, där var det ju inte så mycket hjälp.
Jag förstår nog inte din algoritm. Framförallt är det ett principiellt fel: Du loopar över strängen, men du anropar permute rekursivt bara en gång i loopen. Det kan inte bli tillräckligt många anrop för att generera alla permutationer.
Vad är din huvudidé i algoritmen?
Rekursion handlar om att lösa problem genom att hänvisa till enklare versioner av samma problem (som hänvisar till ännu enklare versioner, och så vidare, tills det "landar" i ett eller flera triviala basfall). I det här fallet ska du hitta permutationer. Kan du komma på ett sätt att hitta permutationer med hjälp av *enklare* permutationer?
I brist på ledning så var det där en chansning.
Jag har fått läsa en del på nätet för att komplettera. Nu skulle jag beskriva tanken så här:
Hoppas bilden är överskådlig.
Tänkte byta tecken successivt enligt trädet. Först byta första, sen andra. Varje gång jag kommer längst ner i trädet är tanken att jag ska printa.
Så om vi börjar klättra ner i vänstra änden, i ABC byter jag A mot A. Sen byter jag B mot B printar ABC. Tillbaka upp ett steg och byter B mot C printar. Sen hela vägen upp till toppen och byter A mot B.....
Hoppas du kan förstå vad jag menar blev lite klumpigt här
Det går nog att lösa problemet med den metoden, men det är inte det enklaste sättet. En ytterligare ledning i den riktning jag vill få dig att tänka: Låtsas att du redan har en funktion skriven nånstans (vi kan säga att den heter perm2) som kan generera permutationer av strängar av längd 2, hur kan du använda den för att skapa permutationer av längd 3?
Okej okej, jag tror jag förstår nu. om Jag i loopen byter första bokstaven och en av de andra två och sedan skriver en hjälpfunktion som kan gör permutationer av de två sista skulle jag kanske kunna använda en stringbuilder för att få rätt på det. Jag ger det ett försök.
Det låter inte som hur jag menade =) Titta på permutationerna av ABC, där jag separerat den första bokstaven:
A, BC
A, CB
B, AC
B, CA
C, AB
C, BA
Det som kommer efter första bokstaven är permutationer av *resten* av bokstäverna. Alltså, när första bokstaven är A är de två efter antingen BC eller CB, vilket är permutationerna av B och C. Du kan därför bygga permutationer av längd 3 genom att loopa igenom varje bokstav i strängen, låta den bokstaven vara den första, kalla på en funktion som genererar alla permutationer av resten av bokstäverna, och sen bara sätta fast de kortare permutationerna som en svans efter första bokstaven.
Och den här principen gäller inte bara för permutationer av längd 2 eller 3, utan du kan alltid göra den här uppdelningen där du väljer en första bokstav och permuterar resten. Därför kan din rekursiva funktion kalla på sig själv; den är sin egen hjälpfunktion (förutsatt att du ger den ett basfall så att rekursionen inte blir en evig loop).
Okej jag tror jag förstår! Jag har lite svårt nu när jag sitter med det eftersom permute här är en void metod. Om jag spara en bokstav och skickar in resten i permute så får jag den inte att returnera permutationerna.
Ahååå, jag förstår! Det tänkte jag inte på. Då är jag osäker, det är kanske en annan metod de är ute efter ändå. Ursäkta sidospåret.
