Wie generiert man Permutationen mit eindeutigen Werten und vermeidet Duplikate?

Permutationen mit eindeutigen Werten generieren

Permutationen, die mit der Funktion itertools.permutations() generiert werden, behandeln Elemente basierend auf der Position und nicht auf dem Wert als eindeutig. Folglich kann es zu Duplikaten kommen, die sich nur in der Reihenfolge der Elemente mit demselben Wert unterscheiden.

Lösung

Um Duplikate zu vermeiden, sollten Sie den folgenden Ansatz in Betracht ziehen:

1. Verwenden Sie den multiset_permutations()-Iterator der Sympy-Bibliothek, der Werte unabhängig davon explizit als eindeutig behandelt Position.
2. Alternativ können Sie einen nicht iterativen Algorithmus implementieren, der die Häufigkeit jedes einzelnen Werts verfolgt:

def unique_permutations(elements):
    """Generate permutations with unique values."""
    elements = sorted(elements)
    result = []
    counts = {}
    prev_element = None
    for element in elements:
        if element != prev_element:
            counts[element] = 1
        else:
            counts[element] += 1
        result.extend(combine(element, counts))
        prev_element = element
    return result

def combine(element, counts):
    """Combine element with unique counts to form permutations."""
    permutations = []
    if sum(counts.values()) == 1:
        return [tuple([element])]
    for other_element, count in counts.items():
        if element == other_element:
            count -= 1
        permutations.extend([*tuple([element]), *sublist] for sublist in combine(other_element, count))
    return permutations

Beispiel

>>> list(unique_permutations([1, 1, 2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Das obige ist der detaillierte Inhalt vonWie generiert man Permutationen mit eindeutigen Werten und vermeidet Duplikate?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!