我将一个数字存储在字符串中。我的代码将数字改组成不同的排列。
如果输入为:
'123'
然后输出排列将是:
123,132,213,231,321,312
如果输入字符串有重复的数字,我的代码不起作用,并进入无限循环。
不起作用的示例输入:
11,22,33,44,55,455,998,855,111,555,888,222 etc.
我的代码:
<?php
function factorial($n){
if($n==1) return $n;
return $n*factorial($n-1);
}
$a = '1234';
$_a = str_split($a);
$num = count($_a);
$ele_amnt = factorial($num);
$output = array();
while(count($output) < $ele_amnt){
shuffle($_a);
$justnumber = implode('', $_a);
if(!in_array($justnumber , $output))
$output[] = $justnumber;
}
sort($output);
print_r($output);
谁能解释为什么以及如何解决它?
简短版本:while 循环的终止条件"是"排列的,而if(!in_array...)
测试"是"组合的。
假设 $a=11;
: 那么$ele_amnt
2
,当数组$output包含多个元素时,你的 while 循环将停止。
你的洗牌/内爆代码可以产生字符串<firstelement><seconelement>
或<secondelement><firstelement>
,两者都是11
。if(!in_array( $justnumber , $output))
只允许将其中一个附加到$output。因此,count($output) 在第一次迭代后将为 1,并将永久保持 1。对于每个具有重复数字的$a都相同。
shuffle() 随机更改数组中元素的位置。因此,算法的性能取决于....运气;-)您可能对类似 https://pear.php.net/package/Math_Combinatorics 感兴趣。
如果输入中有重复的字符,则输出数组将包含较少的排列。 所以你的循环永远不会完成。
您可以映射输入,然后从输出映射回来,然后根据需要进行筛选:
// For a string '122' we get the permutations of '123' first and then process.
$output = op_code_no_repeats('123');
$filtered = array();
foreach($output as $permutation) {
$filtered[] = str_replace('3', '2', $permutation);
}
$filtered = array_unique($filtered);
var_dump($filtered);
输出:
array (size=3)
0 => string '122' (length=3)
2 => string '212' (length=3)
3 => string '221' (length=3)
您的代码对阶乘和排列函数进行了保护:
function factorial($n)
{
if(! is_int($n) || $n < 1)
throw new Exception('Input must be a positive integer.');
if($n==1)
return $n;
return $n * factorial($n-1);
};
function op_code_no_repeats($a) {
$_a = str_split($a);
if(array_unique($_a) !== $_a)
throw new Exception('Does not work for strings with repeated characters.');
$num = count($_a);
$perms_count = factorial($num);
$output = array();
while(count($output) < $perms_count){
shuffle($_a);
$justnumber = implode('', $_a);
if(!in_array($justnumber , $output))
$output[] = $justnumber;
}
sort($output);
return $output;
}