Создание строк со всеми возможными комбинациями

Question

Я использую алгоритм OCR (основанный на tesseract), который имеет трудности с распознаванием определенных символов. Я частично решил, что, создав свою собственную «хэш-таблицу после обработки», которая включает в себя пары символов. Например, поскольку текст - это просто цифры, я понял, что если в тексте есть символ Q, он должен быть 9.

Однако у меня есть более серьезная проблема с 6 и 8 персонажами, так как оба они распознаются как B. Теперь, когда я знаю, что я ищу (когда я переводил изображение в текст), а строки довольно короткие (6 ~ 8 цифр), я думал создать строки со всеми возможными комбинациями 6 и 8 и сравнить каждый из них их к той, которую я ищу.

Так, например, у меня есть следующие строки, признанную OCR:

L0B7B0B5 

Таким образом, каждый B здесь может быть 6 или 8.

Теперь я хочу, чтобы создать список, как ниже:

L0878085 
L0878065 
L0876085 
L0876065 
. 
. 

Так это вроде бинарной таблицы с 3-х цифр, и в этом случае есть 8 вариантов. Но количество символов B в строке может быть отличным от 3 (это может быть любое число).

Я пытался использовать Python itertools модуль с чем-то вроде этого:

list(itertools.product(*["86"] * 3)) 

Который даст следующий результат:

[('8', '8', '8'), ('8', '8', '6'), ('8', '6', '8'), ('8', '6', '6'), ('6', '8', '8'), ('6', '8', '6'), ('6', '6', '8'), ('6', '6', '6')] 

, который я предполагаю, что я могу потом использовать для замены B символов , Однако по какой-то причине я не могу заставить itertools работать в моей среде. Я предполагаю, что ему есть что-то делать, я использую Jython, а не чистый Python.

Буду рад услышать любые другие идеи о том, как выполнить эту задачу. Может быть, есть более простое решение, о котором я не думал?

Answer 1

itertools.product принимает repeat ключевое слово, которое вы можете использовать:

In [92]: from itertools import product 

In [93]: word = "L0B7B0B5" 

In [94]: subs = product("68", repeat=word.count("B")) 

In [95]: list(subs) 
Out[95]: 
[('6', '6', '6'), 
('6', '6', '8'), 
('6', '8', '6'), 
('6', '8', '8'), 
('8', '6', '6'), 
('8', '6', '8'), 
('8', '8', '6'), 
('8', '8', '8')] 

Тогда один довольно лаконичный метод для замещения следует выполнить операцию сокращения со строкой replace метод:

In [97]: subs = product("68", repeat=word.count("B")) 

In [98]: [reduce(lambda s, c: s.replace('B', c, 1), sub, word) for sub in subs] 
Out[98]: 
['L0676065', 
'L0676085', 
'L0678065', 
'L0678085', 
'L0876065', 
'L0876085', 
'L0878065', 
'L0878085'] 

Другой метод, использующий пару дополнительных функций из itertools:

In [90]: from itertools import chain, izip_longest 

In [91]: subs = product("68", repeat=word.count("B")) 

In [92]: [''.join(chain(*izip_longest(word.split('B'), sub, fillvalue=''))) for sub in subs] 
Out[92]: 
['L0676065', 
'L0676085', 
'L0678065', 
'L0678085', 
'L0876065', 
'L0876085', 
'L0878065', 
'L0878085'] 

Answer 2

Здесь простая рекурсивная функция для генерации ваших строк: - (Это псевдокод)

permut(char[] original,char buff[],int i) { 


if(i<original.length) { 

     if(original[i]=='B') { 

      buff[i] = '6' 
      permut(original,buff,i+1) 
      buff[i] = '8' 
      permut(original,buff,i+1) 
     } 

    else if(original[i]=='Q') { 

      buff[i] = '9' 
      permut(original,buff,i+1) 
     } 

     else { 

      buff[i] = ch[i]; 
      permut(original,buff,i+1) 
     } 
} 

else { 

     store buff[]  

    } 


}