创建包含所有可能组合的字符串

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有关。

如果有其他完成此任务的想法，我将非常乐意听取。也许还有更简单的解决方案我没有考虑到？

- Eugene S

---

我不使用Jython，但据说itertools应该可以工作。关于这个问题有什么疑问吗？ - Veedrac

这听起来就像是 itertools.product 的用途。与其手动解决问题，不如尝试让 itertools 在你的环境中发挥作用。 - Jinghao Shi

如果出于某些原因您无法直接使用itertools.product，则可以轻松地复制并粘贴纯Python中的参考实现。它将使用更多的内存，但通常这不是瓶颈。 - DSM

@DSM 谢谢！我刚刚自己搞定了这个问题！ :) - Eugene S

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']

- Warren Weckesser

---

你使用reduce的想法非常好，真的很有帮助。非常感谢！ - Eugene S

最终，我只是直接从itertools.product的参考实现中复制了它，并使用了提出的“reduce”思路来解决这个问题。再次感谢！ - Eugene S

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[]     

  }


}

- Vikram Bhat

---

这是 Python 吗？还是 C？ - K DawG