问PHP中包含重复字符的数字排列
EN

Stack Overflow用户

提问于 2016-02-24 08:07:10

回答 2查看 355关注 0票数 2

我将一个数字存储在一个字符串中。我的代码将数字打乱成不同的排列。

例如，输入为：

'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);

有人能解释一下为什么和如何修复它吗？

php

回答 2

Stack Overflow用户

发布于 2016-02-24 08: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之类的东西感兴趣。

票数 2

Stack Overflow用户

发布于 2016-02-24 11: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;
}