Algorithme de partition Java

Question

Je cherche un algorithme récursif pour partitionner un nombre en k parties.

Pour exemple:

P(5,2) > { {1,4},{2,3} } 
P(7,2) > { {1,6},{2,5},{3,4} } 
P(5,3) > { {1,1,3},{1,2,2} } 

En Java, mais il peut être un autre langage.

Mon code actuellement

public static void partition(int n, int k) { 
     partition(n, k, " "); 
    } 

    public static void partition(int n, int max, String prefix) { 
     if (n == 0) { 
      System.out.println(prefix); 
      return; 
     } 

     for (int i = Math.min(max, n); i >= 1; i--) { 
      partition(n-i, i, prefix + " " + i); 
     } 
    } 

Answer 1

Si je comprends bien, vous voulez partitionner n exactement k nombres, chacun au moins un (1).

Je voudrais d'abord vérifier que n >= k et k >= 1 car sinon ce n'est pas possible (laisser le cas d'angle n = k = 0).

Dans votre appel récursif, puisque vous apposent exactement un numéro à prefix, je pense que vous devriez passer max - 1 comme second argument pour vous assurer que vous finirez avec exactement k partitions.

Il peut y avoir d'autres problèmes. Si vous nous dites votre sortie actuelle, il peut être plus facile à voir.