PHP中包含重复字符的数字排列
PHP中包含重复字符的数字排列
提问于 2016-02-24 16:07:10
我将一个数字存储在一个字符串中。我的代码将数字打乱成不同的排列。
例如，输入为：
'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);有人能解释一下为什么和如何修复它吗？
回答 2
Stack Overflow用户
发布于 2016-02-24 16:35:02
简而言之: while循环的终止条件“是”permutational，而if(!in_array...)测试“是”combinational“。
假设$a=11;：那么$ele_amnt为2，并且当数组$output包含多个元素时，while循环将停止。
随机/内爆代码可以生成字符串<firstelement><seconelement>或<secondelement><firstelement>，这两个字符串都是11。
并且if(!in_array( $justnumber , $output))只允许将其中一个附加到$output。因此count($output)在第一次迭代后将为1，并且将永久保持为1。对于每个具有重复数字的$a都是如此。
shuffle()会随机更改数组中元素的位置。因此，算法的性能取决于....luck ;-)您可能会对https://pear.php.net/package/Math_Combinatorics之类的东西感兴趣。
Stack Overflow用户
发布于 2016-02-24 19:10:13
如果您的输入中有重复的字符，则您的输出数组将包含较少的排列。所以你的循环永远不会完成。
您可以映射您的输入，然后从您的输出映射回来，然后根据您的需要进行过滤：
// 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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35596513
复制相关文章
相似问题
腾讯云开发者
