Permutation d'une suite d'entiers où la somme partielle n'atteint jamais les valeurs données

Question

J'ai essayé de comprendre ce problème, mais en vain. J'ai deux tableaux d'entrée: a [n] et b [n-1]. Ce que j'essaie de faire est de sortir une permutation du tableau "a" de sorte qu'aucune somme partielle ne soit égale à un élément quelconque du tableau "b". Je vais essayer d'illustrer cela par un exemple:

a = {1, 3, 7}

b = {4, 8}

Ainsi, dans ce cas, la permutation {1, 3, 7} ne fonctionnerait pas parce que nous avons les sommes partielles:

1, 1 + 3 = 4 (qui fait partie du tableau b), 1 + 3 + 7 = 11.

Une bonne permutation serait {3, 7, 1}, parce que nous avons les sommes partielles:

3, 3 + 7 = 10, 3 + 7 + 1 = 11 (les résultats ne sont pas dans le tableau b).

J'ai essayé une approche de programmation dynamique (principalement un problème de somme de sous-ensembles), mais cela ne semble pas être utile dans ce cas. Quelqu'un a-t-il une idée de la façon d'aborder ce problème?

Answer 1

L'algorithme que je suggère est récursif, et j'ai aussi un échantillon de code qui pourrait être utile. L'idée est de faire marche arrière:

D'abord voir si la somme totale du tableau a n'apparaît pas dans le tableau b (si c'est le cas, nous nous arrêtons là). Une fois que nous avons annulé le contrôle de somme, nous devons décider de l'ordre des éléments. Nous commençons à partir de la fin, en sélectionnant un candidat i pour la dernière position, et voyons si nous pouvons répéter ce processus pour le tableau n-1 a, dans lequel nous avons retiré notre candidat du tableau. Si c'est le cas, nous ajoutons le candidat i à la position finale du tableau renvoyé - et renvoyons ce tableau.

Les étapes récursives sont:

1. Étant donné un tableau, vérifiez si elle ne contient qu'un seul élément. Si c'est le cas, vérifiez si l'élément existe dans le tableau de somme interdite. Si c'est le cas, retournez null. Si ce n'est pas le cas, renvoyez le tableau avec son seul élément tel quel. (Fin de cas)

2. Compte tenu du tableau avec plus d'un élément:

   2.1. vérifier sa somme par rapport au tableau de somme interdit. S'il existe, renvoyez null. si ce n'est pas le cas, parcourez le tableau et pour chaque élément i appelez la méthode récursivement avec le tableau sans le candidat i.

   2.2. Si l'appel récursif a ramené null, continuez d'itérer.

   2.3. S'il ramène un tableau, attachez l'élément i à la fin du tableau et renvoyez-le.

Le code ci-dessous montre l'algorithme en Java. J'ai essayé de garder les choses simples.

public static boolean contains(int[] arr, int val) { 

    for (int i : arr) { 
     if (i == val) { 
     return true; 
     } 
    } 
    return false; 
    } 

    public static int sum(int[] arr) { 

    int sum = 0; 
    for (int i : arr) { 
     sum += i; 
    } 
    return sum; 
    } 

    public static int[] removeElem(int index, int[] arr) { 

    int[] retArr = new int[arr.length - 1]; 
    for (int i = 0; i < index; i++) { 
     retArr[i] = arr[i]; 
    } 
    for (int i = index + 1; i < arr.length; i++) { 
     retArr[i - 1] = arr[i]; 
    } 
    return retArr; 
    } 

    public static int[] getArr(int[] arr, int[] forbidden) { 

    if (arr.length == 1) { 
     if (!contains(forbidden, arr[0])) 
     return arr; 
     else 
     return null; 
    } 
    else { 
     if (contains(forbidden, sum(arr))) { 
     return null; 
     } 
     else { 
     for (int i = 0; i < arr.length; i++) { 
      int[] retArr = getArr(removeElem(i, arr), forbidden); 
      if (retArr != null) { 
      int[] newArr = new int[arr.length]; 
      for (int j = 0; j < retArr.length; j++) { 
       newArr[j] = retArr[j]; 
      } 
      newArr[newArr.length - 1] = arr[i]; 
      return newArr; 
      } 
     } 
     } 
    } 
    return null; 
    } 

    public static void main(String[] args) throws IOException { 

    int[] a = { 1, 3, 7, 9 }; 
    int[] b = { 4, 19, 16 }; 

    System.out.println("input array a: " + Arrays.toString(a)); 
    System.out.println("forbidden sum array b: " + Arrays.toString(b)); 
    System.out.println(Arrays.toString(getArr(a, b))); 
    } 

sortie:

input array a: [1, 3, 7, 9] 
forbidden sum array b: [4, 19, 16] 
[9, 1, 7, 3] 

quelques autres exemples:

input array a: [1, 3, 7, 9] 
forbidden sum array b: [4, 19, 8] 
[9, 7, 1, 3] 

input array a: [1, 3, 7, 9] 
forbidden sum array b: [4, 10, 8] 
[9, 7, 3, 1] 

input array a: [1, 3, 7, 9] 
forbidden sum array b: [4, 10, 20] 
null 
(for impossible forbidden sum)