Übungsblatt 3 - Mischen Impossible

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Übungsblatt 3 - Mischen Impossible
Muss man die Aufgabe 2 vom Blatt 3 rekursiv lösen oder sind auch iterative Lösungen erlaubt?

3

Siehe hier:

Tut euch selbst einen Gefallen und versucht es rekursiv - man lernt an diesem kleinen Beispiel sicher eine ganze Menge (auch aber nicht nur für die Klausur) dazu…

4

Wenn ich das richtig gesehen habe, so ist s nicht zwingend an nur 3 Buchstaben gebunden, sondern kann auch mehr oder weniger haben korrekt?

5

Ja.

6

ok ich fasse mal zusammen, was das Teil alles machen soll und vermutlich denke ich wieder viel zu kompliziert dabei (das hat mir schon ein paar mal das Genick gebrochen und viel Arbeitszeit in AuD gekostet):

  1. benötige ich für die Länge des Arrays die maximale Anzahl an möglichen Kombinationen, bei 3 Zeichen wären das 15 (wie in den Beispielen, steigt natürlich Exponential mit höherer Anzahl von Zeichen)
  2. Ein Zeichen ist der Basisfall (ich vermute mal hier werden 2 benötigt)
  3. sobald Arrayplatz 0 und 1 nicht mehr null sind fangen die kombies an (methode zum vertauschen wird benötigt)
  4. Leerzeichen berücksichtigen ja oder nein?
  5. während ich das hier so tippe, fällt mir ein, kann es sein das wir uns hier schon im Bereich von Backtracking bewegen, dann wäre natürlich ein weiterverwenden der bisher gespeicherten Ergebnisse sinnvoll (würde zumindest, nach meinem bisherigen Verständnis der Aufgabe, Sinn machen.)? (Nach dem Tutor-Foliensatz, der bisher online steht vermute ich aber eher nicht das es BT ist. ;-))
7

…

Nicht unbedingt a priori: Die Rekursion kann die Teillösungen beim „Zurückkehren aus der Rek.-Tiefe“ zusammensetzen, daher der Verweis auf [m]Arrays.copyOf[/m]

fast - beides nur fast

? zombies?

Jein - auch ein WhiteSpace ist nur eine Nummer in der ASCII-Tabelle (oder Unicode, oder so) - also indirekt ja, direkt nö.
Und ehe Rückfragen kommen: dito für Hochkomma, Komma, eckige Klammern, Totenköpfe, …

BT ist für mich auch nur Rekursion :stuck_out_tongue: - aber IMHO wird hier noch nichts „gebacktracked“.

Hinweis: Wendet den Induktionsgedanken zur Konstruktion an! Fragt euch dabei: wie löse ich das Problem für n Zeichen, wenn ich schon eine Lösung für n-1 Zeichen hätte…

8

Vielleicht als Hilfestellung zwei weitere Ausgaben mit den Eingaben abcd [abcd, abc, abdc, abd, ab, acbd, acb, acdb, acd, ac, adbc, adb, adcb, adc, ad, a, bacd, bac, badc, bad, ba, bcad, bca, bcda, bcd, bc, bdac, bda, bdca, bdc, bd, b, cabd, cab, cadb, cad, ca, cbad, cba, cbda, cbd, cb, cdab, cda, cdba, cdb, cd, c, dabc, dab, dacb, dac, da, dbac, dba, dbca, dbc, db, dcab, dca, dcba, dcb, dc, d] und

abcde [abcde, abcd, abced, abce, abc, abdce, abdc, abdec, abde, abd, abecd, abec, abedc, abed, abe, ab, acbde, acbd, acbed, acbe, acb, acdbe, acdb, acdeb, acde, acd, acebd, aceb, acedb, aced, ace, ac, adbce, adbc, adbec, adbe, adb, adcbe, adcb, adceb, adce, adc, adebc, adeb, adecb, adec, ade, ad, aebcd, aebc, aebdc, aebd, aeb, aecbd, aecb, aecdb, aecd, aec, aedbc, aedb, aedcb, aedc, aed, ae, a, bacde, bacd, baced, bace, bac, badce, badc, badec, bade, bad, baecd, baec, baedc, baed, bae, ba, bcade, bcad, bcaed, bcae, bca, bcdae, bcda, bcdea, bcde, bcd, bcead, bcea, bceda, bced, bce, bc, bdace, bdac, bdaec, bdae, bda, bdcae, bdca, bdcea, bdce, bdc, bdeac, bdea, bdeca, bdec, bde, bd, beacd, beac, beadc, bead, bea, becad, beca, becda, becd, bec, bedac, beda, bedca, bedc, bed, be, b, cabde, cabd, cabed, cabe, cab, cadbe, cadb, cadeb, cade, cad, caebd, caeb, caedb, caed, cae, ca, cbade, cbad, cbaed, cbae, cba, cbdae, cbda, cbdea, cbde, cbd, cbead, cbea, cbeda, cbed, cbe, cb, cdabe, cdab, cdaeb, cdae, cda, cdbae, cdba, cdbea, cdbe, cdb, cdeab, cdea, cdeba, cdeb, cde, cd, ceabd, ceab, ceadb, cead, cea, cebad, ceba, cebda, cebd, ceb, cedab, ceda, cedba, cedb, ced, ce, c, dabce, dabc, dabec, dabe, dab, dacbe, dacb, daceb, dace, dac, daebc, daeb, daecb, daec, dae, da, dbace, dbac, dbaec, dbae, dba, dbcae, dbca, dbcea, dbce, dbc, dbeac, dbea, dbeca, dbec, dbe, db, dcabe, dcab, dcaeb, dcae, dca, dcbae, dcba, dcbea, dcbe, dcb, dceab, dcea, dceba, dceb, dce, dc, deabc, deab, deacb, deac, dea, debac, deba, debca, debc, deb, decab, deca, decba, decb, dec, de, d, eabcd, eabc, eabdc, eabd, eab, eacbd, eacb, eacdb, eacd, eac, eadbc, eadb, eadcb, eadc, ead, ea, ebacd, ebac, ebadc, ebad, eba, ebcad, ebca, ebcda, ebcd, ebc, ebdac, ebda, ebdca, ebdc, ebd, eb, ecabd, ecab, ecadb, ecad, eca, ecbad, ecba, ecbda, ecbd, ecb, ecdab, ecda, ecdba, ecdb, ecd, ec, edabc, edab, edacb, edac, eda, edbac, edba, edbca, edbc, edb, edcab, edca, edcba, edcb, edc, ed, e]

9

@ gaku:

Ist es nicht eher so richtig:

abcd:
[d, c, dc, cd, b, db, bd, cb, bc, dcb, dbc, bdc, cdb, cbd, bcd, a, da, ad, ca, ac, dca, dac, adc, cda, cad, acd, ba, ab, dba, dab, adb, bda, bad, abd, cba, cab, acb, bca, bac, abc, dcba, dcab, dacb, adcb, dbca, dbac, dabc, adbc, bdca, bdac, badc, abdc, cdba, cdab, cadb, acdb, cbda, cbad, cabd, acbd, bcda, bcad, bacd, abcd]

abcde:
[e, d, ed, de, c, ec, ce, dc, cd, edc, ecd, ced, dec, dce, cde, b, eb, be, db, bd, edb, ebd, bed, deb, dbe, bde, cb, bc, ecb, ebc, bec, ceb, cbe, bce, dcb, dbc, bdc, cdb, cbd, bcd, edcb, edbc, ebdc, bedc, ecdb, ecbd, ebcd, becd, cedb, cebd, cbed, bced, decb, debc, dbec, bdec, dceb, dcbe, dbce, bdce, cdeb, cdbe, cbde, bcde, a, ea, ae, da, ad, eda, ead, aed, dea, dae, ade, ca, ac, eca, eac, aec, cea, cae, ace, dca, dac, adc, cda, cad, acd, edca, edac, eadc, aedc, ecda, ecad, eacd, aecd, ceda, cead, caed, aced, deca, deac, daec, adec, dcea, dcae, dace, adce, cdea, cdae, cade, acde, ba, ab, eba, eab, aeb, bea, bae, abe, dba, dab, adb, bda, bad, abd, edba, edab, eadb, aedb, ebda, ebad, eabd, aebd, beda, bead, baed, abed, deba, deab, daeb, adeb, dbea, dbae, dabe, adbe, bdea, bdae, bade, abde, cba, cab, acb, bca, bac, abc, ecba, ecab, eacb, aecb, ebca, ebac, eabc, aebc, beca, beac, baec, abec, ceba, ceab, caeb, aceb, cbea, cbae, cabe, acbe, bcea, bcae, bace, abce, dcba, dcab, dacb, adcb, dbca, dbac, dabc, adbc, bdca, bdac, badc, abdc, cdba, cdab, cadb, acdb, cbda, cbad, cabd, acbd, bcda, bcad, bacd, abcd, edcba, edcab, edacb, eadcb, aedcb, edbca, edbac, edabc, eadbc, aedbc, ebdca, ebdac, ebadc, eabdc, aebdc, bedca, bedac, beadc, baedc, abedc, ecdba, ecdab, ecadb, eacdb, aecdb, ecbda, ecbad, ecabd, eacbd, aecbd, ebcda, ebcad, ebacd, eabcd, aebcd, becda, becad, beacd, baecd, abecd, cedba, cedab, ceadb, caedb, acedb, cebda, cebad, ceabd, caebd, acebd, cbeda, cbead, cbaed, cabed, acbed, bceda, bcead, bcaed, baced, abced, decba, decab, deacb, daecb, adecb, debca, debac, deabc, daebc, adebc, dbeca, dbeac, dbaec, dabec, adbec, bdeca, bdeac, bdaec, badec, abdec, dceba, dceab, dcaeb, daceb, adceb, dcbea, dcbae, dcabe, dacbe, adcbe, dbcea, dbcae, dbace, dabce, adbce, bdcea, bdcae, bdace, badce, abdce, cdeba, cdeab, cdaeb, cadeb, acdeb, cdbea, cdbae, cdabe, cadbe, acdbe, cbdea, cbdae, cbade, cabde, acbde, bcdea, bcdae, bcade, bacde, abcde]

10

hätte jetzt auch eher Chayyams Ergebnis erwartet. :slight_smile:

Naja ich seh für die Klausur schon wieder ganz düster… wenns mit der Rekursion nicht besser wird :frowning:

11

In der Aufgabenstellung lautet es doch:

Die Reihenfolge der r_i in r ist beliebig.

Ich denke die Idee des Aufgabenstellers ist die Rekursion und nicht (notwendigerweise) die Reihenfolge des Ergebnisses.

12

exakt! :wink:

13

Danke für die Erklärungen der Aufgabenstellung.

14

ich sage mal so, aus den Erfahrungen des letzten Semesters, es kam immer auf die Reihenfolge an. :wink:

15

Dann sage ich es mal anders :smiley:
Aus den Erfahrungen der letzten paar Semester, behaupte ich, dass es eher selten um die Reihenfolge bei Aufgaben mit Rekursion geht.
Beispielhaft fallen mir gerade der Sodoku-solver und die Weingläseraufgabe ein.
Bemekerung: Das waren aber die Aufgaben mit Backtracking

16

naja gut eh, meine Aussage war jetzt nicht spezifisch auf die Aufgaben der Rekursion beschränkt ;)…

17

Dann das „immer“ durch „häufig“ ersetzen und wir sind beide zufrieden :stuck_out_tongue:

18

gefühlt war es aber immer :wink:

aber auf häufig können wir uns auch einigen. :smiley:

19

also johnDoe nix gegen deine Aufgaben, aber irgendwie geht mir die aufn §$%&§$%/&. ^^

leerer string kein thema kommt nen leeres Array zurück, ein Zeichen, auch kein Thema, aber sobald es 2+ wird krieg ich nur ein [null] oder ne endlosschleife oder ne StringIndexoutofbound … raus ^^ und ich steh aufm schlauch wieso (klar das hat sicherlich was mit meinem Aufruf hier zu tun, da wenn ich direkt substring von s aufrufe, auch genau die Zeichenfolge im ersten Feld des Array zurückgegeben wird).

20

Hallo , kurze Frage, wäre folgendes möglich, also erlaubt


public static String[] mischen (String s){

.............

return mischen (<Parameter>, ...........,<Parameter>);

}

private static String [] mischen (<Parameter>, ...........,<Parameter>){

...........;

}

Danke!