c++ Aufgabenstellung

while(true) cout << rand() << rand() << rand();

https://en.cppreference.com/w/cpp/algorithm/next_permutation

Mr. Thyristor schrieb:
> Hi
>
> ich möchte von den 10 Zahlen zwischen 1 bis 10 jede mögliche Anordnung
> erhalten.
> ich denk schon die ganze Nacht drüber nach, wie man das Problem in C++
> lösen könnte, aber alle meine Ideen sind äußerst kompliziert und
> umständlich. Ich bin relativ sicher, dass die Aufgabe relativ einfach zu
> lösen wäre.
>
> Hat jemand eine Idee?

10^10-1

Die erste 10 enthält alle möglichen zulässigen Zeichen, also 1 bis 10.
Und die zweite 10 im Exponenten enthält die Länge der Ausgabe.

Im Prinzip ist das wie bei Binärzahlen, wenn man bspw. sagt 2^8-1, was 
für 2 Möglichkeiten also 0 oder 1 und der Länge 8 steht.
Fängt man mit 1 zu zählen an und hört bei 2^8-1, also 255 auf, dann hat 
man alle Kombinationen.

Die 0 hast du nicht drin, du kannst mit ihr aber rechnen und müsstest 
sie dann lediglich in der Ausgabe durch eine 10 ersetzen.

Um alle Kombinationen zu haben müsstest du somit nur von 1 bis 10^10-1 
hochzählen und alle Nullen durch eine 10 ersetzen.

Zu beachten ist noch, dass du natürlich führende Nullen, die beim 
hochzählen nicht dabei sein werden, selber dranhängen und durch eine 10 
ersetzen musst.

Als es noch nicht für jedes Problem eine passende Komponente gab, hatten 
die Leute alle Permutationen mit dem Backtracking Algorithmus erzeugt.

Rolf M. schrieb:
> Dann erzähl doch mal, wie du vorgehen würdest.

Ich habe 9 verschachtelte for Schleifen (0-9) gemacht, und in jeder vor 
Ausgabe der Nummer überprüft, ob die Nummer schon in den vorherigen 
Schleifen vorkommt.
D.h. DIe zweite Schleife hat alle Zahlen 0-9 augegeben, bis auf der von 
Schleife 1. Schleife 3 alle Zahlen 0-9 außer den beiden von Schleife 1 
und Schleife 2 usw.

Die letze (zehnte) Zahl hab ich nur noch per Abfrage bestimmt, d.h. die 
Zahl 0-9, die noch nicht in den vorherigen Schleifen vorgekommen ist


Aber wie erwähnt, die Vorgangsweise habe ich für umständlich gehalten 
und war mir eigentlich sicher, es gibt einen einfacheren und vielleicht 
trivialen Weg...

> es gibt einen einfacheren und vielleicht trivialen Weg

Mathematiker behaupten, das trivialste sei eine rekursive Funktion. Alle 
anderen Menschen sind der Ansicht, 9 ineinander geschachtelte Schleifen 
sind das einfachste.

So was in der Art: Pseudocode
[code]
funktion AlleAusgeben(List alleZahlen) {
  if (alleZahlen is Empty) {
    print (newline)
  for(zahl in alleZahlen) {
    print (zahl)
    restZahlen = alleZahlen - zahl
    AlleAusgeben(restZahlen)
  }
}

AlleAusgeben([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
[/code

Rolf M. schrieb:
> Nano schrieb:
>> 10^10-1
>
> Nein, es ist 10!, zumindest wenn mit "von den Zahlen … jede mögliche
> Anordnung" Permutationen ohne Wiederholung gemeint sind.

Ohne Wiederholung hat er nicht gefordert.
Wenn jede mögliche Anordnung gemeint ist, dann müssen da auch die 
Wiederholungen mit dabei sein.

Bsp. für jede mögliche Anordnung der Ziffern 0 bis 1 bei 3 Stellen 
ergibt:

1

000

2

001 **

3

010

4

011

5

100

6

101

7

110

8

111

** Schon hier kannst du die 2 führenden Nullen nicht einfach weglassen, 
weil die zuvor schon vorkamen. Also ist es mit Wiederholung.

Rolf M. schrieb:
> Vielleicht mal, wie ich die Aufgabe verstehe: Man stelle sich vor, der
> Herr Thyristor hat 10 Zettel, und auf jedem steht eine Zahl. Die legt er
> jetzt in einer Reihe nebeneinander auf den Tisch. Nun will er alle
> Reihenfolgen dieser 10 Zahlen haben, die möglich sind (sprich: alle
> Permutationen).

Ja, in dem Fall hättest du recht, aber diese Anforderung ergibt sich 
nicht aus seiner Threadfrage.
Da sollte er also noch einmal Klarheit schaffen.

Aus meiner Sicht meint er jede mögliche Kombination aus den Ziffern 1 
bis 10, wobei die auch mehrfach vorkommen dürfen.

Mr. Thyristor schrieb:
> Hat jemand eine Idee?
Hausaufgaben selber machen.

> Hausaufgaben selber machen.

Nö. Soweit ich es überblicke geht es hier um etwas ganz anderes.

Mr. Thyristor dachte sich seine Lösung selbst aus und kam zu dem Gefühl, 
das müsse wohl einfacher gehen.

Stimmt. Mr. Thyristor hat das richtige Bauchgefühl für einen Entwickler.
 In der STL finden sich passende Templatemethoden.
 Und es gibt einen prähistorischen Standard Algorithmus, der mit 10-15 
Zeilen auskommt.

Der Tipp wäre eher: Arbeite ein Lehrbuch zu Datenstrukturen und 
Algorithmen durch. Niklaus Wirth oder so etwas in der Art. Gibt es da 
was moderneres?

Zum Programmieren ist die Rekursion wohl die einfachste Methode:

- Für nur zwei Zahlen ist die Permutation triv.
- Für n+1 Zahlen setzt man die (n+1)-te Zahl auf 1 und spielt dann alle 
Permutationen der verbleibenden n Zahlen durch, Dann setzt man die 
(n+1)-te Zahl auf 2 und spielt wieder alle anderen durch, usw.

Ob das effizient, klein und schnell ist, ist nochmal eine andere Frage.

For i = 1000000000 to 10000000000
 ' erstellt jede Mögliche 10 Stellige Zahl
 ' i in string um wandeln.
 ' nach doppelten ziffern suchen (Instr.-Funktion)
 ' wenn nicht ausgeben.
next i

Fertig.

Man wie kann man aus einer einfach Zählerei so eine Wissenschaft machen.

Schlaumaier schrieb:
> Man wie kann man aus einer einfach Zählerei so eine Wissenschaft machen.
So ganz einfach ist es dann nicht. Es geht nicht "0..9", sondern 
"1..10". 10x die Zahl 10 ergibt eine 20-stellige Zahl:
10101010101010101010