php - 计算字符中的可能性。使用连续重复标准的组合

Question

在 PHP 中，给定

• 最终的字符串长度
• 它可以使用的字符范围
• 可能的最小连续重复次数

如何计算符合这些条件的匹配项数量？
为了画出更好的图景……

$range = array('a','b','c');
$length = 2; // looking for 2 digit results
$minRep = 2; // with >=2 consecutive characters
// aa,bb,cc = 3 possibilities

另一个:

$range = array('a','b','c');
$length = 3; // looking for 3 digit results
$minRep = 2; // with >=2 consecutive characters
// aaa,aab,aac,baa,caa
// bbb,bba,bbc,abb,cbb
// ccc,cca,ccb,acc,bcc
// 5 + 5 + 5 = 15 possibilities
// note that combos like aa,bb,cc are not included
// because their length is smaller than $length

最后一个:

$range = array('a','b','c');
$length = 3; // looking for 3 digit results
$minRep = 3; // with >=3 consecutive characters
// aaa,bbb,ccc = 3 possibilities

所以基本上，在第二个例子中，第三个标准让它捕获了，例如[aa]b 在 aab 中，因为 a 连续重复不止一次，而 [a]b[a] 不会匹配，因为那些 a 是分开的。

不用说，没有一个变量是静态的。

Answer 1

明白了。所有归功于 leonbloy @mathexchange.com .

/* The main function computes the number of words that do NOT contain
 * a character repetition of length $minRep (or more). */
function countStrings($rangeLength, $length, $minRep, &$results = array())
{
  if (!isset($results[$length]))
  {
    $b = 0;

    if ($length < $minRep)
      $b = pow($rangeLength, $length);
    else
    {
      for ($i = 1; $i < $minRep; $i++)
        $b += countStrings($rangeLength, $length - $i, $minRep, $results);
      $b *= $rangeLength - 1;
    }

    $results[$length] = $b;
  }

  return $results[$length];
}

/* This one answers directly the question. */
function printNumStringsRep($rangeLength, $length, $minRep)
{
  $n = (pow($rangeLength, $length) 
            - countStrings($rangeLength, $length, $minRep));
  echo  "Size of alphabet : $rangeLength<br/>"
        . "Size of string : $length<br/>"
        . "Minimal repetition : $minRep<br/>"
        . "<strong>Number of words : $n</strong>";
}

/* Prints :
 * 
   Size of alphabet : 3
   Size of string : 3
   Minimal repetition : 2
   Number of words : 15
 *
 */
printNumStringsRep(3, 3, 2);