CODEWITHSUNDEEP
php
tonpsl
tonpsl

Reputation: 45

Number permutations in PHP with repeated characters

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?

Upvotes: 2

Views: 406

Answers (2)

Progrock
Progrock

Reputation: 7485

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

Upvotes: 0

VolkerK
VolkerK

Reputation: 96159

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.

Upvotes: 2

Related Questions