Un problème récursif...

a marqué ce sujet comme résolu.
Auteur du sujet

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 :

$$\displaystyle \sum_{i = 0}^n \binom{n}{i} = 2^n$$

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.

Édité par elyppire

+0 -0

Cette réponse a aidé l’auteur du sujet

Bonsoir,

Désolé pour la mauvaise mise en page.

Je connais pas du tout le C++ donc je ne pense pas pouvoir t’aider de ce côté, et je ne suis pas sûr d’avoir très bien l’algorithme que tu proposes non plus. Je pense que tu déroules ton algorithme sur un petit exemple, tu va te rendre compte comment tu fais plusieurs fois la même somme, sinon voilà comment j’ai déroulé :

1
2
3
4
5
Tu lances ton algo avec (1, 2, 3) (appel initial)
- Il va lancer des appels récursifs avec (1, 2), (2, 3), (1, 3).
- (1, 2) peut lancer avec 1 ou 2
- (2, 3) peut lancer avec 2 ou 3
- (1, 3) peut lancer avec 1 ou 3

En fait tu te retrouves dans une situation ou des appels récursifs vont avoir supprimé exactement les mêmes éléments du tableau donc calculer la même somme (par exemple 3 puis 1 ou 1 puis 3) et c’est normal que la complexité explose dans ce cas là. Je pense que tu peux tenter de changer cela en empêchant l’appel de supprimer certain élément, par exemple, une fois qu’un élément d’indice $i$ du tableau a été supprimé, il ne peut pas supprimer un élément d’indice inférieur à $i$. Si je reprends l’exemple plus haut :

1
2
3
4
5
6
7
8
9
-> L'algo se lance avec [1, 2, 3], l'indice est de -1
--> lance avec [1, 2], et indice 2
--->  ne peut pas faire d'appel récursif car indice > taille du tableau donc termine
--> lance avec [2, 3] et indice 0
---> peut faire un appel récursif avec [2] et indice 1
---> peut faire un appel récursif avec [3] et indice 0
----> peut faire un appel récursif avec [] et indice 0
--> lance avec [1, 3] et indice 1
---> peut faire un appel récursif avec [1] et indice 1

Ici il n’y a plus le problème de calculer plusieurs fois la même somme, puisque tu ne peux pas avoir le cas où des appels récursifs ont supprimé exactement les mêmes éléments.


D’un point de vue itératif, tu peux essayer d’utiliser un tableau de booléen (ou quelque chose de proche) qui indique si oui ou non l’entier est présent dans la prochaine somme que tu va calculer.

1
2
3
4
5
Par exemple, si tu prends n = 2, et les entiers 1 et 2.
- Tu peux dire que 00 indique que tu ne prends aucun des entiers (= 0)
- 01 -> seulement le deuxième (= 2)
- 10 -> seulement le premier (= 1)
- 11 -> les deux (= 3)

Et tu peux généraliser cela avec plus d’entiers.

Édité par Zefjo

+0 -0

Cette réponse a aidé l’auteur du sujet

Sans trop me pencher sur la question, je pense que quelque-chose comme ça est plus efficace qu’utiliser un algo recursif.

 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
41
42
43
44
45
46
47
#include<iostream>
#include<vector>
#include<set>


int main()
{
    std::set<int> everySum;
    std::set<int> everySum2;

    bool odd = false;

    unsigned int n {0};
    std::cin >> n;

    int inter {0};
    std::cin >> inter;
    everySum.insert(inter);
    for (int i = 1; i < n; ++i)
    {
        std::cin >> inter;
        if( ! odd  ) {
            for( auto it = everySum.begin() ; it != everySum.end() ; it++) {
                everySum2.insert(inter+*it);
                everySum2.insert(*it);
            }
            everySum2.insert(inter);
        } else {
            for( auto it = everySum2.begin() ; it != everySum2.end() ; it++) {
                everySum.insert(inter+*it);
            }
            everySum.insert(inter);
        }
        odd=!odd;
    }

    if( odd ) {
        for( auto it = everySum2.begin() ; it != everySum2.end() ; it++)
            std::cout << *it << " ";
    } else {
        for( auto it = everySum.begin() ; it != everySum.end() ; it++)
            std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Après reflection rapide … Il me semble que l’algo que je propose est en $O(2^n)$. En considérant que l’insertion dans un set est en temps constant, ce qui ne me semble pas dérésonnable puisque certainement derrière ça doit être une table de hashage ?

Je ne comprend pas pourquoi la sortie des éléments est triées … Certainement qu’il doit exister une version non ordonné de set et qu’elle est plus efficace au niveau du parcourt.

Si c’est vraiment ça alors set doit être implémenter avec un arbre binaire. Du coup l’insertion n’est pas vraiment en $O(1)$ mais la version non ordonnée doit corriger le problème.

Bisou et bonne nuit 😗

Édité par ache

ache.one                                                            🦊

+0 -0

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.

+2 -0

Cette réponse a aidé l’auteur du sujet

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.


Sinon, la récursivité c’est l’art de se ramener à un problème plus simple. Ici, si je comprends bien, ta fonction calcSum(actual) répond à la question suivante : « afficher toutes les sommes d’un nombre non nul d’éléments de actual ». Déjà, ça montre tu as bien assimilé cette notion de récursivité, parce qu’effectivement, si ton paramètre est de taille $n$, tu fais $n$ appels récursifs sur quelque chose de taille $n-1$.

Comme tu l’as effectivement remarqué, tu fais beaucoup de calculs en double. Essentiellement, supprimer un élément d’un ensemble c’est une opération qui commute dans la plupart des cas, donc quand tu essayes de supprimer un élément $a$ puis de supprimer un élément $b$, tu fais le même appel qu’en supprimant $b$ puis $a$. Du coup ça explose très vite (le nombre d’appels à ta fonction calcSum avec un ensemble de taille $n$ en entrée vérifie $A(n)=nA(n-1)$, donc au total tu en fais environ $n!$).

Pour régler ce problème de commutativité de la suppression, il y a une « astuce » assez générale qui consiste à toujours choisir l’ordre dans lequel tu fais ces opérations. Actuellement, ta fonction récursive prend $n$ décisions, avec initialement $n$ choix, puis $n-1$, etc. : tu choisis un premier élément à supprimer, puis un deuxième, etc. 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 ? Puis : est-ce que je supprime le deuxième ? etc.

Il restera ensuite à simplifier le contenu de ta fonction récursive, mais ça devrait déjà donner des idées. Une solution (correctement indentée) de ce problème tient en 20 lignes.

Édité par Lucas-84

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.

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0

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.

Édité par fromvega

+0 -0

@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 ?

Édité par ache

ache.one                                                            🦊

+0 -0
Auteur du sujet

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$.

Pour régler ce problème de commutativité de la suppression, il y a une « astuce » assez générale qui consiste à toujours choisir l’ordre dans lequel tu fais ces opérations. Actuellement, ta fonction récursive prend $n$ décisions, avec initialement $n$ choix, puis $n-1$, etc. : tu choisis un premier élément à supprimer, puis un deuxième, etc. 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 ? Puis : est-ce que je supprime le deuxième ? etc.

Il restera ensuite à simplifier le contenu de ta fonction récursive, mais ça devrait déjà donner des idées. Une solution (correctement indentée) de ce problème tient en 20 lignes.

Lucas-84

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;
}

Il restera ensuite à simplifier le contenu de ta fonction récursive, mais ça devrait déjà |donner des idées. Une solution (correctement indentée) de ce problème tient en 20 lignes.

Lucas-84 o_O
+0 -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

:euh:

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.

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte