Search code examples
pythonstringlistalignment

Possible alignments of two lists using Python

I have two strings in two different lists A = [dog bit dog null] and B = [hund bet hund]. I would like to find all possible allignments from list B to list A such as :

  C =  [(hund = dog, bet = bit, hund = dog),
        (hund = dog, bet = bit, hund = bit),
        (hund = dog, bet = bit, hund = null),
        (hund = dog, bet = dog, hund = dog),
        (hund = dog, bet = dog, hund = bit),
        etc.. ]

I think there are 64 different allignments between these two strings. I am working on the IBM model1 for word translastion.

Solution

  • If you want the 64 possibilities, you could use itertools.product:

    >>> from itertools import product
>>> A = "dog bit dog null".split()
>>> B = "hund bet hund".split()
>>> product(A, repeat=3)
<itertools.product object at 0x1148fd500>
>>> len(list(product(A, repeat=3)))
64
>>> list(product(A, repeat=3))[:5]
[('dog', 'dog', 'dog'), ('dog', 'dog', 'bit'), ('dog', 'dog', 'dog'), ('dog', 'dog', 'null'), ('dog', 'bit', 'dog')]

    but note that this is going to generate a fair number of duplicates, given that you have dog twice in A:

    >>> len(set(product(A, repeat=3)))
27

    You could even get the associated triplets of pairs if you wanted:

    >>> trips = [zip(B, p) for p in product(A, repeat=len(B))]
>>> trips[:5]
[[('hund', 'dog'), ('bet', 'dog'), ('hund', 'dog')], [('hund', 'dog'), ('bet', 'dog'), ('hund', 'bit')], [('hund', 'dog'), ('bet', 'dog'), ('hund', 'dog')], [('hund', 'dog'), ('bet', 'dog'), ('hund', 'null')], [('hund', 'dog'), ('bet', 'bit'), ('hund', 'dog')]]