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

Déduire 0 en premier lieu. Le zéro est une identité pour l'addition, il est donc inutile par les lois du monoïde dans ce cas particulier. Déduisez également les nombres négatifs si vous voulez monter jusqu'à un nombre positif. Sinon, vous auriez également besoin d'une opération de soustraction.

Donc... l'algorithme le plus rapide que vous pouvez obtenir sur ce travail particulier est le suivant donné en JS.

function items2T([n,...ns],t){
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var data = [3, 9, 8, 4, 5, 7, 10],
    result;

console.time("combos");
result = items2T(data, 15);
console.timeEnd("combos");
console.log(JSON.stringify(result));

C'est un algorithme très rapide mais si vous triez les data tableau descendant il sera encore plus rapide. Utilisation de .sort() est insignifiante puisque l'algorithme aboutira à beaucoup moins d'invocations récursives.

Answer 2

Pour trouver les combinaisons en utilisant excel - (c'est assez facile). (Votre ordinateur ne doit pas être trop lent)

1. Aller sur ce site
2. Accédez à la page "Somme à la cible".

3. Téléchargez le fichier excel "Sum to Target".

   Suivez les indications de la page du site web.

J'espère que cela vous aidera.

Answer 3

La réponse de @KeithBeller avec des noms de variables légèrement modifiés et quelques commentaires.

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

    public static void SumUp(List<int> input, int targetSum)
    {
        SumUpRecursive(input, targetSum, new List<int>());
    }

    private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum)
    {
        // Sum up partial
        int sum = 0;
        foreach (int x in listToSum)
            sum += x;

        //Check sum matched
        if (sum == targetSum)
            Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum);

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.Count; i++)
        {
            //Build list of remaining items to iterate
            List<int> newRemaining = new List<int>();
            for (int j = i + 1; j < remaining.Count; j++)
                newRemaining.Add(remaining[j]);

            //Update partial list
            List<int> newListToSum = new List<int>(listToSum);
            int currentItem = remaining[i];
            newListToSum.Add(currentItem);
            SumUpRecursive(newRemaining, targetSum, newListToSum);
        }
    }'

Answer 4

Ceci peut être utilisé pour imprimer toutes les réponses aussi bien

public void recur(int[] a, int n, int sum, int[] ans, int ind) {
    if (n < 0 && sum != 0)
        return;
    if (n < 0 && sum == 0) {
        print(ans, ind);
        return;
    }
    if (sum >= a[n]) {
        ans[ind] = a[n];
        recur(a, n - 1, sum - a[n], ans, ind + 1);
    }
    recur(a, n - 1, sum, ans, ind);
}

public void print(int[] a, int n) {
    for (int i = 0; i < n; i++)
        System.out.print(a[i] + " ");
    System.out.println();
}

La complexité du temps est exponentielle. Ordre de 2^n

Answer 5

Conversion en Swift 3 de la solution Java : (par @JeremyThompson)

protocol _IntType { }
extension Int: _IntType {}

extension Array where Element: _IntType {

    func subsets(to: Int) -> [[Element]]? {

        func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {

            var sum: Int = 0
            for x in partial {
                sum += x as! Int
            }

            if sum == target {
                solution.append(partial)
            }

            guard sum < target else {
                return
            }

            for i in stride(from: 0, to: numbers.count, by: 1) {

                var remaining = [Element]()

                for j in stride(from: i + 1, to: numbers.count, by: 1) {
                    remaining.append(numbers[j])
                }

                var partial_rec = [Element](partial)
                partial_rec.append(numbers[i])

                sum_up_recursive(remaining, target, partial_rec, &solution)
            }
        }

        var solutions = [[Element]]()
        sum_up_recursive(self, to, [Element](), &solutions)

        return solutions.count > 0 ? solutions : nil
    }

}

l'usage :

let numbers = [3, 9, 8, 4, 5, 7, 10]

if let solution = numbers.subsets(to: 15) {
    print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
    print("not possible")
}