Number permutations in PHP with repeated characters

Question

I store a number in a string. My code shuffles the digits into different permutations.

Example if the input is:

'123'

then the output permutations will be:

123,132,213,231,321,312

If the input string has repeated digits, my code does not work, and goes into an infinite loop.

Example inputs that don't work:

11,22,33,44,55,455,998,855,111,555,888,222 etc.

My code:

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

Can anyone explain why and how to fix it?

Please don't tag questions with [tag:c] when they have nothing to do with it. — Magisch, Feb 24 '16 at 08:10
Possible duplicate of [How to generate all permutations of a string in PHP?](http://stackoverflow.com/questions/2617055/how-to-generate-all-permutations-of-a-string-in-php) — mitkosoft, Feb 24 '16 at 08:47

VolkerK · Answer 1 · 2016-02-24T08:45:12.860

2

Short version: Your terminating condition for the while loop "is" permutational while your if(!in_array...) test "is" combinational.

Let's assume $a=11;: then $ele_amnt is 2 and your while loop will stop when the array $output contains more than one element.
Your shuffle/implode code can produce either the string <firstelement><seconelement> or <secondelement><firstelement>, both being 11.
And if(!in_array( $justnumber , $output)) allows only one of them to be appended to $output. So count($output) will be 1 after the first iteration and will stay 1 in perpetuity. Same for every $a with duplicate digits.

shuffle() changes the position of elements in an array at random. SO, the performance of the algorithm depends on ....luck ;-) You might be interested in something like https://pear.php.net/package/Math_Combinatorics instead.

edited Feb 24 '16 at 08:45

answered Feb 24 '16 at 08:35

VolkerK

95,432
20
163
226

The OP's code works for permutations (even though it does brute force, and will get less efficient for longer strings). The problem lies in the repeated characters. You have linked to a package that has this as a description: "A package that returns all the combinations and permutations, without repitition" – Progrock Feb 24 '16 at 09:06
"The OP's code works for permutations" - no, it mixes permutation and combination and therefore doesn't work (i.e. there are cases where it doesn't work). If the part about " You have linked to a package" has a point, I've missed it. – VolkerK Feb 24 '16 at 09:47
I originally misread the question as the OP wanting to have repeated output characters. I.e. Given an input of ab, output: aa,ab,ba,bb,a,b. – Progrock Feb 24 '16 at 11:23

Progrock · Answer 2 · 2016-02-24T11:52:50.730

Your output array will contain less permutations if you have repeated characters in your input. So your loop never completes.

You could map your inputs, then later map back from your output, and then filter to do as you desire:

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

Outputs:

array (size=3)
  0 => string '122' (length=3)
  2 => string '212' (length=3)
  3 => string '221' (length=3)

Your code with guards on the factorial and permutation functions:

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;
}

Number permutations in PHP with repeated characters

2 Answers2