Algorithmus, Kombination aus 10 Zahlen

  • Allgemein

Es gibt 4 Antworten in diesem Thema. Der letzte Beitrag () ist von Berater90.

    Algorithmus, Kombination aus 10 Zahlen

    Hallo Zusammen,

    ich stehe vor einem Problem. Ich möchte eine Programm schreiben, welches aus einer vorgegebenen Anzahl von Ziffern (z.B.10) und einer vorgegebenen Teilmenge (z.B. 4) sowie einer festen Quersumme (z.B. 26) alle möglichen Kombinationen errechnet. Jede Ziffer darf nur einmal gezogen werden. Das Thema "Partitionierung", mit dem ich mich schon beschäftigt habe, funktioniert hier also nicht. Ich möchte das Script gern in Excel (VBA) schreiben, weil ich mir dort alle Kombinationen auflisten lassen kann.

    Der Quellcode ist nicht mein Problem. Ich finde den richtigen Algorithmus für die Berechnung nicht.

    Meine Ansätze:

    Gegeben:

    Ziffernvorat (1/2/3/4/5/6/7/8/9/10)
    Anzahl der verwendeten Ziffern 4
    Quersumme 26

    Gesucht:

    Alle möglichen Kombinationen -> Aufgelistet

    Lösungsansatz:

    Schleife Beginn
    26 - 10 = 16 - 9 = 7 - 8 = Falsch - 7 = 0 ergibt 10/9/7
    blockiere kleinste Ziffer des vorherigen Ergebnisses (also 7)
    26 - 10 = 16 - 9 = 7 - 8 = Falsch - 6 = 1 - 5 = Falsch - 4 = Falsch - 3 = Falsch - 2 = Falsch - 1 = 0 ergibt 10/9/6/1
    blockiere zweit kleinste Ziffer des vorherigen Ergebnisses (also 6)
    26 - 10 = 16 - 9 = 7 - 8 = Falsch - 5 = 2 - 4 = Falsch - 3 = Falsch - 2 = 0 ergibt 10/9/5/2
    blockiere zweit kleinste Ziffer des vorherigen Ergebnisses (also 5)
    26 - 10 = 16 - 9 = 7 - 8 = Falsch - 4 = 3 - 3 = 0 ergibt 10/9/4/3
    blockiere zweit kleinste Ziffer des vorherigen Ergebnisses (also 4)
    26 - 10 = 16 - 9 = 7 - 8 = Falsch - 3 = 4 - 2 = 2 - 1 = 1 Aussage falsch
    ...

    Irgendwie lässt sich dieser Algorithmus nicht ordentlich in einem Code abbilden. Das Blockieren der Zahlen hat keine Homogenität Würde es was bringen, wenn man in jeder Runde die kleinste Zahl blockiert? Also 1, dann 2, dann 3 ...

    Hat jemand eine Idee? Ich hänge hier irgendwie fest. Vielen Dank schon mal für eure Antworten.

    Gruß
    Berater :) :)

    *Topic verschoben*

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Marcus Gräfe“ ()

    Wie wäre es mit Rekursion?

    Definniere eine Funktion, die Ziffernvorrat, Anzahl der verwendeten Ziffern und eine Quersumme entgegennimmt.
    Die geht alle möglichen Ziffern durch und ruft sich selbst mit aktualisierter Quersumme und Ziffernzahl auf.

    Oder anders:
    Finde alle möglichen Zahlen mit entsprechender Quersumme, deren Ziffern der Größe nach sortiert sind (das dürfte einfacher sein)
    und permutiere dann die Ziffern dieser Zahlen auf alle möglichen Weisen.

    in Permutationen gehe ich auch ganz allgemein auf die rekursive Vorgehensweise beim permutieren ein.
    Dort hab ich auch gezeigt, wie man auf dem dort angegebenen Prinzip zB. einen "Summanden-Permutations-Algo" aufbaut, und der kommt deiner gewünschten Quersummen-Permutation glaub recht nahe.

    Aber natürlich nicht in Excel-VBA.

    Sieht etwas nach Knapsack aus (NP-Vollständig).
    Ermittel' alle Teilmengen mit k Elementen und berechne die Summe. Wobei k die Anzahl der zu ziehenden Ziffern ist. Bei insgesamt n Zahlen gibt es aber binom(n,k) viele Möglichkeiten, welche du alle testen müsstest. Bei "großen" Mengen wird das also nicht mehr funktionieren.

    Hier mal als Pseudo-Code der dir alle Kombinationen mit gewünschter Summe und k Elementen ausgibt:

    Quellcode

    1. function find(list, ref l, target_ds, k, ds=0, i=0) {
    2. if ds == target_ds and l.length == k {
    3. print l
    4. }
    5. if ds > target_ds or l.length > k {
    6. return;
    7. }
    8. for j = i; j < list.length; ++j {
    9. l.add(list[j])
    10. find(list, l, target_ds, k, ds + list[j], j+1)
    11. l.remove_last()
    12. }
    13. }
    15. list = [1,2,3,4,5,6,7,8,9,10]
    16. l = []
    17. find(list, l, 26, 4)


    Bin davon ausgegangen, dass du mit Quersumme einfach die Summe meinst. Ansonsten wäre es z.B. bei 10 ja 1.
    Die initiale Liste kann auch doppelte Zahlen btw. Lücken enthalten. Ist sie sortiert ist die Ausgabe in lexikographischer Reihenfolge.

    Edit: Warum ist das eigentlich in Off-Topic?

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „3daycliff“ ()

Facebook
Telefonspende