Kombinationen ermitteln

1. offizieller Beitrag

    Schönen guten Tag! =)
    Ich sitze gerade an einem Problem wozu ich noch keinen Ansatz habe dies zu lösen. Daher kann ich auch keinen Code präsentieren. Ich möchte gerne alle Kombinationen in einen Array abspeichern, die mit wahlweise x Summanden die Summe y ergeben. Dabei sollen nur natürliche Zahlen berücksichtigt werden.

    Beispiel:
    Ich möchte alle Kombinationen ermitteln, welche die Zahl 5 (y) mit 2 Summanden (x) ergibt.

    Code
    1 + 4
2 + 3
3 + 2
4 + 1


    Das Gleiche möchte ich nun für 3 Summanden machen.

    Code
    1 + 1 + 3
1 + 2 + 2
1 + 3 + 1
2 + 1 + 2
2 + 2 + 1
3 + 1 + 1


    Dafür würde ich gerne in AutoIt eine Funktion schreiben, die dies für mich erledigt. Jedoch habe ich, wie ich bereits erwähnte, noch keinen Lösungsansatz dafür. Ich bitte um ein paar Anregungen.
    LG. Make =)

    Einmal editiert, zuletzt von Yjuq (1. März 2014 um 18:24)

    Die Aufgabe hat so wie du sie beschreibst unendlich viele Lösungen, ausser du schränkst die erlaubten Wertebereiche ausreichend ein. Deshalb solltest du zunächst einmal die Gegebenheiten klar formulieren.

    Deine Gleichung: y = a + b + ... + z

    Ich vermute jetzt mal, dass folgende Bedingungen gelten, auch wenn du das nicht klar definiert hast:

    - die x Summanden sind jeweils positiv (oder auch 0 ?)
    - die x Summanden sind Ganzzahlen ?

    Wenn du das so definierst kannst du die Minimal und Maximalwerte eines Summanden ermitteln (wenn 0 erlaubt ist dann wäre das Maximum bei y=5 die 5, wenn 0 nicht erlaubt ist wäre das Maximum 5-((x-1)*1), die Minimalwerte wären entsprechend 0 oder 1).
    Mit diesen Informationen könnte man dann einfach die dumme Probiermethode nutzen und in einer verschachtelten Schleife für alle x Summanden von Minimum nach Maximum alle Varianten durchprobieren.

    Einmal editiert, zuletzt von misterspeed (1. März 2014 um 15:41)

    Danke für deine Antwort!
    Sorry dass ich es nicht klar formuliert habe:
    Es sollen nur Summanden verwendet werden, die positive Ganzzahlen über 0 sind.
    Also genau die Bedingungen die du oben genannt hast.

    Ich versuch gerade mal diese "Probiermethode" umzusetzen.
    Falls noch jemand andere Vorschläge hat, ich bin ganz Ohr. :)

    • Offizieller Beitrag

    Bei zwei Summanden brauchst Du doch nicht viel probieren:

    Spoiler anzeigen
    [autoit]


    #include <Array.au3>
    $iSumme = 234
    $aSummand = _GetSumArray($iSumme)
    _ArrayDisplay($aSummand)

    [/autoit] [autoit][/autoit] [autoit]

    Func _GetSumArray($iSumme)
    Local $aOut[$iSumme - 1][2], $iIndex = 0
    Do
    $aOut[$iIndex][0] = $iIndex + 1
    $aOut[$iIndex][1] = $iSumme - $iIndex - 1
    $iIndex += 1
    Until $iIndex >= $iSumme - 1
    Return $aOut
    EndFunc ;==>_GetSumArray

    [/autoit]

    Probieren muss man wirklich nicht, da es sich ja mit einem einfachen Schema berechnen lässt.
    misterspeed hat ja schon die Formeln implizit anklingen lassen :

    • y = a + (y - a)
    • z = c + d + (z - c - d)


    Somit ergibt sich:

    Spoiler anzeigen
    [autoit]

    #cs

    [/autoit] [autoit][/autoit] [autoit]

    y = a + b mit y,a,b sind natürliche Zahlen

    [/autoit] [autoit][/autoit] [autoit]

    z = c + d + e mit z,c,d,e sind natürliche Zahlen

    [/autoit] [autoit][/autoit] [autoit]

    #ce

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    $summe1 = ""

    [/autoit] [autoit][/autoit] [autoit]

    $y = 5

    [/autoit] [autoit][/autoit] [autoit]

    For $a = 1 To ($y - 1)
    If $a > 1 Then
    $summe1 &= @CRLF
    EndIf
    $summe1 &= $y &" = "& $a &" + " & ($y - $a)
    Next

    [/autoit] [autoit][/autoit] [autoit]

    MsgBox(0,"Summe mit 2 Summanden bis " & $y, $summe1)

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ;#################################

    [/autoit] [autoit][/autoit] [autoit]

    $summe2 = ""

    [/autoit] [autoit][/autoit] [autoit]

    $z = 5

    [/autoit] [autoit][/autoit] [autoit]

    For $c = 1 To ($z - 2)
    For $d = 1 To ($z - $c - 1)
    If $d > 1 Or $c > 1 Then
    $summe2 &= @CRLF
    EndIf
    $summe2 &= $z &" = "& $c &" + " & $d & " + " & ($z - $c - $d)
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    MsgBox(0,"Summe mit 3 Summanden bis " & $z,$summe2)

    [/autoit]

    Wer immer nur das tut, was er bereits kann - wird auch immer nur das bleiben, was er bereits ist!

    Moin,

    Um das Problem anzugehen gibt es mehrere Methoden. Die einfachste ist natürlich Brute Force.
    Ein weiteres Hindernis ist die nicht vorhersehbare Anzahl aufspaltungen (in deinem Beispiel läuft das alles mit 2 oder 3 Summanden, aber was ist mit 4, 5, 6, ..., n ?)
    Da man in AutoIt keine variable Schleifenschachtelung hat (hab keine Ahnung ob es eine Sprache gibt die sowas besitzt), kann man kein Programm schreiben, welches sich auf die Anzahl Aufspaltungen automatisch anpasst. (In Deutsch: Mit einem Programm mit 2 Schleifen kann man ausschließlich 2 Summanden bestimmen, aber nicht 3, 4, ..., n)

    Da wir aber nicht gänzlich bescheuert sind, basteln wir uns diese Funktionalität einfach selbst.
    Dazu nimmt man ein n Dimensionales Array welches die einzelnen Schleifenzähler darstellt (Array = Anpassbar).
    Anschließend zählen wir die Schleifen (rekursiv) Stück für Stück nach oben. (Rekursion ist hier unumgänglich !).
    Das Resultat: Eine Variable Schleifenverschachtelung.

    Ein kleines Beispiel gibts hier. Das kann natürlich noch optimiert werden. (Man kann große Ergebnisräume ausschließen wenn z.B. die erste Zahl eine 4 ist braucht man nicht mehr 4+2, 4+3, usw absuchen).

    Überraschung !
    [autoit]

    #include <Array.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Global $a = _Calc(7, 4)
    _ArrayDisplay($a)

    [/autoit] [autoit][/autoit] [autoit]

    Func _Calc($nErg, $iCnt)
    Local $aRet[0][$iCnt], $u, $aCnt[$iCnt], $iPos = $iCnt - 1
    Local $iSum
    For $i = 0 To $iCnt - 1 Step 1
    $aCnt[$i] = 1
    Next
    Do
    $iSum = 0
    For $i = 0 To $iCnt - 1 Step 1
    $iSum += $aCnt[$i]
    Next
    If $iSum = $nErg Then
    $u = UBound($aRet)
    ReDim $aRet[$u+1][$iCnt]
    For $i = 0 To $iCnt - 1 Step 1
    $aRet[$u][$i] = $aCnt[$i]
    Next
    EndIf
    Until Not _Array($iCnt, $aCnt, $iPos, $nErg)
    Return $aRet
    EndFunc ;==>_Calc

    [/autoit] [autoit][/autoit] [autoit]

    Func _Array(ByRef $iCnt, ByRef $aCnt, ByRef $iPos, $nErg)
    $aCnt[$iPos] += 1
    If $aCnt[$iPos] = $nErg And $iPos > 0 Then
    $aCnt[$iPos] = 1
    $iPos -= 1
    _Array($iCnt, $aCnt, $iPos, $nErg)
    $iPos += 1
    EndIf
    If $aCnt[0] = $nErg Then Return False
    Return True
    EndFunc ;==>_Array

    [/autoit]

    lg
    M

    Hi,
    schau dir mal die Verfahren zur Optimierung, bspw. Zuschnittoptimierung von Stangen oder Platten an. Also n verschiedene Längen/Flächen, die möglichst ohne (oder minimalem) Rest aus vorhandenen Stangen/Platten herausgeschnitten werden sollen.
    Da wird nicht mit n-dimensionalen Array´s gearbeitet, das würde den Speicher komplett sprengen :P
    Viel eher werden Sortierverfahren genutzt. Man nimmt die größten Teilstücke und fügt sie so lange aneinander, bis das vorgegebene Limit erreicht (dann Ende) oder überschritten wird. Dann geht man einen Schritt zurück und nimmt das nächste kleinere Teilstück uswusf, bis entweder die genaue Länge/Fläche (bei dir die Summe) erreicht ist, oder (bei einer Zuschnittoptimierung) das Reststück möglichst klein ist.
    Bei einer Zuschnittoptimierung wäre hier Schluss, da das "Optimum" erreicht wurde.
    In deinem Fall beendet man den Algorithmus aber nicht, sondern lässt ihn so lange weiterlaufen, bis die Summe ausschliesslich von den kleinsten "Teilstücken" erreicht wurde. Das ist die letzte aller möglichen Lösungen und das Abbruchkriterium wurde erreicht.