Блог

Вот немного контекста, чтобы упростить понимание проблемы:

• У меня есть некоторый текст, прочитанный OCR, с оценкой достоверности, привязанной к каждому прочитанному символу ( [['0', 0.99], ['1', 0.20]] )
• У меня есть карта некоторых похожих символов ( '0': ['O'] , '1': ['l', 'I'] )

Я пытаюсь получить все возможные похожие комбинации, отсортированные по вероятности (например 0 , достаточно уверен, 1 нет, поэтому я хочу начать с 1 ). В итоге я получаю следующую структуру (уже отсортированную по наименьшему баллу, и у меня есть способ восстановить порядок исходной строки после):

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

Теперь мне трудно понять, как получить все комбинации в этом конкретном порядке:

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

Или другой пример, этот:

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

Приведет к этому:

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

Любой псевдокод, который решил бы это? Спасибо за вашу помощь!

То, что вы ищете, — это декартово произведение. В зависимости от используемого вами языка, возможно, лучше всего использовать библиотеку (например, Python itertools.product ), или вы можете реализовать ее самостоятельно.

Для возможной реализации обратите внимание, что мы можем вычислить декартово произведение слева направо (или справа налево, поскольку оно ассоциативно). Поэтому мы можем итеративно умножать первые два массива, пока не останется только один.

 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