Beiträge von -Gaston-

Hat niemand eine Idee? Nicht einmal Ansätze?

Hallo,

womöglich bin ich hier im falschen Unterforum. (Aber welches ist das richtige?)

Ich hätte da folgende Aufgabe, welche ich Lösen soll (ausprogrammieren).

Ich habe eine Kiste, welche 13 verschiedenen Objekte enthält.
Ich weis, in der Kiste sind je Objekt immer 0 bis 4 Stück enthalten. (Abhängig je Anwendungsfall.)

Wenn ich jetzt 4 Objekte aus der Kiste heraus nehme, wie viele Kombinationen gibt es, dass ich immer 4 verschiedene Objekte heraus nehme.


Kleines Beispiel: Wenn nur 4 verschiedene Objekte jeweils 4x in der Kiste wären, dann wären 16 Objekte in der Kiste. Wenn ich nun 4 Elemente heraus ziehe, dann gibt es 1820 Möglichkeiten. Aber bei wie vielen Möglichkeiten sind alle 4 Elemente verschieden?

Wie rechne ich das genau aus?


(Edit: Ich habe die Frage hier in eigenen Worten zusammengefasst, weil die vollständige Aufgabenbeschreibung wäre mir zu kompliziert es nieder zu schreiben.)

Ich hoffe ihr könnte mir helfen :o

-Gaston-

Als erstes einmal Thread des Monats... da stellt sich die Frage in welchem Sinne :coolgrim:

Als erstes einmal danke für den Tipp mit Quick-Sort. Ich war zur Threaderstellung etwas Müde und war beim Suchen nicht so fündig bei Google. Da hab ich immer Array-Sortmethoden gefunden. Mit hilfe von Quick-Sort hatte ich was nettes gefunden (http://www.vcskicks.com/five-element-sort2.php) Ich hab das ganze mit einem wunderschönen ewig langen unüberschaubaren IF - Baum gelöst (5-8 Vergleiche + jedes mal nur 1 finale Zuweisung) . Resultat die schnellste Lösung bis jetzt. (Natürlich mit der normalen Array.Sort() - Methode getestet..)

Zitat von Zaru

An dieser Stelle ein Hoch auf Algodat1

Hab ich noch nicht gehabt, kommt erst :thumb:

Zitat von Ramses13

- Das Einfügen in eine int-Liste alleine ist wahrscheinlich schon langsamer als obiger Bubble-Sort. Vom Sortieren ganz zu schweigen. Sortieren per int-List wird daher wohl eher Laufzeitnachteile bringen.

Das stimmt, deswegen hab ich keine List sondern ein Array verwendet und anschließend mit Array.Sort() sortiert. Der Bubble-Sort war aber trotzdem schneller. Womöglich aus dem Grund, weil ich das Array extra für das Sortieren aus den "5" Werten zusammen setzen musste. Dann die Schleifen auch noch, das kostet.

Zitat von Ramses13

Ein paar Bemerkungen:
- 1000 Milliarden mal sortieren "geht in die Sekunden hinein"? Bei welchem Computer bitte? Bei einer Sortierung pro Nanosekunde (unrealistisch schnell) würde man schon eine Viertelstunde dafür brauchen. Oder reden wir hier von Großrechnern mit zig-tausenden parallel arbeitenden CPUs?

Ich hab das eben kontrolliert. Mein test war mit ca. 35 Milliaren Sortierungen.

Zitat von JohnFoo

Es klingt auf jeden Fall ziemlich wichtig. Sicher ein Hacker. :////

Naja, das ist eher Interessenssache. Es geht teilweise um Wahrscheinlichkeiten. Ich hab jedoch das Problem, dass ich in jeder Situation alle Parameter erneut berechnen muss. Deswegen kann ich keine einfache Formel heranziehen und mir so das Ergebnis berechnen. Und die komplizierten Formeln, dafür fehlen mir ein paar Semester Mathe...

Pointer kann ich nicht nehmen, da die übergebenen Parameter nicht in der Basismethode abgeändert werden dürfen => Auswirkungen auf die Gesamtberechnung.

Zitat von Ramses13

Bei etwa 10 Elementen oder weniger sind die Klassiker ähnlich gut oder oft sogar besser.

Was ist ein Klassiker?

Edit: Int verwende ich wegen dem Konvertieren. Man könnte den Byte Datentyp verwenden, da der Maximalwert bei dieser Sortierung kleiner als 256 ist.

Hallo,

ich bin gerade dabei ein Programm zu erstellen und beim Testen fand ich raus, dass die Sortierung sehr langsam ist. Zuerst verwendete ich ein Array. Da ich aber für das Sortieren jedesmal extra ein Array erstellen musste, hab ich nun folgende Lösung gemacht:

(Sprache: C#)

private void Sort(int in1, int in2, int in3, int in4, int in5, out int out1, out int out2, out int out3, out int out4, out int out5) {
  out1 = in1;
  out2 = in2;
  out3 = in3;
  out4 = in4;
  out5 = in5;
 
  int tmp;
  if (out1 > out2) {
    tmp = out1;
    out1 = out2;
    out2 = tmp;
  }
  if (out2 > out3) {
    tmp = out2;
    out2 = out3;
    out3 = tmp;
  }
  if (out3 > out4) {
    tmp = out3;
    out3 = out4;
    out4 = tmp;
  }
  if (out4 > out5) {
    tmp = out4;
    out4 = out5;
    out5 = tmp;
  }
  if (out1 > out2) {
    tmp = out1;
    out1 = out2;
    out2 = tmp;
  }
  if (out2 > out3) {
    tmp = out2;
    out2 = out3;
    out3 = tmp;
  }
  if (out3 > out4) {
    tmp = out3;
    out3 = out4;
    out4 = tmp;
  }
  if (out1 > out2) {
    tmp = out1;
    out1 = out2;
    out2 = tmp;
  }
  if (out2 > out3) {
    tmp = out2;
    out2 = out3;
    out3 = tmp;
    if (out1 > out2) {
      tmp = out1;
      out1 = out2;
      out2 = tmp;
    }
  }
}

Dies ist zwar um ein vielfaches schneller als die vorherigen Varianten, aber das ist trotzdem noch zu langsam
Für das Sortieren gehen jetzt noch ca. 25% der Zeit drauf.
Kennt jemand eine schnellere Methode?

Edit: Mir ist klar, das ganze ist schon recht schnell gelöst, da das ganze aber ein paar 1000 Milliarden Mal sortiert wird, geht das trotzdem in die Sekunden hinein ...