[C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
DerAlbi
Establishment
Beiträge: 269
Registriert: 20.05.2011, 05:37

[C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von DerAlbi »

Ja, ähm, der Titel... besser ein Beispiel, oder?

Gegeben:

Code: Alles auswählen

Liste[0] = [0, 4, 5]
Liste[1] = [4, 5]
Liste[2] = [0]
Liste[3]= [5, 9]
Ich muss aus jeder Liste exakt ein Element auswählen, sodass in der resultierenden Liste kein doppelter Eintrag drin ist.
Ein mögliches Ergebnis ohne Kollisionen ist hier z.B:

Code: Alles auswählen

[4@0, 5@1, 0@2, 9@3] oder [5@0, 4@1, 0@2, 9@3]
Weiß jemand, wie man das algorithmisch löst, oder wie man hier nach einem effizienten Algorithmus googelt?
Der Mist ist, dass das lösen einer Kollision zu anderen Kollisionen führen kann.
Man könnte:
1) zwingende Lösungen zu erst populieren hier die [0@2]
2) dann aus auswählbaren Lösungen die einzigartigen populieren, also die, die garantiert keine doppelungen haben oder erzeugen. Hier die [9@3]
3) und dann den Rest durchzählen im sinne von "eine Nummer erzeugen, in der jede stelle für den Index in der Original-Liste steht"
übrig bleibt die Liste[0] mit [4,5] und Liste[1] mit [4,5] und da braucht Index "01" um die 4@0 der einen und die 5@1 der anderen Liste zu erwählen.
3.1) Das durchzählen ist aber sicher langsam, daher verändert man der Reihe nach nur die Indices mit Doppelungen. Dafür muss man aber jedes mal Doppelungen feststellen - muss man aber so oder so, weil man muss ja die Validität der Lösung prüfen..
Ich weiß aber nicht, ob sowas in einer garantierten Lösung endet, oder wie effizient das ist.

Fun-Fact: es geht nicht um Integers, sondern um Typen und das ganze wird constexpr-template-magic im Kontext eines variadischen Templates. Die Listen sind tuple usw. Das ganze ist also in einem Header und sollte das compilieren nicht all zu sehr aufhalten. Spaß! Es wird niemals mehr als 16 listen geben und die Listen sind zwischen 1..4 Elementen lang.

Gibts für solche Probleme irgendwelche schlauen Baumstrukturen oder sowas?
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von Jonathan »

Uff, das mit den Templates ist eine Sache, erstmal ist ja die Frage, was ein effizienter Algorithmus dafür ist. Klingt interessant, aber so auf die schnelle fällt mir nicht ein, zu welchem längst effizient gelösten Problem deines äquivalent ist.

Aber ich hab neulich ein Video gesehen mit einem Problem das ganz ehrlich klang. "Finde 5 Wörter mit jeweils 5 Buchstaben so dass insgesamt 25 verschiedene Buchstaben verwendet werden". Schau vlt. mal rein:

https://www.youtube.com/watch?v=c33AZBnRHks

Es ist bei genauerer Betrachtung wohl nicht ganz das selbe, die benutzten z.B. als Eingabe eine Liste legaler englischer Wörter. Aber vielleicht hilft es ja trotzdem weiter.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von NytroX »

Im Prinzip ist das, was versucht wird, so ähnlich wie ein Parser arbeitet.
Man hat ja im Prinzip einen Baum, von dem es dann mehrere Möglichkeiten gibt.

Bei ~16 Listen mit ~4 Einträgen kann man denke ich 2 Wege gehen:

1. Eine Art Wavefunction Collapse:
Man eliminiert ungültige Möglichkeiten nach und nach aus den Listen, und landet dann bei x Elemente pro Liste, aus der man sich frei bedienen kann. Wenn dann eine Liste keine Elemente mehr hat, ist keine Lösung möglich.
Vermutlich lohnt es sich hier mit der längsten Liste anzufangen, oder das in Tabellenform zu machen.

2. Vorgehen wie bei einem GLR-Parser:
Man probiert frei alles durch. Bei jeder Möglichkeit "spawned" man quasi einen neuen logischen Strang/Fiber, der dann versucht die Liste zu füllen. Wenn sich der Strang in Widersprüche verwickelt, "stirbt" er.
Dann sind am Ende entweder alle Möglichkeiten/Stränge weg, oder der erste Strang mit gültiger Lösung ist das Ergebnis.
Vermutlich lohnt es sich hier, mit der kürzesten Liste anzufangen, weil man dann weniger wahrscheinlich "Backtracken" muss.

Bei Template-Magic bin ich aber raus, besonders mit dem limitierten constexpr/consteval von C++.
DerAlbi
Establishment
Beiträge: 269
Registriert: 20.05.2011, 05:37

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von DerAlbi »

@ Jonatan: das Video habe ich sogar gekannt, aber ich denke nicht, dass ich die Lösungen dort sinnvoll verstehe :-D Zumal die die Natur der Daten stark ausnutzen und mit SIMD und Multithreading anfangen. (habe ein paar der schnellen Lösungen angeschaut und z.B. die Parallelisierbarkeit des Algorithmus' ist mir ja egal)

@ NytroX: ich habe mich mal an das gesetzt, was du mit "Wavefunction Collapse" meinst und es deshalb auch so genannt. Ich weiß nicht exakt, warum es funktioniert, aber ich finde keinen Testfall, der keine Lösung findet, außer wenn ich auch keine finden würde. Ich habe das erst mal in Python hingeschmissen. Ich schaue mal, ob ich das nach C++ bekomme.

Code: Alles auswählen

from typing import List, Tuple, Dict

Alternatives: List[List[int]] = [ [4, 5],
                                  [4, 5, 7, 0],
                                  [0],
                                  [4, 7, 9],
                                  [4, 7, 8],
                                  [0, 6],
                                  [6, 5, 4, 7, 8]]

Solution: List[Tuple[int, int]] = []


def buildDict(inp: List[List[int]]) -> Dict[int, List[Tuple[int, int]]]:
    retval = {}
    for i in range(len(inp)):
        for j in range(len(inp[i])):
            if inp[i][j] in retval:
                retval[inp[i][j]].append( (i, j) )
            else:
                retval[inp[i][j]] = [ (i, j) ]
    return retval


def removeValue(inp: List[List[int]], value) -> List[List[int]]:
    for i in range(len(inp)):
        inp[i] = [e for e in inp[i] if e != value]
    return inp


def findForcedSolutions(inp: List[List[int]]):
    i = 0
    while i < len(inp):
        if len(inp[i]) == 1:
            print("Found forced solution: Entry \"" + str(inp[i][0]) + "\" in List", i)
            Solution.append( (i, inp[i][0]) )
            inp = removeValue(inp, inp[i][0])
            i = 0
        else:
            i = i + 1
    return inp


def findUniqueSolutions(inp: List[List[int]]):
    rebuildDict = True
    while rebuildDict:
        rebuildDict = False
        dictionary = buildDict(inp)
        for key in dictionary:
            if len(dictionary[key]) == 1:
                ListIndex = dictionary[key][0][0]
                EntryIndex = dictionary[key][0][1]
                value = inp[ListIndex][EntryIndex]
                print("Found unique solution: Entry \"" + str(value) + "\" in List", ListIndex)
                Solution.append( (ListIndex, value) )
                inp[ListIndex] = []
                rebuildDict = True
                break
    return inp

def getSmallestImpactValue(inp: List[List[int]]):
    dictionary = buildDict(inp)
    if len(dictionary) == 0:
        return -1
    fom = {}
    # fom = "sum of length of all alterative-arrays that contain a certain value"
    # Example [ [0, 1, 2], [0, 4, 5], [1, 2] ]
    #  -> gives fom=3+3=6 for value 0,
    #  ->       fom=3+2=5 for value 1
    #           fom=3 for value 4
    # Finding the value that generates the smallest figure of merit
    # will solve for values with the least alternatives 'alternatives destroyed'
    # first
    for key in dictionary:
        fom[key] = sum([len(inp[k[0]]) for k in dictionary[key]])
    return sorted(fom.items(), key=lambda x: x[1])[0][0]


def solveForSmallesListContaining(inp: List[List[int]], val: int):
    smallestListIndex = len(inp)
    smallestListLength = 10000
    for i in range(len(inp)):
        if val in inp[i]:
            if len(inp) < smallestListLength:
                smallestListLength = len(inp)
                smallestListIndex = i
    print("Disambiguate solution: Entry \"" + str(val) + "\" in List", smallestListIndex)
    Solution.append( (smallestListIndex, val))
    inp[smallestListIndex] = []
    inp = removeValue(inp, val)
    return inp


def collapse(inp: List[List[int]]):
    inp = findUniqueSolutions(inp)
    while True:
        inp = findForcedSolutions(inp)
        largestImpactValue = getSmallestImpactValue(inp)
        if largestImpactValue < 0:
            break
        inp = solveForSmallesListContaining(inp, largestImpactValue)


collapse(Alternatives.copy())
if len(Solution) == len(Alternatives):
    print("\nSolution:")
else:
    print("\nWARNING: Partial solution:")
for s in sorted(Solution, key=lambda s:s[0]):
    print("From List " + str(s[0]) + ": \"" + str(s[1]) + "\" from ", Alternatives[s[0]])

valuesTaken = [s[0] for s in Solution]

print("")
if len(valuesTaken) == len(dict.fromkeys(valuesTaken)):
    print("=> Values are unique :-)")
else:
    print("=> noooohohoho :-(")
ergibt:

Code: Alles auswählen

Found unique solution: Entry "9" in List 3
Found forced solution: Entry "0" in List 2
Found forced solution: Entry "6" in List 5
Disambiguate solution: Entry "8" in List 4
Disambiguate solution: Entry "7" in List 1
Disambiguate solution: Entry "4" in List 0
Found forced solution: Entry "5" in List 6

Solution:
From List 0: "4" from  [4, 5]
From List 1: "7" from  [4, 5, 7, 0]
From List 2: "0" from  [0]
From List 3: "9" from  [4, 7, 9]
From List 4: "8" from  [4, 7, 8]
From List 5: "6" from  [0, 6]
From List 6: "5" from  [6, 5, 4, 7, 8]

=> Values are unique :-)
Im Prinzip führe ich in collapse() zuerst ein Quick-Solve aus: alle Werte, die nur 1x auftreten, können bedenkenlos als Lösung genommen werden, da die der Lösung niemals doppelt hinzugefügt werden können. Danach bleiben nur komplizierte fälle übrig.
Dann wird eine Schleife ausgeführt:
1) die forcierten Lösungen akzeptieren
-> diese Lösungsmöglichkeit wird dann überall gelöscht, wo die noch mit anderen Alternativen zusammen auftritt, um Dopplungen zu vermeiden
-> wenn durch das Löschen von Lösungsmöglichkeiten noch mehr forcierte Lösungen auftauchen, werden die gleich mit gelöst.
2) Es bleiben nur Alternativen-Listen zurück, die weder forciert, noch einzigartige Lösungen enthalten. Diese Situation löse ich mit einer Bewertungsfunktion: ich schaue quasi, "angenommen man würde Wert X als Lösung akzeptieren, wie groß ist die Summe der Länge aller Alternativlisten, in denen X auftaucht?"
Von dieser Bewertungsfunktion nehme ich dann das X, dass das Minimum erzeugt. Dann suche ich die kürzeste Alternativen-Liste, die X enthält und lege dort X als Lösung fest. Das ist dann der Kollaps der Alternativen. Es wird also immer die Lösung genommen, die am wenigsten Alternativen hat und auch die wenigsten Alternativen zerstört.
Natürlich wird auch hier wieder die Lösung aus allen anderen Alternativlisten gelöscht, sodass eventuell wieder Alternativlisten entstehen, die forcierte Lösungen haben.

Wenn jemand damit spielen will und eine Alternativliste konstruieren kann, bei der keine vollständige Lösungen gefunden wird, obwohl eine existiert, oder wo die Lösung nicht einzigartig ist, her damit.
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von dot »

Ich fühle hier sehr starke xy problem vibes…

Ich würde vorschlagen, dass du uns mal erklärst, was genau du mit der Lösung dieses Problems zu erreichen erhoffst.
DerAlbi
Establishment
Beiträge: 269
Registriert: 20.05.2011, 05:37

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von DerAlbi »

Es handelt sich um die statische Resourcenverteilung einer DMA in einem Mikrocontroller. Es gibt 2 DMAs die jeweils 8 Kanäle haben. Jeder dieser Kanäle ist auswählbar mit verschiedenen Peripherien (Timer, Serielle Kommunikation (RX/TX) usw) verbunden (aber nicht alle Peripherien sind überall). Manche Peripherieverbindungen sind einzigartig nur an einem bestimmten DMA-Kanal zu finden, andere sind doppelt oder 3x redundant auf verschiedenen DMA-Kanälen zu auswählbar.
Mein Ziel ist es eine Compile-Time-Sichere Verteilung der DMA-Kanäle zu erreichen.

Jede Peripherie kennt ihre möglichen DMA-Verbindungen. Zum Schluss möchte ich folgendes Schreiben können:

Code: Alles auswählen

using DMAConnectionManager = DMAConnectionManagerTemplate<RegisterPeriphery<DMADirection::RX, SPI0>,
                                                          RegisterPeriphery<DMADirection::TX, SPI0>,
                                                          RegisterPeriphery<DMADirection::RX, SPI1>,
                                                          RegisterPeriphery<DMADirection::TX, SPI1>,
                                                          RegisterPeriphery<DMADirection::RX, SPI2>,
                                                          RegisterPeriphery<DMADirection::TX, SPI2> >;
                                                          
using SPI0_DMAChannelRX = DMAConnectionManager::RXDMAChannelFor<SPI0>;
...
Ich möchte damit vermeiden, dass man Resourcen manuell (fehl-)verteilt oder sich auf manuelle Verteilung verlässt und damit Code schreibt, der aufgrund von Faulheit auf Magic-Values basiert. Bei einer Hardware-Revision soll man zum Schluss einfach nur die Peripherie-Nummer ändern können und alles soll sich selbst regeln. Also andere DMA-Kanäle usw. Damit wird der Code portierbar, teilweise sogar über Mikrocontroller hinweg.
StephanT
Beiträge: 23
Registriert: 04.07.2021, 11:30

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von StephanT »

Ich habe leider nicht viel Zeit, aber könnte das nicht helfen?

https://en.wikipedia.org/wiki/Hungarian_algorithm
DerAlbi
Establishment
Beiträge: 269
Registriert: 20.05.2011, 05:37

Re: [C++] Befülle eine Liste mit einzigartigen Elementen aus einer Liste von Alternativen

Beitrag von DerAlbi »

Ich glaube dabei geht es um numerische Optimierung, nicht um die zwanghafte Auswahl von Items aus einer Liste von Alternativen ohne Doppelungen in der Endauswahl. Nah dran und definitiv verwandt, aber nicht identisch.

Zum Schluss muss ich jetzt auch sagen, dass ich das ganze erfolgreich nach C++ auf Typ-Basis portiert habe. 180 Zeilen constexpr-Code (doppelt so viel Code im Vergleich zu Python). Ich rechne dabei mit den Hashes der Typnamen und konvertiere dann die Hashes wieder zu Typen. Damit war der Kernalgorithmus fast direkt von Python übernehmbar, bis auf, dass std::map (als Python-dicts-Ersatz) nicht constexpr-tauglich ist.
Trotzdem muss dot sich keine Gedanken mehr über "enormous amounts of wasted time and energy" gedanken machen. :-) Für das, was es leistet und die Fehler die es verhindert, waren 2 Abende gut investierte Zeit.

Ich glaube auch, dass die Performance stimmt. Es wird pro Iteration mindestens eine Lösung gefunden, meist mehr. In der Praxis ist es hoffentlich so, dass der statistisch größte Teil durch die Vorbehandlung einzigartiger Lösungen erschlagen wird; dann erst die erzwungenen Lösungen und das kollabieren der Mehrdeutigkeiten. Das ist in echtem Code vermutlich selten.

Spannend wäre, warum eine Bewertungsfunktion und das Kollabieren der jeweils kürzesten Alternativliste so absonderlich effizient ist. Das war wortwörtlich der erste Versuch.

Danke an NytroX für den Namen dafür!
Danke auch an alle andere für den Input.
Antworten