Welche Datenstruktur?

[serend2]

Hallo zusammen,

ich hab folgendes Problem innerhalb eines Projektes:

Gegeben sei diese Datenstruktur, das jeweils erste Wort stellt das ursprüngliche Wort dar, die nachfolgenden sind verwechselbare Wörter:
[['you'], ['know', 'nye', 'knee'], ['one', 'wen', 'when', 'win'], ['of','if'], ['the', 'zhou'], ['intense'], ['pleasures']]

Gesucht: eine gute Datenstruktur, mit der alle Pfade generiert werden können, die durch den Satz vom Anfang bis Ende jeweils drei Abweichungen vom Original enthalten.

Beispiele: You nye wen of zhou intense pleasures.
Oder: You know wen if zhou intense pleasures.

Ideen?

(Bäume? Automaten? Fertige Module vorhanden dafür?)

EDIT: eine Lösung ist itertools.product - allerdings werden dort alle Möglichkeiten generiert und müssen nachträglich gelöscht werden -> senkt die Performanz

Wer hat bessere Lösungen?

[EyDu]

Hallo und willkommen im Forum!

Eine (ungetestete) Lösung ohne Nachdenken:

Code: Alles auswählen

import itertools
import operator

def difference(first, other):
    return sum(x != y for (x, y) in zip(first, other))

if __name__ == "__main__":
    WORDS = [['you'], ['know', 'nye', 'knee'], ['one', 'wen', 'when', 'win'], ['of','if'], ['the', 'zhou'], ['intense'], ['pleasures']]

    first = map(operator.itemgetter(0), WORDS)
    print filter(lambda ws: difference(first, ws) == 3, itertools.product(*WORDS))

Das ist allerdings nicht besonders effizient. An sich schreit das Problem nach Rekursion. Wenn du das itertools-Modul vernünftig einsetzt und nicht blind alle Kombinationen berechnest, dann geht das noch etwas schöner.

[BlackJack]

@serend2: Man kann sich mit `itertools.combinations()` alle 3-elementigen Kombinationen von den Wörtern die verwechselbar sind ermitteln, und dann von denen jeweils mit `itertools.product()` alle Varianten erzeugen.

Edit:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
from itertools import combinations, product


def iter_deviations(sentence, max_deviations):
    ambigous_indices = [i for i, ws in enumerate(sentence) if len(ws) > 1]
    if len(ambigous_indices) < max_deviations:
        for result in product(*sentence):
            yield result
    else:
        for indices in combinations(ambigous_indices, max_deviations):
            indices = set(indices)
            new_sentence = list(sentence)
            for i in ambigous_indices:
                if i in indices:
                    new_sentence[i] = new_sentence[i][1:]
                else:
                    new_sentence[i] = [new_sentence[i][0]]
            for result in product(*new_sentence):
                yield result


def main():
    sentence = [
        ['you'],
        ['know', 'nye', 'knee'],
        ['one', 'wen', 'when', 'win'],
        ['of', 'if'],
        ['the', 'zhou'],
        ['intense'],
        ['pleasures'],
    ]
    for result in iter_deviations(sentence, 3):
        print(' '.join(result))


if __name__ == '__main__':
    main()

[serend2]

Danke für eure Lösungen
Prima und so schnell.

Ich nutze jetzt deine Lösung BlackJack, weil sie so wunderbar schnell ist.

Was ich aber noch nicht verstehe: Bei Sätzen, die weniger confusions als die max_deviations enthalten, z.B.
sentence = [['you'],['know'],['one'], ['of'],['the', 'zhou'], ['intense'],['pleasures']]

Wird der Ausgangssatz auch als confusion generiert?
Stehe da voll auf dem Schlauch. Könnte das nachträglich einfach abfangen, wäre aber eine unschöne Lösung.

LG