Why does duplications happen in Heap's algorithm

Question

I want to get all permutations from elements of array. Source array is very simple:

$arr = [ 1,2,3,4 ];

I wrote the code for implement Heap's algorithm,

private function mixture( $size, array $collection ) {

    $permutations = [];
    $offset = $size - 1;

    if ( 1 === $size ) {
        $permutations[] = implode( '-', $collection );
        return $permutations;
    }

    for ( $i = 0; $i < $offset; $i++ ) {
        $permutations = array_merge( $permutations, $this->mixture( $offset, $collection ) );

        $j = ( 0 == $size % 2 ) ? $i : 0;
        $tmp_el = $collection[ $offset ];
        $collection[ $offset ] = $collection[ $j ];
        $collection[ $j ] = $tmp_el;
    }

    $permutations = array_merge( $permutations, $this->mixture( $offset, $collection ) );
    return $permutations;
}

The result of works has a many of duplications

array (size=24)
    0 => '1-2-3-4'  << same 4
    1 => '2-1-3-4'  << same 5
    2 => '3-2-1-4'
    3 => '2-3-1-4'
    4 => '1-2-3-4'  << same 0
    5 => '2-1-3-4'  < same 1
    6 => '4-2-3-1'
    7 => '2-4-3-1'
    8 => '3-2-4-1'
    9 => '2-3-4-1'
    10 => '4-2-3-1'
    11 => '2-4-3-1'
    12 => '4-1-3-2'
    13 => '1-4-3-2'
    14 => '3-1-4-2'
    15 => '1-3-4-2'
    16 => '4-1-3-2'
    17 => '1-4-3-2'
    18 => '4-1-2-3'
    19 => '1-4-2-3'
    20 => '2-1-4-3'
    21 => '1-2-4-3'
    22 => '4-1-2-3'
    23 => '1-4-2-3'

Please, help me to understand a reason for this and fix the code. I want to remove any duplication from the result. Thanks

Answer 1

Your only problem is that you need to pass the $collection by reference because PHP creates an array copy by default:

mixture( $size, array &$collection )

https://3v4l.org/7Vn2p

<?php

$arr = [ 1,2,3,4 ];

$expected = [
    '1-2-3-4',
    '2-1-3-4',
    '3-1-2-4',
    '1-3-2-4',
    '2-3-1-4',
    '3-2-1-4',
    '4-2-1-3',
    '2-4-1-3',
    '1-4-2-3',
    '4-1-2-3',
    '2-1-4-3',
    '1-2-4-3',
    '1-3-4-2',
    '3-1-4-2',
    '4-1-3-2',
    '1-4-3-2',
    '3-4-1-2',
    '4-3-1-2',
    '4-3-2-1',
    '3-4-2-1',
    '2-4-3-1',
    '4-2-3-1',
    '3-2-4-1',
    '2-3-4-1',
];

function mixture( $size, array &$collection ) {

    $permutations = [];
    $offset = $size - 1;

    if ( 1 === $size ) {
        $permutations[] = implode( '-', $collection );
        return $permutations;
    }

    for ( $i = 0; $i < $offset; $i++ ) {
        $permutations = array_merge( $permutations, mixture( $offset, $collection ) );

        $j = ( 0 == $size % 2 ) ? $i : 0;
        $tmp_el = $collection[ $offset ];
        $collection[ $offset ] = $collection[ $j ];
        $collection[ $j ] = $tmp_el;
    }

    $permutations = array_merge( $permutations, mixture( $offset, $collection ) );
    return $permutations;
}

print_r($permutations = mixture( count($arr), $arr ));

if ($expected == $permutations) {
    echo 'PASS'.PHP_EOL;
} else {
    echo 'FAIL'.PHP_EOL;
    echo 'missing: '.PHP_EOL;
    print_r(array_diff($expected, array_unique($permutations)));
}