Discussion :

[Jlmat]

Bonjour,

J'essaye de trouver le bon formalisme mathématique pour résoudre mon problème. Il s'agit d'un problème de dénombrement.

1. Pour simplifier on peut l'assimiler à un jeu de N bâtons que je dois distribuer sur n-emplacements nE. Combien ai-je de possibilités théoriques de diviser en nR Regroupements mes bâtons sur les nE Emplacements.
prenons un exemple:
N = 4 bâtons
nE = 7 emplacements possible pour chaque bâtons

Je mets une image de quelques possibilités de regroupements possibles:




C'est un peu loin pour moi, cette affaire. Je suis sans doute dans le cas d'un choix simultané sans ordre et sans répétition. Êtes-vous d'accord?

Donc, j'utiliserai pour ça un arrangement A



2. Mais mon problème, c'est que je veux un seul vide entre les paquets de bâtons et non pas plusieurs comme dans la première image.

Par exemple, si je prends deux groupes de bâtons, je veux obtenir les partitions suivantes:



Je n'ai donc que 5 possibilités.

On a Nb = 4 Bâtons pour nE emplacements = 5 car je suis obligé de mettre un emplacement vide pour séparer les deux Paquets => nP = 2, donc nE = Nb + (nP -1) = 4 + (2 - 1) = 5
Si je veux maintenant trois paquets, il me faut deux intervalles => Nb = 4 bâtons ; nE = 4 + (3 - 1) = 6 emplacements etc...

Il semble que l'ordre des intervalles entre en compte, je suis donc parti sur une Combinaison plutôt qu'un Arrangement. J'ai bien essayé la formule suivante, mais le résultat n'est pas bon :

N = C₅⁴ + C₄³ + C₄² = 5 + 4 +3

L'image ci-dessus traite un groupe avec 1 seul bâton, mais en réalité, il faudrait des groupes de 2 bâtons minimum pour faire un groupe. Il faudrait peut-être que je trouve tous les groupes possibles et que je soustrais ce qui ne convient pas. Comment traiter ce problème?

Merci d'avance pour votre aide

[tbc92]

Tu parles de combinaisons et d'arrangements.
Ca me fait penser à un bricoleur qui aurait une super perceuse électrique et un super poste de soudure... et qui demanderait : pour planter un clou, je prends quel outil ?
Il a un marteau classique, mais il veut utiliser les outils qu'il a payés très chers.
Tu as galéré pour apprendre les combinaisons et les arrangements, et donc, tu ne veux plus faire d'addition ni de multiplication. Comme mon bricoleur.

Tu as des vides et des batons. 1 vide pour 4 batons dans le premier dessin.
a vides et b batons en général.

On va regarder les formes autorisées dans un premier temps.
Il y a 6 formes autorisées si j'ai bien suivi
-A- a1 vides + b1 batons+ a2 vides + b2 batons + a3 vides , avec a1+a2+a3=a et b1+b2=b
-B- a1 vides + b1 batons+ a2 vides + b2 batons , avec a1+a2 =a et b1+b2=b
-C- b1 batons+ a1 vides + b2 batons + a2 vides , avec a1+a2=a et b1+b2=b
-D- b1 batons+ a vides + b2 batons , avec b1+b2=b
-E- a1 vides + b batons + a2 vides , avec a1+a2=a
-F- a vides + b batons
J'espère que je n'en ai pas oublié.
Dans tous ces trucs, a1, b1,a2 b2, a3 ne peuvent pas être nuls, sinon on aura des double-comptes.
Pour chacun des cas, on va ensuite compter en détail.
Par exemple, pour les 3 premières formes, de combien de façons peut on choisir b1 et b2, tous les 2 non nuls pour que b1+b2=b. Il y a b-1 façons.
Pour la forme A, de combien de façon peut-on choisir a1, a2 et a3 pour avoir a1+a2+a3=a ; ... pas simple, allez : (a-2)(a-1)/2
Donc pour la forme A, on a (a-2)(a-1)(b-1)/2 façons de choisir a1,a2,a3,b1,b2

Etc,il faut calculer les autres configurations, puis additionner tout ça.

Peut-être qu'au final, on va retomber sur un résultat 'connu', mais je ne crois pas.

Si tu veux que chaque groupe contienne au moins 2 éléments, alors
Pour la forme A
ça n'a pas d'impact sur le calcul du nombre de façons de choisir a1,a2, a3 puisque un vide peut-être seul.
Et au lieu de b-1, c'est b-3 façons de choisir b1 et b2.

Donc (a-2)(a-1)(b-3)/2

Etc etc.

[Flodelarab]

Bonjour

Je suis sans doute dans le cas d'un choix simultané sans ordre et sans répétition. Êtes-vous d'accord?

Oui.

Donc, j'utiliserai pour ça un arrangement A

Argh. Je m'étrangle. J'aurais aimé lire "Donc j'utiliserai une combinaison". L'arrangement est avec l'ordre. La combinaison, sans ordre.

2. Mais mon problème, c'est que je veux un seul vide entre les paquets de bâtons et non pas plusieurs comme dans la première image.
(...)
Comment traiter ce problème?

Déjà, commence par donner un énoncé qui ne change pas toutes les 3 lignes. Quel est le vrai énoncé complet ?

À partir de N bâtons, tu veux le nombre de dispositions de k groupes de 2 batons au moins, séparés par un trou. C'est bien ça ?

[Jlmat]

Merci tbc92 d'avoir pris le temps de répondre

Tu parles de combinaisons et d'arrangements.
Ca me fait penser à un bricoleur qui aurait une super perceuse électrique et un super poste de soudure... et qui demanderait : pour planter un clou, je prends quel outil ?
Il a un marteau classique, mais il veut utiliser les outils qu'il a payés très chers.

C'est à dire que je cherche la structure de contrôle d'un enchaînements de tests. Donc j'ai plusieurs paramètres sur lesquels je dois jouer. Mes cours de stat remontent à 40 ans,

Je l'ai modélisé ici de manière simplifié. Les Bâtons sont des critères à prendre en compte dans les tests que je dois effectuer. Seul compte le nombre de critères par groupe (au moins 2 critères) par groupe de test à effectuer.
Donc en fait j'ai pris 7 emplacements (4 Bâtons + 3 Vides) parce que j'avais 4 bâtons. Ce qui m'intéresse, ça n'est pas la cardinalité dans chaque groupe des critères bi, mais le nombre de groupe que je peux faire : b1,b2...bi séparés par un vide pour matérialiser le groupe. => l'arrangement ou répartition des vides (a dans ta notation) ne m'intéresse pas, c'est fictif. ça se traduira dans un programme par une fon de boucle.
Par contre, la somme des critères bi doit toujours être le même, ici b = 4.

Par ailleurs, je dois pouvoir envisager plus tard, plus de 2 groupes. Dans ta simulation avec tes 6 configurations A...F, les configurations A,B,C,D envisagent deux groupes de critères b. Les configurations E et F ne répondent pas à la solution car E et F ne possèdent qu'un seul groupe b (bâtons).

-A- a1 vides + b1 batons+ a2 vides + b2 batons + a3 vides , avec a1+a2+a3=a et b1+b2=b
-B- a1 vides + b1 batons+ a2 vides + b2 batons , avec a1+a2 =a et b1+b2=b
-C- b1 batons+ a1 vides + b2 batons + a2 vides , avec a1+a2=a et b1+b2=b
-D- b1 batons+ a vides + b2 batons , avec b1+b2=b
-E- a1 vides + b batons + a2 vides , avec a1+a2=a
-F- a vides + b batons
J'espère que je n'en ai pas oublié.

Non pas d'oubli car l'emplacement vers la gauche ou vers la droite des bi n'a pas d'importance.

Par exemple, pour les 3 premières formes, de combien de façons peut on choisir b1 et b2, tous les 2 non nuls pour que b1+b2=b. Il y a b-1 façons.

Oui, c'est ce que j'avais trouver avec les couples B = {(1,3) , (2,2) , (3,1)}

Si tu veux que chaque groupe contienne au moins 2 éléments, alors
Pour la forme A
ça n'a pas d'impact sur le calcul du nombre de façons de choisir a1,a2, a3 puisque un vide peut-être seul.
Et au lieu de b-1, c'est b-3 façons de choisir b1 et b2.

Donc (a-2)(a-1)(b-3)/2

Ok, tout ça me paraît juste, je voudrais trouver une formule qui synthétise tout ça en prenant des petites valeurs pour vérifier plus facilement :

Soit NB = nombre bâtons (critères) total = 10
NG = nombre de groupements de critères maximum des processus 2 à 4
NC = nombre de critères minimum par groupement = 2
Objectif = Vérification de tous les critères des couples B2 = { (b1,b2) ... (bi,bj) }
Vérification de tous les critères des triplets B3 = { (b1,b2,b3)...(bi,bj,bk)}
Vérification de tous les critères des quadruplets B4 = { (b1,b2,b3,b4)...(bi,bj,bk,bl)}

Est-ce que je peux prendre ton raisonnement pour y parvenir? Bon, on va voir ça plus tard!

merci

[Jlmat]

Merci Flodelarab

Aie! j'étais en train de plancher sur la réponse de tbc92 quand tu as répondu!

A la fin de ma réponse à tbc92, j'essaye de reformuler simplement mon problème...

Oui, c'est ça, le nombre de 2, 3 ou n bâtons dans un ou plusieurs groupes de bâtons ensemble NB Bâtons

[Flodelarab]

Tu vas rire : c'est Fibonacci. La suite de Fibonacci. La célébrissime suite de Fibonacci.

Ton premier groupe commence forcément par 2 bâtons. Pour chaque bâton suivant, il faut déterminer s'il renforce le groupe actuel, ou s'il commence un nouveau groupe. Dans ce dernier cas, le bâton suivant renforce obligatoirement le groupe, puisqu'il ne faut pas de groupe de 1. Le processus revient donc à choisir 1 ou 2 pour chacun des N-2 bâtons. J'appelle f la fonction de dénombrement, et n, le nombre de bâtons restant. On a:

• Si n==1, f renvoie 1 (le bâton renforce le groupe actuel)
• Si n==2, f renvoie 2 (soit les 2 bâtons renforcent le groupe actuel, soit les 2 bâtons forment un nouveau groupe)
• Si n>2, f(n)=f(n-2)+f(n-1) (Idem sauf que le processus continue après la détermination du bâton actuel)

Les valeurs sont donc : 1; 2; 3; 5; 8; ... etc Fibonacci !

Je rappelle qu'on considère f(N-2) et pas f(N). J'appelle g, la fonction finale. On obtient :
g(1) impossible
g(2)=1
g(3)=1
g(4)=2
g(5)=3
g(6)=5

Listons les 5 possibilités pour 6 bâtons :
XX XX XX
XX XXXX
XXX XXX
XXXXXX
XXXX XX
Il semble bien que nous les ayons tous.

Bonne chance

[Jlmat]

Tu vas rire : c'est Fibonacci. La suite de Fibonacci. La célébrissime suite de Fibonacci.
Bonne chance

Super Flodelarab

Je tiens le bon Bout!

Je vérifie ça plus tard

merci

[Jlmat]

Hello,

En attendant de vérifier si c'est bien la solution que je cherche, je vous donne une procédure que j'ai écrite en Lazarus pour calculer le n ième terme de la suite de Fibinacci :

Code :

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
19
20
21
 
{--- Finobacci -----------------------------------------------------------------
 Donne la valeur de la suite de Fonibacci au n ième terme
--------------------------------------------------------------------------------}
function fNiemeFinobacci(n : LongInt): LongInt;
 var i, Fi,A,B : longint;
begin
  A := 1; B := 1; Fi := 1;
  if n < 2
  then result := Fi
  else
  begin
    For i := 2 to n do
    begin
      Fi := A + B;
      A := B;
      B := Fi;
    end;
    result := Fi;
  end
end;

[Flodelarab]

Euh ... c'est mignon, mais il y a une formule, que tu peux retrouver sur l'oeis (clique ici).



Version Libre Office Calc: (case B1, rang en A1)

Code :

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

=((1/2+RACINE(5)/2)^A1 - (1/2-RACINE(5)/2)^A1)/RACINE(5)

[Guesset]

Bonjour,

Il est possible de simplifier le code en utilisant le fait que la boucle n'est pas exécutée si la borne de fin est inférieure à la borne de début.

Code PAS :

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

1
2
3
4
5
6
7
8
9
10
function Fibonacci(n : LongInt): LongInt;
var i, u, u1 : longint;
begin
   u := 1; u1 := 1;
   for i := 2 to n do begin
      u += u1;
      u1:= u - u1;
      end;
   result := u;
end;

La formule rappelée par Flodelarab sera intéressante dès que les valeurs seront moindrement importantes car racines, exponentiations, divisions et conversion en entier prennent un peu de temps.

Salutations

[Jlmat]

Merci à vous deux

Merci Guesset pour la simplification de mon code...

=Flodelarab;Euh ... c'est mignon, mais il y a une formule, que tu peux retrouver sur l'oeis.

Oui, elle est chouette ta formule Flodelarab, mais j'ai tendance à me méfier des calculs avec des nombres irrationnels car comme le dis Guesset, au final, je vais avoir un nombre important de possibilités: peut-être entre 50 et 100 bâtons => plusieurs milliers de tests.
C'est peut-être négligeable avec les logiciels maintenant. Je vais peut être faire un test sur 100 000 appels pour comparer les deux formules. D'ailleurs, avec des LongInt, je suis limité au 60ième terme de la suite dans la fonction, ce qui est peut-être contourné par la formule de Flodelarab! A vérifier.

Par contre ton lien sur l'oeis est très intéressant et va me servir pour des vérifications de ma grande procédure car je dois isoler toutes les possibilités par groupe identifié : n = 2, 3, 4... NB (NBâtons ou critères).

A suivre

[Jlmat]

J'ai fait un test de boucle de 0 à 100 pour détecter une divergence entre les deux formules:

Ma formule itérative rectifiée et la formule mathématique avec la racine. J'obtiens une divergence d'une unité sur le 75ème terme:



Bon, je ne sais pas d'où ça viens! Il semble que ça soit du aux limites des fonctions utilisées car sur le calcul du 76ème terme, la formule donne un résultat négatif. je mets donc le code:

Code :

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

1
2
3
4
5
6
7
8
 
{-------------------------------------------------------------------------------
Avec Trunc : Au 10e terme F = 54 au lieu de 55
-------------------------------------------------------------------------------}
function FormuleFibonacci(n : LongInt): LongInt;
begin
  result :=Round( (intPower((1/2+sqrt(5)/2),n) - intPower((1/2-sqrt(5)/2),n) ) / sqrt(5) )
end;

Code pas optimisé, notamment sqrt(5) peut être mis en constante...

Mais il me faudra sans doute aborder le problème car, même si j'ai fixé une limite du nombre de critères (bâtons) au max égale à 100 (NBmax), car dans ma recherche de toutes les possibilités avec deux groupes et 100 bâtons, je peux avoir un groupe à 5 bâtons et l'autre à 95, donc > 75...
D'ailleurs, la valeur Max de LongInt est de 2 147 483 647, donc normalement ça devrait planter avant. Mais bon, ici on parle de maths, je verrais les problèmes de variables limites après...

Je vais replancher sur l'Algo de départ, à savoir lister tous les couples ou n-uplets des groupes de bâtons...

[Jlmat]

Je vais replancher sur l'Algo de départ, à savoir lister tous les couples ou n-uplets des groupes de bâtons...

C'est bon en fait, Flodelarab a trouvé la bonne formule, le listage des n-uplets n'étaient pas dans ma question algo de départ. Je vais donc y réfléchir en partant sur un tableau de booléens sans doute pour dispatcher les différents groupes de bâtons...

Si j'ai des difficultés, je reviendrais vers vous

Merci

[Guesset]

Bonjour Jimat

...Bon, je ne sais pas d'où ça viens! Il semble que ça soit du aux limites des fonctions utilisées car sur le calcul du 76ème terme, la formule donne un résultat négatif...

Si le second terme tend vers 0 le premier est supérieur à deux fois (2.236 fois) le résultat attendu, il y a donc un risque de dépassement de capacité (en fait surtout un problème de précision du à l'usage implicite de simple float). Des valeurs précalculées affectées à des double voire des extended pourraient résoudre le problème sous réserve que les fonctions utilisées possèdent une variante avec ces types d'arguments.

Un autre approche serait d'utiliser l'exponentiation de Dijkstra en tirant partie de fait que la formule utilise deux formes du nombre d'or et donc a²= a + 1.

Il y a toujours 1000 façons de tondre un œuf .

Salut

[Jlmat]

Si le second terme tend vers 0 le premier est supérieur à deux fois (2.236 fois) le résultat attendu, il y a donc un risque de dépassement de capacité (en fait surtout un problème de précision du à l'usage implicite de simple float). Des valeurs précalculées affectées à des double voire des extended pourraient résoudre le problème sous réserve que les fonctions utilisées possèdent une variante avec ces types d'arguments.

merci Guesset,

Oui, j'y ai pensé...
Je travaille sur le listage des solutions...

A+