Discussion :

[qi130]

Bonjour,

L'intitulé me parait déjà compliqué

Je cherche à construire un tableau contenant toutes les combinaisons possibles de ventilation des votes.

Ainsi, et pour l'exemple: avec 4 votants et 4 candidats, le tableau résultant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
4 0 0 0
3 1 0 0
3 0 1 0
3 0 0 1
2 2 0 0
...
0 0 0 4

soit 35 lignes (si je ne me suis pas gourré dans mon tableau manuel)
je pensais à du récursif, mais je n'arrive à trouver la condition de sortie satisfaisante, et après la 4ème ligne, ça part en sucette et j'ai toujours "3" en colonne 1.

Avez-vous un algo à me proposer ?

Précision: je dois faire ça en vba/excel

[Flodelarab]

Bonjour

décidément, c'est la semaine du dénombrement sur le forum.

Ton cas est simple. "c" est le nombre de candidats et "v" le nombre de votants. On choisit c-1 séparations entre les bulletins parmi v+1, indépendamment de l'ordre (les séparations sont indiscernables) et avec répétition (si on répète, un candidat a zéro vote). C'est donc une combinaison avec répétition.



Je ne suis pas surpris que tu trouves 35 empiriquement :

[qi130]

Merci pour cette réponse.

Tu évoques le "dénombrement" que j'ai googlisé et pour excel (ma contrainte), il existe la fonction COMBINA qui renvoie bien 35.

Mais comment obtenir ces 35 tuples?

[Flodelarab]

Es-tu bien sûr de savoir ce que tu fais ? Pour l'élection présidentielle française 2022, il y a eu 32057325 votes exprimés pour 12 candidats. Soit 9.205423378019423e+74 possibilités de répartitions. Environ 10⁷⁵. . Tu vas légèrement faire exploser la mémoire de ton ordinateur. Surtout avec un tableur qui n'est pas un outil très robuste.

Quel est le vrai but final ?

[anapurna]

salut


si tu n'as que 4 elements max
en faisant 4 boucle imbriqué tu peut faire apparaitre tes denombrement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
  POUR  L De 4 a 0  Faire 
    POUR   K De 4 a 0  Faire 
      POUR   J De 4 a 0  Faire 
         POUR  I De 4 a 0  Faire 
            SI I+J+K+L = 4 Faire
               ECRIRE(I,J,K,L)
            FIN SI
         FIN POUR
      FIN POUR
   FIN POUR
 FIN POUR

pour la recursivité je pense qu'il va faloir passer par un tableau

[tbc92]

Le même code que Anapurna, mais un peu optimisé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
Pour i de 4 à 0 pas -1 faire 
   Pour j de 4-i a 0 pas -1 faire 
      Pour j de 4-i-j a 0 pas -1 faire 
         l=4-i-j-k
         ecrire (i,j,k,l)
      Fin pour
   Fin pour
Fin pour

[AbsoluteLogic]

Bonjour,

Voilà un script pour la génération des tuples de manière récursive.
L'idée est de créer une fonction listant les tubles étant donnés:
- les valeurs du tuple calculées jusque là (initialement vide)
- le nombre d'éléments restant à ajouter dans le tuple
- la somme des valeurs qui restent à rajouter

Je l'ai fait en Python qui est assez explicite. Je te laisse le traduire dans le language que tu veux.

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Compute all n-tuples with given sum, starting with the optional tuple values
# Found tuples are added to result
def get_tuples_with_sum(result, n, sum, tuple=[]):
    if len(tuple) == n:
        # Stop recursion when the tuple is complete, and then the sum should be null
        if sum == 0:
            result.append(tuple.copy())
        return
    for x in range(sum + 1):  # between 0 and sum included
        tuple.append(x)
        get_tuples_with_sum(result, n, sum - x, tuple)
        tuple.pop()
 
 
result = []
get_tuples_with_sum(result, 4, 4)
for X in result:
    print(X)

[qi130]

Hello à tous les répondants.

Pressé par le temps, j'ai mis en oeuvre la solution proposée par Anapurna.
L'optimisation proposée tbc suggère des votes négatifs je me suis sûrement trompé

Je clos le sujet, mais pas la récursivité...
J'y reviendrai à tête reposée pour ma satisfaction intellectuelle.

Merci à AbsoluteLogic pour son algo