Simplification de combinaisons (k parmi i) parmi n

[nylon81]

Bonjour,
J'aimerais savoir s'il est possible (par un code ou autre) de simplifier des combinaisons de k parmi n, avec des combinaisons de k parmi i sans répétition, tous des entiers naturels k:[2;5], i:[3;6], n:[7;12] , kSi oui combien de combinaison k parmi i est-il possible d'obtenir au maximum ?


Soit par généralisation pour k:[2;5], i:[3;6], n:[7;12] , kEksurn l'ensemble des combinaisons de k parmi n.
Soit n, soit k, je cherche pour i entier naturel i:[3;6]: a(i), Eksuri et Eresteksurn tel que
Eksurn soit la somme directe de i:[3;6] Eksuri et de Eresteksurn
où chaque Eksuri se décompose lui même en un nombre a(i) de sous espace.
où Eresteksurn représente l'ensemble supplémentaire des combinaisons qui n'ont pas été pris en compte dans les Eksuri.
Je cherche à déterminer les i éléments appartenant à [1;12] et le nombre de fois a(i) que différents éléments (: au moins i-k+1) ont été pris, ainsi que l'ensemble Eresteksurn énumérant l'ensemble des combinaions restantes.

Avec la condition supplémentaire si possible:
Imaginons 2 possibilités de réduction, chaque combinaison trouvée compte pour ((k parmi i) -1), la solution envisagée sera celle contenant le plus grand ((k parmi i) -1).



Je m'explique :
Pour k=2, i=3, 4, 5, 6, et n=12
Pour la combinaison 2 parmi 12, j'aimerai donc la simplifier un maximum en combinaisons 2 parmi 3 et/ou 2 parmi 4 et/ou 2 parmi 5 et/ou 2 parmi 6.
J'ai un fichier texte regroupant les 66 combinaisons, s'il peut être utile.
En supplément j'aimerai la condition:
Si au maximum on obtient d'une façon 2*(2 parmi 6) et 1*(2 parmi 5) dans un premier temps et dans un second temps 2*(2 parmi 6) et 3*(2 parmi 4), je préférerais la seconde solution car elle m'offrira une réduction de 2*15+3*6=48 combinaisons contre 2*15+1*10=40, soit une différence de 8 supérieure au nombre de combinaison supplémentaire qu'elle m'a demandé (2).

En somme, soit E2sur12 l'ensemble des combinaisons de 2 parmi 12 je cherche pour i entier naturel i:[3;6], a(i), E2suri et E tel que
E2sur12 soit la somme directe de E2sur3 + E2sur4 + E2sur5 +E2sur6 + Ereste2sur12
où chacun des E2sur3 , E2sur4 , E2sur5 , E2sur6 , Ereste2sur12 se décompose lui même en un nombre respectif a(3) , a(4), a(5) , a(6) de sous espace.


J'ai des bases en langage C et VBA.
J'ai commencé à la mian sur un bout de papier mais les erreurs sont récurentes sans méthodes bien élaborées puis je n'arrive pas à rédiger un code en VBA pour les obtenir (même sans la condition supplémentaire).
Je comprends tout raisonnement d'un niveau de mathématiques maths sup et maths spé.
Pouvez-vous détailler la démarche à suivre ou me laisser un bout de code pour m'aider à résoudre ce problème.


Merci par avance de votre aide.

Cordialement.

[fatal_error]

salut,

pour moi c'est pas clair

Pour k=2, i=3, 4, 5, 6, et n=12
Pour la combinaison 2 parmi 12, j'aimerai donc la simplifier un maximum en combinaisons 2 parmi 3 et/ou 2 parmi 4 et/ou 2 parmi 5 et/ou 2 parmi 6.

c'est quoi ta règle de simplification

J'ai un fichier texte regroupant les 66 combinaisons, s'il peut être utile.

pas toutes, mais au moins écrire quelques une en exemple serait bien

En supplément j'aimerai la condition:
Si au maximum on obtient d'une façon 2*(2 parmi 6) et 1*(2 parmi 5) dans un premier temps et dans un second temps 2*(2 parmi 6) et 3*(2 parmi 4), je préférerais la seconde solution car elle m'offrira une réduction de 2*15+3*6=48 combinaisons contre 2*15+1*10=40, soit une différence de 8 supérieure au nombre de combinaison supplémentaire qu'elle m'a demandé (2).

je comprends pas comment tu décomposes tes Eksurn en a(i) Eksuri et Ekrestesurn
par ex je vois pas d'ou ca sort 2 parmi 6, ni comment tu déduis tes Ekrestesurn

Et aussi Eksurn c'est quoi un nombre, un ensemble?
si c'est un ensemble que représente ta "somme directe" ?

[nylon81]

Grosso modo pour n=12 k=2,
Supposons les chiffres 1,2,3,4,5,6,7,8,9,10,11,12 le 2 parmi 12 va nous donner les 66 combinaisons suivantes: {1;2}{1;3}{1;4}...{10;11}{10;12}{11;12} qui correspond à l'ensemble des combinaisons 2parmi12: E2sur12, je veux retrouver le maximum de paire {a;b} a et b entre 1 et 12 appartenant à l'ensemble ci-dessus.
Pour cela je ne peux que m'aider de k appartenant à [3;6] pour les possibilités de combinaisons créées 2parmi3, 2parmi4, 2parmi5, 2parmi6
Pour i=6 je divise en deux catégories : 1,2,3,4,5,6 et 7,8,9,10,11,12. j'applique alors le 2 parmi 6 qui me génère les combinaisons {1;2}{1;3}{1;4},...{5;6} et {7;8}{7;9}{7;10}...{10;11}{10;12}{11;12} ce qui correspond à 2*15 combinaisons donc a(i) pour i=6: a(6)=2, il me reste alors 36 combinaisons (66-2*15) appartenant à E2sur12.
Je me rends compte ici que je ne peux pas réduire à nouveau que ce soit avec un 2sur6 ou autre 2suri donc j'obtiens pour i=6 30 combinaisons de réduites.

Si j'essaie pour i=5, intuitivement je divise en deux groupes: 1 jusqu'à 5 et 6 jusqu'à 10. j'obtiens alors les combinaisons : {1;2}{1;3}{1;4}...{4;5} et {6;7}{6;8}{6;9}...{9;10} je réduis ici de 20 combinaisons, je me rends compte également que je peux composer à l'aide de 2sur3 (i=3): en prenant les deux nombres que je n'ai pas utilisés 11 et 12: pour 1;6;11 j'obtiens les possibilités {1;6}{1;11}{6;11} ainsi que pour 2;7;11 ainsi de suite jusqu'à 5;10;11. Le nombre 12 est neutre ici et je ne peux m'en servir.

Ici j'ai donc réduit de : 20 combinaisons pour i=5 a(5)=2; ainsi que de 15 combinaisons (3*5) pour i=3 a(3)=5, ce qui me fait un total de 35 combinaisons réduites.
Je me rends compte alors que je simplifie et réduit plus en utilisant la solution combinée i=5;i=2 qu'en utilisant la solution i=6 (30 combinaisons de réduites).

La condition donne ici : 35-30 = 5 combinaisons de réduites de la première méthode à l'autre, j'additionne les a(i) pour chacune des solutions: a(5)+a(3)=2+7=7 et nous avons pour l'autre solution a(6)=2. On se rapproche de l'ensemble E2sur12 pour les deux solutions:
pour i=5;i=3 31 combinaisons simples restantes avec a(5)+a(3)=7, pour i=6 36 combinaisons simples restantes avec a(6)=2
Pour choisir la bonne solution on choisit la solution ayant la valeur la plus petite : 31+a(5)+a(3)=31+7=38 = 36+a(6)=38
Donc il n'y a pas de solutions préférentielles ici.
Ceci fait figure d'exemple, il faudrait étudier les cas i=4 combiné peut-être avec i=3 permettant d'obtenir encore plus de réductions.
J'ai détaillé la condition mais elle n'est pas fortement exigée il me faut juste avoir un maximum de combinaisons réduites.

Dans ce cas si j'opte pour la solution avec i=5 et i=3:
E2sur12=E2sur3+E2sur5+Ereste2sur12

Nous voyons qu'aucun élément des ensembles E2sur3 et E2sur5 ne se croisent l'intersection est vide car
E2sur3=({1;6}{1;11}{6;11}......{5;10}{5;11}{10;11}) il y a dans cet ensemble 15 couples {a;b}
E2sur5=({1;2}{1;3}{1;4}...{4;5}{6;7}{6;8}{6;9}...{9;10}) il y a dans cet ensemble 20 couples {a;b}
Ereste2sur12= ({1;7}{1;8}........{10;12}{11;12}) il y a dans cet ensemble 31 couples {a;b} à TROUVER

J'espère avoir été clair :)

[fatal_error]

ok je pense avoir compris.
si j'abstrais ton algo, alors on veut:

Code: Tout sélectionner

pour une liste L de k-uplons obtenus par les C(n,k) elem piochés dans {1,...,n}
choisir des combinaisons telles que
 # pour chaque combinaison choisie
  - la combinaison est de type C(i,k) avec i dans {3,..,6}
  - l'ensemble des k-uplons générés ne contient aucun k-uplons générés par une autre combinaison choisie
  - chaque entier du k-uplon généré appartient à {1,...,n}
 # le nombre de tous les k-uplons générés soit maximal

[fatal_error]

par rapport à i dans {3,6}, k==2 et n==12
on peut utiliser les C(3,2) (chaque ligne correspond à une combi de type C(3,2) assez évidente)

Code: Tout sélectionner

{9,10},{9,11},{10,11}
{7,8},{7,11},{8,11}
{6,8},{6,10},{8,10}
{6,7},{6,9},{7,9}
{5,8},{5,9},{8,9}
{5,7},{5,10},{7,10}
{4,6},{4,11},{6,11}
{3,5},{3,11},{5,11}
{3,4},{3,10},{4,10}
{2,5},{2,6},{5,6}
{2,4},{2,9},{4,9}
{2,3},{2,8},{3,8}
{1,4},{1,8},{4,8}
{1,3},{1,9},{3,9}
{1,2},{1,11},{2,11}
{0,4},{0,7},{4,7}
{0,3},{0,6},{3,6}
{0,2},{0,10},{2,10}
{0,1},{0,5},{1,5}



la condition de paires qui se répètent pas vient du fait qu'entre deux lignes quelconques il y a au plus un seul élément en commun.

de la à montrer que c'est en prenant le plus petit i que ca marche je sais pas :hum: , mais déjà en ne prenant que le plus petit i, c'est pas trivial :triste:

[nylon81]

Tu as compris ce que je voulais :) je me doute bien que le problème devient très complexe pour un n donné un k donné et trouver les bons i.
Restreignons-nous à un % de réduction soit maximal finalement: ici tu as trouvé 19*3/66 =86% c'est parfait.

Je vais également me restreindre à un seul i, et trouver le i entre 3 et 6 pour lequel j'obtiens le max de réduction.
Tu les as trouvé par programmation j'imagine, j'ai du mal à programmer notamment lorsque je lui indique que seulement un élément change entre deux lignes QUELCONQUES. Tu peux me laisser un bout de code pour les trouver ?

[fatal_error]

le code qui génère ca est copié collé de http://www.maths-forum.com/showthread.php?t=156862&page=1&highlight=intersecting
19/08/2014, 17h06

le seules différences est
--m[i][j] = ((l[i]*l[j])();
++compute();

tu as la description de l'algorithme dans la même discussion

[TheReveller]

Bonjour,

Je ne saurais prouver ce que j'avance, mais je crois que ce qui te permettra toujours de maximiser ta "réduction" sera d'utiliser le plus petit "i" puisque c'est lui qui te permettra d'obtenir le plus de sous-groupes. Peut-être que mettre un peu d'efforts sur les théories des ensembles pourrait permettre d'en tirer des conclusions.

Par exemple, pour ton cas de 2 parmi 12, si j'effectue du 2 parmi 3 à l'aide de ces 17 sous-groupes (à titre indicatif seulement, le nombre de sous-groupes dépend de la technique employée, sinon il faut optimiser [il est en fait possible de faire 18 sous-groupes, même 19, et voire même 20!]) :

Code: Tout sélectionner

     1     2     3
     1     4     5
     1     6     7
     1     8     9
     1    10    11
     2     4     6
     2     5     7
     2     8    10
     2     9    11
     3     4     7
     3     5     6
     3     8    11
     3     9    10
     4     8    12
     5     9    12
     6    10    12
     7    11    12

Alors j'obtiens ces 51 paires (parmi les 66 paires possibles) :

Code: Tout sélectionner

     1     2
     1     3
     2     3
     1     4
     1     5
     4     5
     1     6
     1     7
     6     7
     1     8
     1     9
     8     9
     1    10
     1    11
    10    11
     2     4
     2     6
     4     6
     2     5
     2     7
     5     7
     2     8
     2    10
     8    10
     2     9
     2    11
     9    11
     3     4
     3     7
     4     7
     3     5
     3     6
     5     6
     3     8
     3    11
     8    11
     3     9
     3    10
     9    10
     4     8
     4    12
     8    12
     5     9
     5    12
     9    12
     6    10
     6    12
    10    12
     7    11
     7    12
    11    12

À moins que j'aie mal compris un aspect, ou, comme je dis, mon commentaire reste hypothétique.

Ou peut-être que pour ta formule, le maximum se trouve ailleurs, mais c'est que ta formule de comparaison semble additionner des pommes avec des oranges :

Par exemple :
31 (paires restantes) + 5 (sous-groupes utilisés) + 2 (sous-groupes utilisés) = 38 [type d'unité ??]
36 (paires restantes) + 2 (sous-groupes utilisés) = 38 [type d'unité ??]

Pour ce que je t'ai donné, ce serait donc :

15 (paires restantes) + 17 (sous-groupes utilisés) = 32

J'aurais plutôt vu une formule de comparaison uniquement basée sur le nombre de paires restantes, non ?

[nylon81]

Tu as bien compris le pb TheReveller,
et je me suis limité au i le plus petit (sinon le pb devient extrêmement compliqué et il nécessite une puissance folle du PC) donc pour l'exemple 2 parmi 12 je n'ai utilisé que des 3 sur 12. j'ai réussi à récupérer toutes les combinaisons de 3 éléments parmi 12 où parmi ces 3 éléments aucun n'avait deux éléments en commun.
En code VBA j'ai donc utilisé la technique suivante:
-Récupérer tous les 2 parmi 12 = Liste 1 : 66
-Récupérer tous les 3 parmi 12 = Liste 2 : 220
-Faire une boucle sur la Liste 1 dans laquelle se trouve une nouvelle boucle sur la Liste 2 où je récupère sur une Liste 3 l'ensemble des triplets de la Liste 2 qui vérifient la condition souhaitée = Liste 3 : 17
-Faire une nouvelle Liste 4 qui me donne tous les duo qui ne sont pas compris dans la Liste 3 = Liste 4 : 15

(Pour information : 17*3+15=66)

Merci pour vos réponses fatal_error & TheReveller