回溯算法,创建所有可能的(不同字母)固定长度的单词


Backtracking algorithm to create all possible (distinct letters) words with fixed length?

我有英文字母表"ABCDEFGHIJKLMNOPQRSTUVWZYX"中所有可能的BIG字母作为字符集。我想从这个集合中创建所有可能的组合——所有"单词",固定长度为8,字母不同。

单词示例:

ABCDEFGH

PQELFKMB

XLOPQDEH

我尝试过的算法(在stackoverflow上找到,但不再有链接)是这样的:

<?php
function getPermCount($letters, $count)
{
  $result = 1;
  // k characters from a set of n has n!/(n-k)! possible combinations
  for($i = strlen($letters) - $count + 1; $i <= strlen($letters); $i++) {
    $result *= $i;
  }
  return $result;
}
// Decodes $index to a $count-length string from $letters, no repeat chars.
function getPerm($letters, $count, $index)
{
  $result = '';
  for($i = 0; $i < $count; $i++)
  {
    $pos = $index % strlen($letters);
    $result .= $letters[$pos];
    $index = ($index-$pos)/strlen($letters);
    $letters = substr($letters, 0, $pos) . substr($letters, $pos+1);
  }
  return $result;
}
$letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
echo '2 letters from 4:<br>';
for($i = 0; $i < getPermCount($letters, 3); $i++)
  echo getPerm($letters, 3, $i).'<br>';
?>

从我所看到的情况来看,如果我尝试使用3个字母,效果会很好。但长度为8,我有450万种可能性。我已经检查了结果,但在最后3个字母中没有看到Q。

我试着找到一个随机的"单词":MBFHPXSN而且在列表中找不到它。所以并非所有的可能性都存在。

PS:我得到了wget的所有"单词",所以php给我的所有东西都应该在文件中。

你们还有其他解决方案吗?

代码在php中,但几乎可以在任何东西中,c#、python、java

450万个组合还远远不能解决这个问题。我想PHP在内存耗尽之前就已经用完了。

26*25*24*23*22*21*20*19可能的8个字母的单词,您可以从ASCII大写字母构建而不重复。这是62.990.928.000单词。即使你可以紧凑地存储它们,每个字只使用8个字节,而且没有开销,这意味着你需要大约469 GB的RAM。我怀疑你有那么多。。。

如果只想生成8个字母的单词,那么迭代解决方案可能有8个嵌套循环
最外层的循环索引循环从1到26。
每个连续的索引循环形成prev_index+1到26。

这样内存就不会被过度使用。