Warum passiert Duplikate in Heaps Algorithmus

Question

Ich möchte alle Permutationen von Elementen des Arrays erhalten. Quelle Array ist sehr einfach:

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

ich den Code schrieb für Heap's algorithm zu implementieren,

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

Das Ergebnis der Arbeiten hat eine viele Doppelungen

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' 

Bitte helfen Sie mir zu verstehen, ein Grund dafür und den Code reparieren. Ich möchte jegliche Duplizierung aus dem Ergebnis entfernen. Dank

Answer 1

Ihr Problem ist nur, dass Sie die $collection durch Verweis übergeben müssen, weil PHP ein Array Kopie standardmäßig erstellt:

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