3

在 PHP 中，给定

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

您如何计算符合这些条件的匹配数？
为了画出更好的画面……</p> 

$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

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

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

4

3 回答 3

1

我认为最好用数学来处理这个问题。

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

$rangeLength = count($range);
$count = (pow($rangeLength,$length-$minRep+1) * ($length-$minRep+1)) - ($rangeLength * ($length-$minRep)); // is the result

现在， $count 在三种情况下得到了真实的结果。但它可能不是通用公式，需要改进。

试着解释一下：

pow($rangeLength,$length-$minRep+1)

在此，我们将重复字符视为一个。例如，在您给出的第二个示例中，我们认为在 aab 中，aa 是一个字符。因为，两个字符需要一起改变。我们认为现在有两个像 xy 这样的字符。因此，字符 a、b 和 c 的可能性相同，即 3 ($rangeLength) 两个字符的可能值 ($length-$minRep+1)。所以 3^2=9 是第二个例子的可能情况。

我们计算出 9 仅代表 xy 而不是 yx。为此，我们乘以 xy 的长度 ($length-$minRep+1)。然后我们有 18 个。

看起来我们计算了结果，但我们的计算中有重复。我们没有考虑到这种情况：xy => aaa 和 yx => aaa。为此，我们计算并减去重复的结果

- ($rangeLength * ($length-$minRep))

所以在这之后，我们得到了结果。正如我在描述开始时所说的那样，这个公式可能需要改进。

于 2012-08-21T00:02:40.047 回答
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);
于 2012-08-22T10:11:17.440 回答
0

有了数学，工作变得非常复杂。但是，总有一种方法，甚至不如数学那么漂亮。我们可以使用 php 创建所有可能的字符串，并使用正则表达式控制它们，如下所示：

$range = array('a','b','c');
$length = 3; 
$minRep = 2; 

$rangeLength = count($range);

$createdStrings = array();
$matchedStrings = array();

function calcIndex(){
    global $range;
    global $length;
    global $rangeLength;

    static $ret;

    $addTrigger = false;

    // initial values
    if(is_null($ret)){ 
        $ret = array_fill(0, $length, 0);
        return $ret;
    }

    for($i=$length-1;$i>=0;$i--){
        if($ret[$i] == ($rangeLength-1)) {
            if($i==0) return false;
            $ret[$i] = 0;
        }
        else {
            $ret[$i]++;
            break;
        }
    }

    return $ret;
}

function createPattern()
{
    global $minRep;
    $patt = '/(.)\\1{'.($minRep-1).'}/';
    return $patt;
}

$pattern = createPattern();


while(1) 
{
    $index = calcIndex();
    if($index === false) break;

    $string = '';
    for($i=0;$i<$length;$i++)
    {
        $string .= $range[$index[$i]];
    }

    if(!in_array($string, $createdStrings)){ 
        $createdStrings[] = $string;
        if(preg_match($pattern, $string)){
            $matchedStrings[] = $string;
        }
    }
}

echo count($createdStrings).' is created:';
var_dump($createdStrings);

echo count($matchedStrings).'strings is matched:';
var_dump($matchedStrings);
于 2012-08-21T15:44:54.363 回答