algorithm - How to get all combinations of arbitrary number of arrays of arbitrary length with specific order

Question

Here's a bit of context, to make the problem easier to understand:

• I have some text read by OCR, with a confidence score attached to each character read ([['0', 0.99], ['1', 0.20]])
• I have a map of some lookalike characters ('0': ['O'], '1': ['l', 'I'])

I am trying to get all the lookalike combinations possible, sorted by probability (e.g. 0 is fairly sure, 1 is not, so I want to start with the 1). I end up with the following structure (already sorted by lowest score, and I have a way to restore the order of the original string after):

[
  [ '1', 'l', 'I' ],
  [ '0', 'O' ],
]

Now, I have a hard time figuring out how to get all combinations in this specific order:

[
  ['1', '0'],
  ['l', '0'],
  ['I', '0'],
  ['1', 'O'],
  ['l', 'O'],
  ['I', 'O'],
]

Or another sample, this:

[
  [ '0', 'O' ],
  [ '2', 'Z' ],
  [ '5', 'S' ],
]

Would lead to this:

[
  [ '0', '2', '5' ],
  [ 'O', '2', '5' ],
  [ '0', 'Z', '5' ],
  [ 'O', 'Z', '5' ],
  [ '0', '2', 'S' ],
  [ 'O', '2', 'S' ],
  [ '0', 'Z', 'S' ],
  [ 'O', 'Z', 'S' ],
]

Any pseudo-code that would solve this? Thanks for your help!

Answer 1

What you're looking for is the Cartesian product. Depending on the language you use, it may be best to use a library (such as Python's itertools.product), or you could implement it yourself.

For a possible implementation, note that we can compute the Cartesian product left-to-right (or right to left, as it is associative). We can therefore iteratively multiply the first two arrays, until only a single one is left.

function Cartesian(arrays):
    while length(arrays) > 1
        multiplied = multiply(arrays.pop(), arrays.pop())
        arrays.add(multiplied)
    return arrays[0]

function multiply(a1, a2):
    result = []
    for e1 in a1
        for e2 in a2
            result.add(e1 + a1)
    return result