首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >PHP中包含重复字符的数字排列

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

Stack Overflow用户
提问于 2016-02-24 16:07:10
回答 2查看 355关注 0票数 2

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

例如,输入为:

代码语言:javascript
代码运行次数:0
运行
复制
'123'

那么输出排列将是:

代码语言:javascript
代码运行次数:0
运行
复制
123,132,213,231,321,312

如果输入的字符串有重复的数字,我的代码就无法工作,并进入无限循环。

不起作用的示例输入:

代码语言:javascript
代码运行次数:0
运行
复制
11,22,33,44,55,455,998,855,111,555,888,222 etc.

我的代码:

代码语言:javascript
代码运行次数:0
运行
复制
<?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);

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

EN

回答 2

Stack Overflow用户

发布于 2016-02-24 16:35:02

简而言之: while循环的终止条件“是”permutational,而if(!in_array...)测试“是”combinational“。

假设$a=11;:那么$ele_amnt2,并且当数组$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
EN

Stack Overflow用户

发布于 2016-02-24 19:10:13

如果您的输入中有重复的字符,则您的输出数组将包含较少的排列。所以你的循环永远不会完成。

您可以映射您的输入,然后从您的输出映射回来,然后根据您的需要进行过滤:

代码语言:javascript
代码运行次数:0
运行
复制
// 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);

输出:

代码语言:javascript
代码运行次数:0
运行
复制
array (size=3)
  0 => string '122' (length=3)
  2 => string '212' (length=3)
  3 => string '221' (length=3)

你的代码在阶乘和置换函数上有保护:

代码语言:javascript
代码运行次数:0
运行
复制
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;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/35596513

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档