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?
Welche Datenstruktur?
Hallo und willkommen im Forum!
Eine (ungetestete) Lösung ohne Nachdenken:
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.
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 Leben ist wie ein Tennisball.
@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:
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()
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
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