gültige Kombination finden

    Hallo!
    Ich habe zwei Listen:
    A 1
    B 2
    C 1
    D 3
    E 0
    F 0
    (natürlich deutlich länger)

    (Anzahl gleich Summe aller Zahlen in der 1. Liste)
    AB:
    AD:
    AC:
    AF:
    BD:
    BC:
    ED:

    Jetzt muss hinter jede Zeile der zweiten Liste ein Buchstabe stehen. Dabei dürfen aber die in der ersten Liste genannten Limits nicht unterschritten werden.
    1700 Einträge hat die erste Liste,
    2700 die zweite.

    Bei dem Beispiel möchte ich dann z.B. diese Ausgabe:

    AB: B
    AD: D
    AC: C
    AF: A
    BD: D
    BC: B
    ED: D

    Wenn das Limit 0 ist, muss der andere Buchstabe ausgewählt werden. Der zweite eindeutige Fall ist, wenn das Limit der Anzahl der offenen Listeneinträge, in dem der Buchstabe vorkommt, entspricht.

    Die Datenstruktur habe ich wie folgt interpretiert:
    $limits[X][0] Limit
    $limits[X][1] Buchstabe
    $limits[X][2] Anzahl der Vorkommnisse
    $limits[X][3] Quotient Limit durch Anzahl

    $verbindung[X][0] erster Buchstabe
    $verbindung[X][1] zweiter Buchstabe
    $verbindung[X][2] Lösung

    In der ersten Liste wird angegeben, wie oft der jeweilige Buchstabe als Lösung in der zweiten Reihe existieren darf.

    Die Aufgabenstellung ist:
    Jeder Schüler hat ein individuelles Limit an Aufgaben, die er erledigen muss (limits.txt). Jede Zeile in der Datei aufgaben.txt stellt eine Aufgabe da, die entweder der eine, oder der andere Schüler bearbeiten muss. Finden Sie eine Lösung, bei der kein Schüler zu viele oder zu wenig Aufgaben bearbeiten muss. Geben Sie dazu für jede Zeile an, welcher Schüler die Aufgabe zugeteilt bekommen soll.

    Also z.B.:
    Tom 1
    Peter 2
    Lisa 0

    Tom Peter : Peter
    Lisa Peter : Peter
    Tom Lisa : Tom

    Zuerst kann man die eindeutigen Fälle bestimmen: Wenn das Limit 0 ist (bei jeder Festlegung wird aktuallisiert), muss der andere Name ausgewählt werden. Der zweite eindeutige Fall ist, wenn das Limit der Anzahl der offenen Listeneinträge, in dem der Name vorkommt, entspricht (z.B. Peter, 2 Einträge, Limit 2).
    meine Datenstruktur:
    $limits[X][0] Limit
    $limits[X][1] Name des Schülers
    $limits[X][2] Anzahl der Aufgaben
    $limits[X][3] Quotient Limit durch Aufgabenanzahl

    $verbindung[X][0] erster Name
    $verbindung[X][1] zweiter Name
    $verbindung[X][2] wird bearbeitet von...

    Ziel ist es, das jeder sich an sein Limit hällt und nicht mehr oder weniger zu bearbeiten hat. Jede Namenskombination kommt nur ein mal vor.

    Ich habe es nach dem Verfahren hierversucht

    [autoit]

    Global $fertig = False

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

    Func loesungfinden($nr)
    While $fertig == False
    $erfolg = Suchen($nr, 0)
    If $erfolg == -1 Then
    $erfolg = Suchen($nr, 1)
    EndIf
    If $erfolg == 1 Then
    If $fertig == True Then Return True
    If loesungfinden($nr + 1) == True Then
    Return True
    Else
    loeschen($nr)
    If Suchen($nr, 1) == -1 Then
    loeschen($nr)
    Else
    If loesungfinden($nr + 1) == True Then Return True
    EndIf
    EndIf
    EndIf
    loeschen($nr)
    Return False
    WEnd
    EndFunc ;==>loesungfinden
    loesungfinden(0)

    [/autoit]

    Aber leider funktioniert das nicht, das endet in einer Dauerschleife:

    Vorher werden alle eindeutigen Fälle bereits zugeordnet und gelöscht, diese kommen also im gesammten Array nicht mehr vor.
    Die Funktion suchen(ID, Nr) überprüft erst, ob mitlerweile ein eindeutiger Fall (bei mehreren Fehler) vorliegt und teilt dann entsprechend zu (auch zum anderen, wenn nötig, also zum 1. anstatt 0. wie aufgerufen). Beinem uneindeutigem Fall wird nach dem übergebenen Parameter entschieden.
    Die Funktion löschen(ID) löscht den Eintrag wieder.

    Mir ist die Laufzeit relativ egal, hauptsache die Aufgabe ist gelöst, kann auch ruhig 2 Stunden dauern.


    Ich bin jetzt schon seit Tagen am Rumprobieren, aber irgendwie bekomme ich es nicht hin.

    Es wäre sehr nett, wenn mir da jemand helfen könnte!
    Vielen Dank!

    Einmal editiert, zuletzt von petter2 (16. November 2011 um 17:41)


    Und das sind die vorgegebenen Paare? Immer 2?
    Und niemand soll mehr als die maximale Aufgabenzahl bekommen - also wennich oben die ersten 2 betrachte - AD, ok A macht. A hat damit maximum erreicht, kann also bei AC und AF nicht mehr dran sein?

    Spoiler anzeigen
    [autoit]

    ´#include <Array.au3>
    #include <SQLite.au3>
    #include <SQLite.dll.au3>
    Global $aResult, $iRows, $iColumns, $tmpResult, $tmpiColumns, $tmpiRows
    Global $limits[7][3], $verb[8][4]
    _SQLite_Startup()
    _SQLite_Open()
    _SQLite_Exec(-1, "CREATE TABLE LIMITS (ID INTEGER PRIMARY KEY AUTOINCREMENT, Nutzer VARCHAR(50), Maxlimit VARCHAR(3), Done Varchar(3), Lastchanged VARCHAR(10));")
    _SQLite_Exec(-1, "CREATE TABLE Verbindungen (ID INTEGER PRIMARY KEY AUTOINCREMENT, Nutzer_1 VARCHAR(50),Nutzer_2 VARCHAR(50), ChosenUser VARCHAR(50));")

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

    Testdatacreate()
    Eindeutig()
    While True
    $s = NachEindeutig()
    If IsArray($s) Then
    MsgBox(0, "FEHLER", "Die gegebenen Werte führen zu keiner Lösung.")
    _ArrayDisplay($s)
    ;~ _SQLite_GetTable2d(-1, "SELECT * From LIMITS;", $aResult, $iRows, $iColumns)
    ;~ _ArrayDisplay($aResult)
    ;~ _SQLite_GetTable2d(-1, "SELECT * From Verbindungen;", $aResult, $iRows, $iColumns)
    ;~ _ArrayDisplay($aResult)
    Exit
    ElseIf @error = 2 Then
    MsgBox(0, "FEHLER", "Es gab keinen Startwert, über den geprüft werden konnte.")
    Exit
    ElseIf $s = 2 Then
    MsgBox(0, "ERFOLG", "alles erledigt")
    _SQLite_GetTable2d(-1, "SELECT * From Verbindungen;", $aResult, $iRows, $iColumns)
    _ArrayDisplay($aResult)
    _SQLite_GetTable2d(-1, "SELECT * From LIMITS;", $aResult, $iRows, $iColumns)
    _ArrayDisplay($aResult)
    Exit
    EndIf
    WEnd
    Func Testdatacreate()
    Local $aSql = 'Begin Transaction ;' & @CRLF
    $limits[1][0] = "A"
    $limits[1][1] = "1"
    $limits[2][0] = "B"
    $limits[2][1] = "3"
    $limits[3][0] = "C"
    $limits[3][1] = "1"
    $limits[4][0] = "D"
    $limits[4][1] = "2"
    $limits[5][0] = "E"
    $limits[5][1] = "0"
    $limits[6][0] = "F"
    $limits[6][1] = "0"
    For $i = 1 To 6
    $aSql &= "INSERT INTO LIMITS (Nutzer,Maxlimit,Done,Lastchanged) VALUES ('" & $limits[$i][0] & "', '" & $limits[$i][1] & "', '0', '-1');" & @CRLF
    Next
    $verb[1][0] = "A"
    $verb[1][1] = "B" ;B
    $verb[2][0] = "A"
    $verb[2][1] = "D" ;D
    $verb[3][0] = "A"
    $verb[3][1] = "C" ;C
    $verb[4][0] = "A"
    $verb[4][1] = "F" ;A
    $verb[5][0] = "B"
    $verb[5][1] = "D" ;D
    $verb[6][0] = "B"
    $verb[6][1] = "C" ;B
    $verb[7][0] = "E"
    $verb[7][1] = "D" ;D
    For $i = 1 To 7
    $aSql &= "INSERT INTO Verbindungen (Nutzer_1,Nutzer_2,ChosenUser) VALUES ('" & $verb[$i][0] & "', '" & $verb[$i][1] & "', '');" & @CRLF
    Next
    $aSql &= 'Commit Transaction ;' & @CRLF
    _SQLite_Exec(-1, $aSql)
    EndFunc ;==>Testdatacreate
    Func Eindeutig()
    For $i = 1 To UBound($verb) - 1
    $iRval = _SQLite_GetTable(-1, "SELECT Maxlimit,Done FROM LIMITS WHERE Nutzer = '" & $verb[$i][0] & "';", $aResult, $iRows, $iColumns)
    If $aResult[3] = 0 Or $aResult[3] = $aResult[4] Then
    _SQLite_Exec(-1, "UPDATE Verbindungen SET ChosenUser = '" & $verb[$i][1] & "' WHERE Nutzer_1 = '" & $verb[$i][0] & "' AND Nutzer_2 = '" & $verb[$i][1] & "';")
    _SQLite_Exec(-1, "UPDATE LIMITS SET Done = Done + 1 WHERE Nutzer = '" & $verb[$i][1] & "';")
    EndIf
    $iRval = _SQLite_GetTable(-1, "SELECT Maxlimit,Done FROM LIMITS WHERE Nutzer = '" & $verb[$i][1] & "';", $aResult, $iRows, $iColumns)
    If $aResult[3] = 0 Or $aResult[3] = $aResult[4] Then
    _SQLite_Exec(-1, "UPDATE Verbindungen SET ChosenUser = '" & $verb[$i][0] & "' WHERE Nutzer_1 = '" & $verb[$i][0] & "' AND Nutzer_2 = '" & $verb[$i][1] & "';")
    _SQLite_Exec(-1, "UPDATE LIMITS SET Done = Done + 1 WHERE Nutzer = '" & $verb[$i][0] & "';")
    EndIf
    Next
    EndFunc ;==>Eindeutig
    Func NachEindeutig()
    _SQLite_GetTable(-1, "SELECT ID FROM LIMITS WHERE Done > Maxlimit;", $aResult, $iRows, $iColumns)
    If $iRows > 0 Then
    _SQLite_GetTable2d(-1, "SELECT DISTINCT ChosenUser,Done,Maxlimit FROM Verbindungen INNER JOIN LIMITS ON Verbindungen.ChosenUser = LIMITS.Nutzer WHERE LIMITS.Done > LIMITS.Maxlimit;", $aResult, $iRows, $iColumns)
    Return $aResult
    EndIf
    _SQLite_GetTable(-1, "SELECT ID FROM LIMITS WHERE Done <> Maxlimit;", $aResult, $iRows, $iColumns)
    If $iRows = 0 Then Return 2
    Local $Who
    _SQLite_GetTable(-1, "SELECT Nutzer FROM LIMITS WHERE Maxlimit = Done AND Done != '0'", $aResult, $iRows, $iColumns)
    $Users = $aResult
    If UBound($Users) - 1 < 2 Then Return SetError(2, 0, 0)
    For $k = 2 To UBound($Users) - 1
    _SQLite_GetTable2d(-1, "SELECT Nutzer_1,Nutzer_2,ChosenUser FROM Verbindungen WHERE Nutzer_1 IN (SELECT Nutzer FROM LIMITS WHERE Maxlimit = Done AND Done != '0') AND ChosenUser = '';", $aResult, $iRows, $iColumns)
    $lastarray = $aResult
    For $i = 1 To UBound($lastarray) - 1
    If $lastarray[$i][0] = $Users[$k] Then
    $Who = 1
    Else
    $Who = 0
    EndIf
    _SQLite_Exec(-1, "UPDATE Verbindungen SET ChosenUser = '" & $lastarray[$i][$Who] & "' WHERE Nutzer_1 = '" & $lastarray[$i][0] & "' AND Nutzer_2 = '" & $lastarray[$i][1] & "';")
    _SQLite_Exec(-1, "UPDATE LIMITS SET Done = Done + 1 WHERE Nutzer = '" & $lastarray[$i][$Who] & "';")
    Next
    _SQLite_GetTable2d(-1, "SELECT Nutzer_1,Nutzer_2,ChosenUser FROM Verbindungen WHERE Nutzer_2 IN (SELECT Nutzer FROM LIMITS WHERE Maxlimit = Done AND Done != '0') AND ChosenUser = '';", $aResult, $iRows, $iColumns)
    $lastarray = $aResult
    For $i = 1 To UBound($lastarray) - 1
    If $lastarray[$i][0] = $Users[$k] Then
    $Who = 1
    Else
    $Who = 0
    EndIf
    _SQLite_Exec(-1, "UPDATE Verbindungen SET ChosenUser = '" & $lastarray[$i][$Who] & "' WHERE Nutzer_1 = '" & $lastarray[$i][0] & "' AND Nutzer_2 = '" & $lastarray[$i][1] & "';")
    _SQLite_Exec(-1, "UPDATE LIMITS SET Done = Done + 1 WHERE Nutzer = '" & $lastarray[$i][$Who] & "';")
    Next
    Next
    Return 1
    EndFunc ;==>NachEindeutig

    [/autoit]

    Habe es mit SQLite versucht zu lösen, aber deine Beispielwerte können zu keiner Lösung führen.
    habe die Werte dann etwas angepasst (B-Limit = 3, D-Limit = 2) und so läuft es durch.

    Du musst nur schauen, das deine Daten im selben Format wie bei mir eingelesen werden, dann sollte es klappen

    --EDIT-- Dieser Weg funktioniert nur, wenn mindestens 1 Person Limit = 0 hat und dadurch das Limit eines anderen erreicht wird.

    --EDIT-- Eine Variable ($aSQL) hatte sich verabschiedet, habe die oben jetzt wieder eingefügt

    --EDIT-- Sollte es Probleme beim einelesen in das Format geben oder bei den SQL Befehelen, schreib mich ruhig an ;)

    Alternativer Vorschlag:

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>

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

    ; Anzahl der Einzelvorkommen:
    Global $a_Einz[6][2] = [["A", 1], _
    ["B", 2], _
    ["C", 1], _
    ["D", 3], _
    ["E", 0], _
    ["F", 0]]
    ;Mögliche Kombinationen:
    Global $a_Comb[7][2] = [["A", "B"], _
    ["A", "D"], _
    ["A", "C"], _
    ["A", "F"], _
    ["B", "D"], _
    ["B", "C"], _
    ["E", "D"]]

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

    ;Überführung von $a_Einz in ein Dictionary zum einfacheren Programmieren:
    Global $o_Anz = ObjCreate("Scripting.Dictionary")
    For $i = 0 To UBound($a_Einz) - 1
    $o_Anz($a_Einz[$i][0]) = $a_Einz[$i][1]
    Next

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

    Global $s1, $s2

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

    While UBound($a_Comb) > 0
    CleanEinz($o_Anz, $a_Comb) ; eliminiere nicht vorhandene Einzelvorkommen
    $i_Min = getDictMin($o_Anz) ; kleinstes vorhandenes Vorkommen

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

    For $i = UBound($a_Comb) - 1 To 0 Step -1
    $s1 = $a_Comb[$i][0]
    $s2 = $a_Comb[$i][1]

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

    If ($o_Anz($s1) = 0) And ($o_Anz($s2) = 0) Then
    Exit MsgBox(0, "Fehler", "Fehler - geht nicht auf!")

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

    ElseIf $o_Anz($s1) = $i_Min Then
    ConsoleWrite($a_Comb[$i][0] & "," & $a_Comb[$i][1] & ": " & $s2 & @CRLF)
    $o_Anz($s2) = $o_Anz($s2) - 1
    _ArrayDelete($a_Comb, $i)

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

    ElseIf $o_Anz($s2) = $i_Min Then
    ConsoleWrite($a_Comb[$i][0] & "," & $a_Comb[$i][1] & ": " & $s1 & @CRLF)
    $o_Anz($s1) = $o_Anz($s1) - 1
    _ArrayDelete($a_Comb, $i)
    EndIf
    Next
    WEnd

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

    ;
    Func CleanEinz(ByRef $o_Einz, ByRef $a_Comb)
    For $i In $o_Einz.Keys
    If Not IsInCombs($i, $a_Comb) Then $o_Einz.remove($i)
    Next
    EndFunc ;==>CleanEinz

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

    Func IsInCombs($s_C, ByRef $a_Comb)
    For $i = 0 To UBound($a_Comb) - 1
    If ($a_Comb[$i][0] = $s_C) Or ($a_Comb[$i][1] = $s_C) Then Return True
    Next
    Return False
    EndFunc ;==>IsInCombs

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

    Func getDictMin(ByRef $o_Dic)
    Local $b1 = True, $i
    For $x In $o_Dic.Items
    If $b1 Then
    $i = $x
    $b1 = False
    Else
    If $x < $i Then $i = $x
    EndIf
    Next
    Return $i
    EndFunc ;==>getDictMin

    [/autoit]

    Habe durch AspirinJunkie grade gemerkt, das ein Fehler bei der SQL Variante ist, deine Beispielwerte funktionieren doch, suche grade den Fehler

    Vielen Dank Ihr zwei!
    Leider funktionieren darran aber nicht meine längeren Beispiele, ich habe den Anfang wie folgt verändert:

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

    ; Anzahl der Einzelvorkommen:
    Global $a_Einz[6][2] = [["A", 1], _
    ["B", 2], _
    ["C", 1], _
    ["D", 3], _
    ["E", 0], _
    ["F", 0]]
    ;Mögliche Kombinationen:
    Global $a_Comb[7][2] = [["A", "B"], _
    ["A", "D"], _
    ["A", "C"], _
    ["A", "F"], _
    ["B", "D"], _
    ["B", "C"], _
    ["E", "D"]]
    #ce

    [/autoit]

    Vielen Dank!


    EDIT:
    Mit einem weiteren Test-Beispiel funktioniert es auch nicht... leider......

    [autoit]

    #include <Array.au3>
    ; Anzahl der Einzelvorkommen:
    Global $a_Einz[9][2] = [["A", 2], _
    ["B", 0], _
    ["C", 4], _
    ["D", 1], _
    ["E", 1], _
    ["F", 4], _
    ["G", 0], _
    ["H", 1], _
    ["I", 0]]
    ;Mögliche Kombinationen:
    Global $a_Comb[13][2] = [["A", "B"], _
    ["A", "D"], _
    ["A", "C"], _
    ["C", "E"], _
    ["D", "F"], _
    ["C", "F"], _
    ["H", "I"], _
    ["H", "F"], _
    ["G", "E"], _
    ["F", "G"], _
    ["C", "D"], _
    ["G", "I"], _
    ["E", "F"]]

    [/autoit]

    Schüler A, 2 Aufgaben
    Schüler B, 0 Aufgaben
    Schüler C, 4 Aufgaben
    Schüler D, 1 Aufgaben
    Schüler E, 1 Aufgaben
    Schüler F, 4 Aufgaben
    Schüler G, 0 Aufgaben
    Schüler H, 1 Aufgaben
    Schüler I, 0 Aufgaben
    ---------------------
    Summe = 13 Aufgaben

    Partner:

    AB
    AD
    AC
    CE
    DF
    CF
    HI
    HF
    GE
    FG
    CD
    GI
    EF

    mögliche Lösung:

    AB A
    AD A
    AC C
    CE C
    DF D
    CF C
    HI H
    HF F
    GE E
    FG F
    CD C
    FI F
    EF F

    2 Mal editiert, zuletzt von petter2 (16. November 2011 um 17:37)

    Klar geht das Beispiel nicht - es ist ja auch nicht lösbar.
    Du hast als mögliche Kombination "G-I" angegeben. Sowohl G als auch I haben aber als mögliche Vorkommen 0 - kann also gar nicht funktionieren.
    Ändert man das G in ein F (wie in deiner Lösung) so wird das ganze auch gelöst.

    Zitat von BLinz


    Und das sind die vorgegebenen Paare? Immer 2?
    Und niemand soll mehr als die maximale Aufgabenzahl bekommen - also wennich oben die ersten 2 betrachte - AD, ok A macht. A hat damit maximum erreicht, kann also bei AC und AF nicht mehr dran sein?

    Ja, immer zwei Namen. Ja genau. Mann muss halt eine gültige Kombination finden...
    Vielen Dank!

    Ich hab es mal noch weiter verfeinert aber lösbar ist es für das Skript weiterhin nicht:

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>

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

    #region Dateien einlesen
    Global $s_FileAnz = "cities-small.txt"
    Global $s_FileRelation = "partnerships-small.txt"
    Global $i_n

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

    $a_T = StringRegExp(FileRead($s_FileAnz), '(\d+)\s+"([^"]+)"', 4)
    Global $a_Einz[UBound($a_T)][2]
    $i_n = 0
    For $i In $a_T

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

    $a_Einz[$i_n][0] = $i[2]
    $a_Einz[$i_n][1] = Int($i[1])
    $i_n += 1
    Next

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

    $a_T = StringRegExp(FileRead($s_FileRelation), '"([^"]+)",\s+"([^"]+)"', 4)
    Global $a_Comb[UBound($a_T)][3]
    $i_n = 0
    For $i In $a_T
    $a_Comb[$i_n][0] = $i[1]
    $a_Comb[$i_n][1] = $i[2]
    $i_n += 1
    Next
    $a_T = 0
    #endregion Dateien einlesen

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

    ;Überführung von $a_Einz in ein Dictionary zum einfacheren Programmieren:
    Global $o_Anz = ObjCreate("Scripting.Dictionary")
    For $i = 0 To UBound($a_Einz) - 1
    $o_Anz($a_Einz[$i][0]) = $a_Einz[$i][1]
    Next
    Global $s1, $s2

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

    #region Auf Lösbarkeit hin untersuchen
    Global $i_Sum = 0
    ; Wenn die Summe aller Möglichkeiten kleiner ist als die Anzahl der Kombinationen geht das System nicht auf:
    For $i = 0 To UBound($a_Einz) - 1
    $i_Sum += $a_Einz[$i][1]
    Next
    If $i_Sum < UBound($a_Comb) Then Exit MsgBox(48, "Fehler", "Nicht genügend Möglichkeiten für alle Kombinationen!")

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

    ; Wenn Die zu verteilende Anzahl eines Parameters größer ist als das tatsächliche Vorkommen geht das System nicht auf:
    For $i In $o_Anz.Keys
    If $o_Anz($i) > GetEinzelCount($i, $a_Comb) Then Exit MsgBox(48, "Fehler", $i & " hat mehr Möglichkeiten als überhaupt Vorkommen in den Kombinationen!")
    Next
    #endregion Auf Lösbarkeit hin untersuchen

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

    While UBound($a_Comb) > 0
    CleanEinz($o_Anz, $a_Comb) ; eliminiere nicht vorhandene Einzelvorkommen
    $i_Min = getDictMin($o_Anz) ; kleinstes vorhandenes Vorkommen

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

    #region nach Freiheitsgrad sortieren
    ; Summe der Vorkommen der Kombination bestimmen:
    For $i = 0 To UBound($a_Comb) - 1
    $a_Comb[$i][2] = $o_Anz($a_Comb[$i][0]) + $o_Anz($a_Comb[$i][1])
    Next
    _ArraySort($a_Comb, 0, 0, 0, 2)
    #endregion nach Freiheitsgrad sortieren

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

    For $i = UBound($a_Comb) - 1 To 0 Step -1
    $s1 = $a_Comb[$i][0]
    $s2 = $a_Comb[$i][1]
    $d1 = $o_Anz($s1)
    $d2 = $o_Anz($s2)

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

    If ($d1+$d2 = 0) Then
    ConsoleWrite("########## Fehler bei: " & $s1 & ", " & $s2 & @CRLF)
    Exit MsgBox(48, "Fehler", "Fehler - geht nicht auf!")

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

    ElseIf $d1 = $i_Min Then
    ConsoleWrite($s1 & ", " & $s2 & ": " & $s2 & @CRLF)
    $o_Anz($s2) = $d2 - 1
    _ArrayDelete($a_Comb, $i)
    ExitLoop

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

    ElseIf $d2 = $i_Min Then
    ConsoleWrite($s1 & ", " & $s2 & ": " & $s1 & @CRLF)
    $o_Anz($s1) = $d1 - 1
    _ArrayDelete($a_Comb, $i)
    ExitLoop
    EndIf
    Next
    WEnd

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

    #region Hilfsfunktionen
    Func CleanEinz(ByRef $o_Einz, ByRef $a_Comb)
    For $i In $o_Einz.Keys
    If Not IsInCombs($i, $a_Comb) Then $o_Einz.remove($i)
    Next
    EndFunc ;==>CleanEinz

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

    Func IsInCombs($s_C, ByRef $a_Comb)
    For $i = 0 To UBound($a_Comb) - 1
    If ($a_Comb[$i][0] = $s_C) Or ($a_Comb[$i][1] = $s_C) Then Return True
    Next
    Return False
    EndFunc ;==>IsInCombs

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

    Func getDictMin(ByRef $o_Dic)
    Local $b1 = True, $i
    For $x In $o_Dic.Items
    If $b1 Then
    $i = $x
    $b1 = False
    Else
    If $x < $i Then $i = $x
    EndIf
    Next
    Return $i
    EndFunc ;==>getDictMin

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

    Func getDictMax(ByRef $o_Dic)
    Local $b1 = True, $i = 0
    For $x In $o_Dic.Items
    If $x > $i Then $x = $i
    Next
    Return $i
    EndFunc ;==>getDictMax

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

    Func GetEinzelCount($s_Elem, ByRef $a_Comb)
    Local $i_C = 0
    For $i = 0 To UBound($a_Comb) - 1
    If ($a_Comb[$i][0] = $s_Elem) Or ($a_Comb[$i][1] = $s_Elem) Then $i_C += 1
    Next
    Return $i_C
    EndFunc ;==>GetEinzelCount
    #endregion Hilfsfunktionen

    [/autoit]


    Wie stellst du eigentlich sicher das das System überhaupt lösbar ist?

    Fällt da jemandem der Fehler auf?

    Einmal editiert, zuletzt von petter2 (16. November 2011 um 17:40)

    Ich habe ein ähnliches Problem.
    Folgendes Skript funktioniert auch für die small-Variante:

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>

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

    #region Dateien einlesen
    Global $s_FileAnz = "cities-small.txt"
    Global $s_FileRelation = "partnerships-small.txt"
    Global $i_n

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

    $a_T = StringRegExp(FileRead($s_FileAnz), '(\d+)\s+"([^"]+)"', 4)
    Global $a_Einz[UBound($a_T)][2]
    $i_n = 0
    For $i In $a_T

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

    $a_Einz[$i_n][0] = $i[2]
    $a_Einz[$i_n][1] = Int($i[1])
    $i_n += 1
    Next

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

    $a_T = StringRegExp(FileRead($s_FileRelation), '"([^"]+)",\s+"([^"]+)"', 4)
    Global $a_Comb[UBound($a_T)][3]
    $i_n = 0
    For $i In $a_T
    $a_Comb[$i_n][0] = $i[1]
    $a_Comb[$i_n][1] = $i[2]
    $i_n += 1
    Next
    $a_T = 0
    #endregion Dateien einlesen

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

    If Not CheckCombination($a_Comb, $a_Einz, 0) Then MsgBox(48, "Fehler!", "System nicht lösbar!")

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

    Func CheckCombination(ByRef $a_Comb, $a_Anz, $i, $s_Decr = Default)
    If $s_Decr <> Default Then
    If Not DecrEinz($a_Anz, $s_Decr) Then MsgBox(0,"", $s_Decr)
    EndIf
    Local Const $s1 = $a_Comb[$i][0], $s2 = $a_Comb[$i][1]
    Local Const $d1 = GetAnz($a_Anz, $s1), $d2 = GetAnz($a_Anz, $s2)

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

    If $d1 + $d2 < 1 Then Return False
    ConsoleWrite($i & @CRLF)

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

    If $i = UBound($a_Comb) - 1 Then
    If $d1 > 0 Then Return ConsoleWrite($s1 & ", " & $s2 & " : " & $s1 & @CRLF)
    Return ConsoleWrite($s1 & ", " & $s2 & " : " & $s2 & @CRLF)
    EndIf

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

    ;Versuch auf s1:
    If ($d1 > 0) And CheckCombination($a_Comb, $a_Anz, $i + 1, $s1) Then
    Return ConsoleWrite($s1 & ", " & $s2 & " : " & $s1 & @CRLF)
    ;Versuch auf s2:
    ElseIf CheckCombination($a_Comb, $a_Anz, $i + 1, $s2) Then
    Return ConsoleWrite($s1 & ", " & $s2 & " : " & $s2 & @CRLF)
    EndIf
    Return False
    EndFunc ;==>CheckCombination

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

    #region Hilsfunktionen
    Func DecrEinz(ByRef $a_Einz, Const $s_Key)
    For $i = 0 To UBound($a_Einz) - 1
    If $a_Einz[$i][0] = $s_Key Then
    $a_Einz[$i][1] -= 1
    Return True
    EndIf
    Next
    Return False
    EndFunc ;==>DecrEinz

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

    Func GetAnz(ByRef $a_Einz, Const $s_Key)
    For $i = 0 To UBound($a_Einz) - 1
    If $a_Einz[$i][0] = $s_Key Then Return $a_Einz[$i][1]
    Next
    Return -1
    EndFunc ;==>GetAnz
    #endregion Hilsfunktionen

    [/autoit]

    Bei den großen jedoch bleibt es, wie bei dir, in der Schleife hängen.
    Für mich jedoch völlig unlogisch da ich mir momentan nicht erklären kann wie da überhaupt irgendwas hängen kann.

    Echt merkwürdig...
    Bei mir soll er ja eigentlich immer wieder so weit zurückgehen, bis er einen anderen Weg gehen kann, aber er kommt sozusagen in eine Sackgasse.....

    Hat jemand Ideen?
    Danke.

    hab dran gearbeitet, lasse grade durchlaufen und schaue ob es diesmal klappt ( die große Datei)