Un problème récursif...

Bonsoir,

J’essaie de résoudre un problème algorithmique proprement mais j’ai un peu de mal. Voici le problème :

• On vous donne un entier $n$
• On vous donne $n$ entiers non nécessairement positif
• Afficher toutes les sommes qu’il est possible d’effectuer avec ces entiers.

Par exemple : Si l’utilisateur entre l’entier $n = 3$, et les trois entiers $1, 2, 3$ alors le programme devra afficher $1, 2, 3, 4, 5$, car $1+2 = 3$, $ 2+3 = 5$…

Bon, tout d’abord je me dis qu’une résolution fera sûrement intervenir un algorithme récursif car je vois difficilement comment un algorithme itératif peut marcher dès lors que $n$ est inconnu avant compilation.

Voilà l’idée de l’algorithme que j’ai implémenté :

On prend deux tableaux, l’un va contenir les éléments entrés par l’utilisateur l’autre l’ensemble des sommes possibles. Je fais une boucle for sur le premier tableau et je pop un élément de ce tableau et j’appelle la fonction.

Bon ce n’est pas très clair, donc voilà son implémentation en C++ :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include <numeric>

void calcSum (std::vector<int> actual, std::list<int> &allSum)
{
    std::vector<int>copy;
    if (actual.size() == 0 ){return;}
    allSum.push_back (std::accumulate(begin(actual), end(actual), 0));
    for (size_t i  = 0; i < actual.size(); ++i)
    {
        copy = actual;
        copy.erase(copy.begin()+i);
        calcSum(copy, allSum);
    }
}
int main()
{
    std::list<int>allSum;
    std::vector<int>actual;
    unsigned int n {0};
    std::cin >> n;

    int inter {0};
    for (int i = 0; i < n; ++i)
    {
        std::cin >> inter;
        actual.push_back(inter);
    }
    calcSum(actual, allSum);
    std::list<int>::const_iterator 
    lit (allSum.begin()), 
    lend(allSum.end());
    for(;lit!=lend;++lit) std::cout << *lit << ' ';
    return 0;
}

Ce code marche parfaitement et m’affiche bien toutes les sommes possibles, néanmoins le problème est qu’il calcule plusieurs fois la même somme. J’ai quand même essayer de faire attention aux structures de données en prenant une liste pour toutes les sommes car l’ajout d’un élément à une liste est en $\mathcal O (1)$ alors que pour un vector il est en $\mathcal O(n)$. Malheureusement cela est négligeable car mon algorithme si je ne me trompe pas tourne en $\mathcal O(n^n)$, ce qui est plutôt énorme.

De plus par rapport à l’énoncé de l’exercice puisque :

alors il est sûrement possible d’implémenter une algorithme en $\mathcal O (2^n)$ et je suis loin du compte.

C’est pourquoi si des personnes ont des idées d’algo plus opti que celui que je propose ou une autre manière de voir les choses, ou encore des suggestions par rapport aux structures de données utilisées n’hésitez pas :p.

Merci d’avance.

Bonne soirée.

Pour moi, il y a une ambiguïté dans l’énoncé. Quand tu parles de recenser TOUTES les sommes, (et quand tu parles ensuite de 2^n), si tu as comme jeu de données 1,2 et 3, je pense que la somme 1+2+3=6 est valide. Alors que tu sembles considérer qu’elle n’est pas valide dans ton recensement ( quand tu dis 1,2,3,4,5).

Et je pense que le résultat 0 est également valide. Et avec ces 2 hypothèses, c’est clair qu’un traitement récursif est particulièrement adapté.

Avec ces indices, à toi de jouer.

Perso si n<64 j’aurais tendance à favoriser plutôt la version binaire, ça me parait plus simple que la version récursive.

Mais de toute façon mathématiquement c’est la même chose, et du moment qu’on veut énumérer toutes les possibilités on n’a pas le choix, il faut toutes les tester; je pense qu’on ne peut pas faire beaucoup mieux que O(2^n).

Ca serait très différent si on cherchait une seule solution particulière: à peu de chose près on aurait le problème du sac à dos et on pourrait faire un algorithme de programmation dynamique.

En considérant qu’une somme est l’addition de 2 à n nombres on peut implémenter un algo de complexité O(2^(n-2)) en partant de la somme de tous les nombres et en retranchant 0 à n-2 nombres de cette somme.

@fromvega: Ce qui reste du $O(2^n)$ … Puisque $2^n = 4*2^{n-2}$ …

@QuentinC: J’ai pas compris ta remarque sur $n < 64$.
Si $n$ est trop grand, au contraire, on a tendance à préferer la version itérative pour éviter les stackoverflow, nan ?

C’est une vraie question, j’ai pas compris ton raisonnement, pourrais-tu le détailler ?

Bonsoir,

Je remercie tout le monde pour les suggestions que j’ai reçu.

C’est difficile de parler d’« algo le plus optimisé » si on ne se fixe pas des contraintes raisonnables. Dans quoi vivent tes entiers ? ($|x_i|\le 1000$ ? $|x_i| \le 2^{64}$ ?) Quelles sont les valeurs typiques de $n$ ? Suivant l’objectif, ce ne sont pas les mêmes techniques qu’on va essayer de mettre en œuvre.

Yep désolé pour les imprécisions, c’est plutôt : $\mid x_i \mid \leq 10^4$, pareil pour $n$.

Oui et il semblerait que c’est justement ce que propose Zefjo avec son algorithme, et c’est vrai que c’est plutôt malin d’utiliser le fait que $<$ est une relation d’ordre non commutative pour résoudre le problème. Je ne sais pas si j’y aurai pensé, merci pour cette suggestion Zefjo !

Par contre, je me sens un peu bête après avoir vu le code de ache. En fait je suis tout de suite partit sur l’idée qu’un algo récursif était obligatoire, car $n$ était inconnu, et en fait ce raisonnement est faux puisqu’on peut traiter les données une à une, soit au fur et à mesure que l’utilisateur nous fournit les données. Et je dois avouer que je n’y ai jamais trop pensé, d’habitude je fais juste rapidement ma boucle for qui demande les données à l’utilisateur et ensuite je réfléchis à l’algorithme

Bon finalement, en utilisant l’excellente idée de Zefjo et Lucas-84 j’obtient :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include <numeric>

void calcSum (std::vector<int> actual, std::list<int> &allSum,int lastElement)
{
    std::vector<int>copy;
    if (actual.size() == 0){return;}
    allSum.push_back (std::accumulate(begin(actual), end(actual), 0));

    if(lastElement > actual.size()){return;}
    for (size_t  i  = lastElement; i < actual.size(); ++i)
    {
        copy = actual;
        copy.erase(copy.begin()+i);
        calcSum(copy, allSum, i);
    }
}
int main()
{
    std::list<int>allSum;
    std::vector<int>actual;
    unsigned int n {0};
    std::cin >> n;

    int inter {0};
    for (int i = 0; i < n; ++i)
    {
        std::cin >> inter;
        actual.push_back(inter);
    }
    calcSum(actual, allSum, 0);
    std::list<int>::const_iterator 
    lit (allSum.begin()), 
    lend(allSum.end());
    for(;lit!=lend;++lit) std::cout << *lit << ' ';
    return 0;
}

Yep désolé pour les imprécisions, c’est plutôt : $\mid x_i \mid \leq 10^4$, pareil pour $n$.

Pour le coup je pense pas que l’algo en $2^n$ aille taper dans les $n \approx 10^4$. Si les $x_i$ sont dans $[-C,C]$, on peut faire typiquement du $Cn^2/32$ en temps et $Cn$ en mémoire, ce qui paraît mieux (même si ici ça fait quand même de l’ordre de $10^{10}$ opérations).

$<$ est une relation d’ordre non commutative

…

En fait je suis tout de suite partit sur l’idée qu’un algo récursif était obligatoire, car $n$ était inconnu, et en fait ce raisonnement est faux puisqu’on peut traiter les données une à une, soit au fur et à mesure que l’utilisateur nous fournit les données.

L’idée n’est pas vraiment là-dedans, c’est strictement identique à faire quelque chose comme :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

std::vector<int> ainter(N);

for (int i = 0; i < N; ++i)
    std::cin >> ainter[i];

// ...

for (int inter: ainter) {
    // insérer ici le code de ache
}

Je pense que ce qui te bloque, c’est plutôt comment on pourrait itérer sur toutes les parties d’un ensemble sans passer par du récursif. Pourtant c’est envisageable : il suffit de faire une boucle entre 0 et $2^n-1$ au lieu d’une boucle entre $0$ et $n-1$. Ça nécessite d’introduire une correspondance entre un entier entre $0$ et $2^n-1$ et l’ensemble des parties de $\{0, ..., n-1\}$, mais si on suppose qu’on a une boîte noire is_in_subset(mask, x) qui retourne 1 ssi. l’indice x est dans le sous-ensemble représenté par l’entier mask (entre 0 et $2^n-1$), alors l’algorithme pourrait s’écrire :

1
2
3
4
5
6

// On se place dans le cas N <= 63.
for (int64 mask = 0; mask < (1LL << N); ++mask) {
    int s = 0;
    for (int i = 0; i < N; ++i) if (is_in_subset(mask, i)) s += a[i];
    // ajouter s aux résultats
}

Une implémentation possible de is_in_subset avec les opérations bit-à-bit pourrait être (mask >> x) & 1, ce qui donne un algorithme en $O(n2^n)$ assez concis (c’est, je pense, l’idée de QuentinC). Je pense que le facteur logarithmique $n$ est assez inévitable dans cette approche, et il « disparaît » (modulo la mémoire) dans la bonne version récursive.

Dans la version de ache, cette boucle de $2^n$ est cachée dans l’itération sur le std::set, qui double de taille à chaque étape.

Du coup, tu as bien supprimé les calculs en double dans ta nouvelle version. Bon, ta complexité est plutôt du $n2^n$ que du $2^n$, parce qu’à chaque itération tu recalcules la somme de ton entrée. Est-ce que tu vois une modification de tes paramètres pour éviter de faire du linéaire avec std::accumulate à chaque étape ?

Tes suppressions dans tes std::vector, en plus d’être inefficaces, sont assez inélégantes. Est-ce que tu vois comment changer légèrement ton code pour que actual soit toujours le même au fur et à mesure des appels, et donc en ne faisant aucun erase ?

Il restera enfin à réduire le nombre de transitions, peut-être en méditant plus attentivement le :

Essaye de réduire ce nombre de décisions, par exemple en essayant de faire le choix : est-ce que je supprime le premier élément ?

@QuentinC: J’ai pas compris ta remarque sur n<64. Si n est trop grand, au contraire, on a tendance à préferer la version itérative pour éviter les stackoverflow, nan ? C’est une vraie question, j’ai pas compris ton raisonnement, pourrais-tu le détailler ?

C’est exact, on risque le stack overflow avec un grand n si on utilise la version récursive. Par contre la version itérative est peut-être moins évidente à concevoir, et elle est aussi beaucoup moins sexy (avouez qu’un algorithme récursif est souvent très élégant et plutôt court)

Je pensais surtout à n<64 parce que c’est facile de compter de 0 à 2^64-1. Pour plus grand c’est moins rigolo, à ma connaissance en C++ il n’y a pas de type à la BigInteger du Java dans la bibliothèque standard, et j’en ai pas vu non plus dans boost.

boost::multiprecision

Ce qui est marrant c’est qu’avec OCaml, générer toutes les combinaisons possibles ça prend exactement $5$ lignes (vive le pattern-matching)

1
2
3
4
5

let rec combination l =  
    let rec aux acc = function
        |[] -> acc
        |t::q -> aux ((List.map (fun x -> t::x) (acc))@acc) q
    in aux [[]] l;;

En plus comme c’est tail-recursif je crois que OCaml l’optimise en le mettant en itératif mais je ne suis pas sûr que le compilo fasse toujours cette optimisation.

Générer toutes les permutations de n’importe quelle type de séquence en C++ vers n’importe quel type de séquence en sortie :

1
2
3
4
5
6
7

template<class Iterator, class OutSequence>
void all_permutations(Iterator begin, Iterator end, std::insert_iterator<OutSequence>& it){
    std::sort(begin, end);
    do{
      it = typename OutSequence::value_type(begin, end);
    } while(std::next_permutation(begin, end));
}

On a 2 lignes de plus : une pour que ce soit générique et une accolade.

Mis à part ça : what’s the point ?

Toi tu génère les permutations pas les combinaisons (bon après c’est possible que je comprenne mal ton code), aussi générer toutes les permutations en utilisant std::next_permutation…

C’était juste pour dire que au début je galérais à le faire alors qu’en "pensant" différemment avec OCaml c’est presque évident.

EDIT : d’ailleurs l’idée de bitmask est vraiment génial, je l’ai utilisé pas mal de fois pour des problèmes de combinatoire, je n’en avait jamais entendu parler avant alors qu’il semblerait sur codeforce c’est une technique assez fréquente.

Je peux jouer ?

1
2
3
4
5

import itertools

def all_combinations(items):
    return (e for n in range(len(items)+1)
            for e in itertools.combinations(items, n))

1
2
3
4

def combinations(items, acc=((),)):
    return combinations(items[1:],
                        [z for y in [(x, x + (items[0],)) for x in acc]
                         for z in y]) if items else acc

My bad, mal lu.

… aussi générer toutes les permutations en utilisant std::next_permutation…Source:InaDeepThink

Bah en utilisant les possibilités offertes par le langage et sa bibliothèque standard. Ça fait partie des outils qui sont à disposition et qui du coup servent à faciliter le travail.

On peut le faire quasiment dans le même esprit :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

template<class Sequence, class Iterator>
Sequence combination(Sequence acc, Iterator begin, Iterator end){
  if(begin == end) return acc ;
  else {
    acc.resize(acc.size()*2);
    auto acc_e = std::begin(acc) + acc.size() / 2;
    std::transform(std::begin(acc), acc_e, acc_e, [end](auto t){ t.push_back(*(end-1)); return t ; });
    return combination(acc, begin, end-1);
  }
}

Je pense qu’on peut faire mieux en jouant avec d’autres types d’itérateurs (et avec accumulate en miroir avec ce qu’il y a chez mon voisin du dessous).

Mais ce que je voulais dire par "What’s the point ?" c’est que la longueur du code n’est pas nécessairement un super aspect qualitatif.

aussi générer toutes les permutations en utilisant std::next_permutation…

C’est pourtant assez idiomatique.

C’était juste pour dire que au début je galérais à le faire alors qu’en "pensant" différemment avec OCaml c’est presque évident.

Pour narguer un peu les Pythoneux qui utilisent leurs libs, tu peux même folder le tout :

1

let gen_all_subsets l = List.fold_right (fun t res -> res @ List.map (fun x -> t::x) res) l [[]]

Ça vient du fait qu’on fait beaucoup de dynamiques, et pour représenter des états…