Trouver toutes les combinaisons possibles de chiffres pour atteindre une somme donnée.

Question

Comment faire pour tester toutes les combinaisons possibles d'ajouts à partir d'un ensemble donné. N de nombres pour qu'ils aboutissent à un nombre final donné ?

Un bref exemple :

• Ensemble de chiffres à ajouter : N = {1,5,22,15,0,...}
• Résultat souhaité : 12345

Answer 1

Ce problème peut être résolu par une combinaison récursive de toutes les sommes possibles en filtrant celles qui atteignent la cible. Voici l'algorithme en Python :

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 

if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Ce type d'algorithmes est très bien expliqué dans ce qui suit Conférence sur la programmation abstraite à Stanford - cette vidéo est très recommandable pour comprendre comment la récursion fonctionne pour générer des permutations de solutions.

Modifier

Ce qui précède est une fonction de générateur, ce qui le rend un peu plus utile. Nécessite Python 3.3+ à cause de yield from .

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Voici la version Java du même algorithme :

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

C'est exactement la même heuristique. Mon Java est un peu rouillé mais je pense que c'est facile à comprendre.

Conversion en C# d'une solution Java : (par @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

La solution Ruby : (par @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit : discussion sur la complexité

Comme d'autres l'ont mentionné, il s'agit d'une problème NP-hard . Il peut être résolu en un temps exponentiel O(2^n), par exemple pour n=10 il y aura 1024 solutions possibles. Si les cibles que vous essayez d'atteindre sont dans une gamme basse, alors cet algorithme fonctionne. Ainsi, par exemple :

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) génère 1024 branches car la cible n'a jamais l'occasion de filtrer les solutions possibles.

D'autre part subset_sum([1,2,3,4,5,6,7,8,9,10],10) ne génère que 175 branches, car la cible à atteindre 10 permet de filtrer de nombreuses combinaisons.

Si N y Target sont de grands nombres, il faut passer à une version approximative de la solution.

Answer 2

La solution de ce problème a été donnée un million de fois sur Internet. Le problème s'appelle Le problème du changement de monnaie . On peut trouver des solutions à http://rosettacode.org/wiki/Count_the_coins et son modèle mathématique à http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (ou Google problème de changement de pièces ).

Au fait, la solution Scala de Tsagadai est intéressante. Cet exemple produit soit 1 soit 0. Comme effet secondaire, il liste sur la console toutes les solutions possibles. Il affiche la solution, mais ne parvient pas à la rendre utilisable de quelque manière que ce soit.

Pour être aussi utile que possible, le code doit retourner un List[List[Int]] afin de permettre d'obtenir le nombre de solutions (longueur de la liste des listes), la "meilleure" solution (la liste la plus courte), ou toutes les solutions possibles.

Voici un exemple. Il est très inefficace, mais il est facile à comprendre.

object Sum extends App {

  def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {

    def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
      (x._1 + y._1, x._2 ::: y._2)
    }

    def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
      if (numbers.isEmpty || total < 0) {
        (0, resultAcc)
      } else if (total == 0) {
        (1, sumAcc :: resultAcc)
      } else {
        add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
      }
    }

    sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
  }

  println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}

Lorsqu'il est exécuté, il affiche :

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)

El sumCombinations() peut être utilisée seule, et le résultat peut être analysé plus avant pour afficher la "meilleure" solution (la liste la plus courte), ou le nombre de solutions (le nombre de listes).

Notez que même ainsi, les exigences peuvent ne pas être entièrement satisfaites. Il se peut que l'ordre de chaque liste dans la solution soit important. Dans un tel cas, chaque liste devrait être dupliquée autant de fois qu'il y a de combinaisons de ses éléments. Ou bien nous pourrions être intéressés uniquement par les combinaisons qui sont différentes.

Par exemple, on peut considérer que List(5, 10) devrait donner deux combinaisons : List(5, 10) y List(10, 5) . Pour List(5, 5, 5) il peut donner trois combinaisons ou une seule, selon les besoins. Pour les nombres entiers, les trois permutations sont équivalentes, mais si nous avons affaire à des pièces de monnaie, comme dans le "problème du changement de pièce", elles ne le sont pas.

Les exigences ne précisent pas non plus si chaque numéro (ou pièce) peut être utilisé une seule fois ou plusieurs fois. On pourrait (et on devrait !) généraliser le problème à une liste de listes d'occurrences de chaque nombre. Dans la vie réelle, cela se traduit par "quelles sont les manières possibles de gagner une certaine somme d'argent avec un ensemble de pièces (et non un ensemble de valeurs de pièces)". Le problème original n'est qu'un cas particulier de ce problème, où nous avons autant d'occurrences de chaque pièce que nécessaire pour obtenir le montant total avec chaque valeur de pièce.

Answer 3

Une version Javascript :

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target) {
    return;  // if we reach the number why bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([3,9,8,4,5,7,10],15);

// output:
// 3+8+4=15
// 3+5+7=15
// 8+7=15
// 5+10=15

Answer 4

En Haskell :

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

Y J :

(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...

Comme vous pouvez le remarquer, tous deux adoptent la même approche et divisent le problème en deux parties : générer chaque membre de l'ensemble de puissance, et vérifier la somme de chaque membre par rapport à la cible.

Il existe d'autres solutions, mais celle-ci est la plus simple.

Avez-vous besoin d'aide pour l'un ou l'autre ou pour trouver une approche différente ?

Answer 5

Version C++ du même algorithme

#include <iostream>
#include <list>
void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial)
{
        int s = 0;
        for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
        {
            s += *cit;
        }
        if(s == target)
        {
                std::cout << "sum([";

                for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
                {
                    std::cout << *cit << ",";
                }
                std::cout << "])=" << target << std::endl;
        }
        if(s >= target)
            return;
        int n;
        for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
        {
            n = *ai;
            std::list<int> remaining;
            for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
            {
                if(aj == ai)continue;
                remaining.push_back(*aj);
            }
            std::list<int> partial_rec=partial;
            partial_rec.push_back(n);
            subset_sum_recursive(remaining,target,partial_rec);

        }
}

void subset_sum(std::list<int> numbers,int target)
{
    subset_sum_recursive(numbers,target,std::list<int>());
}
int main()
{
    std::list<int> a;
    a.push_back (3); a.push_back (9); a.push_back (8);
    a.push_back (4);
    a.push_back (5);
    a.push_back (7);
    a.push_back (10);
    int n = 15;
    //std::cin >> n;
    subset_sum(a, n);
    return 0;
}