Integer Partitionierung in PHP

Question

Das fühlt sich an wie ein sehr einfaches Problem, aber ich schaffe es nicht, es elegant zu machen und "fühlt sich richtig an". Hier ist das Problem:

eine Reihe T Geben, alle möglichen Arten drucken, um T. Zum Beispiel zu bekommen:

T = 5 
1 + 1 + 1 +1 + 1 
2 + 1 + 1 + 1 
3 + 1 + 1 
2 + 2 + 1 
4 + 1 
3 + 2 

Beachten Sie, dass, 3 + 2 gleich als 2 + 3, so dass Sie don Ich muss beide Fälle drucken.

Ich muss es in PHP tun, hoffe, dass jeder helfen kann :).

Answer 1

Ein einfacher Weg, um dieses Problem zu lösen, ist es rekursiv zu lösen. Es folgt eine Beispielcode,

<?php 
function recursion($left, $last, $ar) { 
    if($left == 0) { 
     foreach ($ar as $n) { 
      printf("%d ", $n); 
     } 
     print "<br>"; 
     return; 
    } 
    for($n = $last; $n <= $left; $n++) { 
     $b = $ar; 
     array_push($b, $n); 
     recursion($left - $n, $n, $b); 
    } 
} 

recursion(5, 1, []); 

Ausgang:

1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5 

Beachten Sie, dass diese Brute-Force-rekursive Lösung nicht für größere T. arbeiten scheint, dass eine dynamische Programmierung Lösungen existieren, die diese problm für Zahlen lösen können in einem größeren Bereich.