Discussion :

[jlf]

bonjour

j'ai une liste de N nombres

je voudrais trouver toutes les valeurs possible de l'addition de P chiffres dans ces N et compter leur nombre d'apparition

par exemple
N=5 (chiffres a=1, ..e=5)
p = 2

je cherche les 10 résultats suivants :
a+b=3
a+c=4
a+d=5 (apparait 2 fois sur 10)
...
d+e=9 (1 fois)

j'ai essayé avec des boucles for mais je coince

j'entrevois une soluce en récursif mais je crains de vite déborder la pile (mes P et N seront assez grands), je ne sais pas si ça vaut le coup d'essayer comme ça

merci de votre aide

[Graffito]

Une solution théorique :

Developper un arbre avec des branches de profondeur P avec comme info pour les noeuds : le nombre de l'ensemble N choisi, la liste des fils.

La racine a N fils.
La liste des noeuds fils d'un noeud de profondeur X a N-X fils (liste des nombres differents de celui du noeud X et de ses ancetres)
Ensuite, il reste juste à trier les sommes obtenues pour les noeuds terminaux (somme du nombre de la feuille+nombre associés aux ancètres).

Attention, prendre uniquement des fils supérieurs aux pères si on veut éviter les doublons (commme 2+4 et 4+2).

En pratique, il suffit de traiter une seule branche (tableau de P nombres) et de reperer pour chaque niveau l'index du fils (tableau de P index de valeur 1 à N).

[jlf]

pardon mais je ne comprend pas bien ce qu'il faut faire exactement

un petit exemple pour concrétiser me serait utile ?
en tous cas merci de cette réponse

[plegat]

Salut,

Une autre méthode... utiiliser un compteur binaire, à chaque bit correspondant un de tes chiffres. Ensuite, tu incrémentes ton compteur, tu vérifies que le nombre de bits correspondant activés correspond au nombres de chiffres que tu veux additionner, et tu stockes la valeur de la somme dans un tableau (éventuellement, pour les combinaisons non prises en compte, tu mets 0 comme résultat)
Au final, il ne te reste plus qu'à parcourir le tableau contenant les résultats pour compter le nombre d'occurences.

Exemple: avec tes 5 chiffres (1, 2, 3, 4 et 5), somme 2 par 2

compteur à 5 bits (car 5 chiffres), noté a4.a3.a2.a1.a0
a4 correspond au 5
a3 au 4
a2 au 3
a1 au 2
et a0 au 1

on fait partir le compteur de 1 et on incrémente:

compteur=1, en binaire 00001, nombre de bits acitvés: 1, pas bon, suivant
compteur=2, en binaire 00010, 1 bit activé, pas bon
compteur=3, en binaire 00011, 2 bits activés, ok, 2+1=3
...
compteur=6, en binaire 00110, 2 bits activés, 3+2=5
compteur=7, en binaire 00111, 3 bits activés, pas bon
...
et ainsi de suite, jusqu'au dernier:
compteur=31, en binaire 11111, 3 bits activés, pas bon

Tu as au final un tableau de 31 valeurs résultat: {0, 0, 3, ... , 5, 0, ... ,0} sur lequel tu peux travailler.

[jlf]

je ne sais pas si j'ai bien compris mais ça parait séduisant

par exemple si je veux tester tous les paquets de 10 parmi 30 :

1) mon compteur ira de 1 à 2^30
2) pour tous les valeurs de ce compteur je recherche celles dont l'expression binaire possède 10 bits à 1, et j'additionne les nombres dont l'indice est celui des bits activés

c'est ça ?

mais comment faire pour détecter le nombre et le rang des bits mis à 1 ? (je pense faire ça en Delphi)

et par ailleurs ça me limite à une liste de 32 nombres avec des entiers "normaux" ?
à la rigueur ce serait acceptable pour moi, disons mieux que rien, mais bon j'envisageais de laisser un pc travailler plusieurs semaines d'affilée ;o))

[plegat]

c'est ça ?

oui, tout à fait ça.

mais comment faire pour détecter le nombre et le rang des bits mis à 1 ? (je pense faire ça en Delphi)

deux possibilités:

1. utiliser un entier pour le compteur, le convertir en binaire et analyser les bits (avec la limitation que tu soulignes sur le nombre de bits)
2. utiliser un tableau de dimension N, qui sert à stocker la valeur de chaque bit, et gérer l'incrémentation de manière logicielle

et par ailleurs ça me limite à une liste de 32 nombres avec des entiers "normaux" ?

oui, et c'est d'ailleurs pour ça que la seconde solution ci-dessus serait plus souple.

à la rigueur ce serait acceptable pour moi, disons mieux que rien, mais bon j'envisageais de laisser un pc travailler plusieurs semaines d'affilée ;o))

En quoi la durée de travail limiterait la méthode? C'est juste pour la limitation 32 bits ça?
Avec un tableau de dimension N, tu n'es plus limité en taille (enfin... moins qu'avec un entier sur 32 bits), donc tu peux monter assez haut.