Comment proposer un algorithme "Opérations de sous-ensemble"?

Question

Je travaille sur ce problème:

Étant donné un ensemble (ou multiset) de nombres positifs, trouver tous les numéros qui sont la combinaison de certains éléments de l'ensemble. La combinaison signifie somme, soustraction ou produit.

Par exemple, si A = {3, 4, 7}, nous devons trouver 3, 4, 7, 3 + 4, 3 * 4, | 3-4 |, 3 + 7, 3 * 7, | 3-7 |, 4 + 7, 4 * 7, | 4-7 |, 3 + 4 + 7, 3 + 4 * 7, 3+ | 4-7 |, | 3 + 7-4 |, | 3 * 7-4 | ...

Heureusement, notre ensemble n'est pas plus grand que 10 nombres, mais je ne suis pas capable de trouver un algorithme pour trouver toutes les solutions. Vous pouvez voir ce problème comme le "problème de la somme des sous-ensembles" (donné un ensemble A et un entier k, disons si A contient un sous-ensemble dont les éléments somme k) mais au lieu de somme, c'est une combinaison d'opérateurs. toutes les valeurs de k possibles.

J'ai essayé mais trop de solutions possibles manquent. Il n'est pas correct, mais je veux seulement montrer l'essence de mon idée: (code C++)

vector<int> analyze (vector<int> v) { 

    if (v.size()==1) return v[0]; 
    vector<int> result; 
    vector<int> u = analyze(v.delete(1)); //u = analyze(v[1], ..., v[n]) 
    for (int i = 0; i < u.size(); i++) { 
     result.add(v[0] + u[i]); 
     result.add(v[0] * u[i]); 
     result.add(abs(v[0] - u[i])); 
    } 
    result.add(v[0]); 
    return result + u; //Union 
} 

Si A = {a, b, c, d} cette fonction ne reviendra pas:

une * (c + b * d)

(a b) + (c d)

| ad | + b

Tout le monde sait sur la façon d'aborder ce problème , ou toute bibliographie qui aide?

Answer 1

Je suggère de générer tous les arbres d'analyse (il n'est pas nécessaire de le faire explicitement).

Supposons que nous ayons un sous-ensemble de l'ensemble initial. S'il y a un nombre, nous le renvoyons juste. Sinon, nous parcourons toutes les opérations. Pour une opération fixe, nous parcourons toutes les façons de partitionner l'ensemble en deux sous-ensembles. Nous pouvons calculer toutes les expressions possibles pour les sous-ensembles de façon récursive, puis les combiner en utilisant cette opération.

Pour prendre en compte le fait que nous sommes autorisés à ne pas utiliser certains des nombres, nous pouvons exécuter cet algorithme pour tous les sous-ensembles de l'ensemble donné.