›

Défi pour les matheux

cargocargo Membre
12:13 modifié dans Vos applications #1
Bonjour,

En parallèle à  l'appli coredata que je compte bien réussir à  développer (je commence à  piger cocoa & obj-c), je souhaiterais pouvoir faire la chose suivante avec une petite appli cocoa ou même grâce à  une formule dans un tableau excel, peu importe, seul le résultat compte, toutes les idées et amorces de réflexions sont les bienvenues :

soit une première liste de nombres, par ex :
15 47 22 105 93 38 59

soit une deuxième liste de nombres, par ex:
37 21 212 178 43

Le programme doit être capable de trouver une combinaison de nombres dans la première liste dont la somme est un nombre de la seconde liste.
Il doit pouvoir explorer exhaustivement toutes les combinaisons possibles en cherchant à  "remplir" un maximum de nombres de la seconde liste avec des combinaisons de sommes de nombres de la première liste.
Il ne travaille qu'avec des nombres entiers.

dans l'exemple, voilà  les 2 combinaisons à  trouver :
15 (1ère liste) + 22 (1ère liste) = 37 (2ème liste)
47 + 93 + 38 = 178

Pigé ? C'est de la combinatoire en fait, le programme examine toutes les combinaisons possibles et retient celles qui matchent.

PS: je rembourse les frais de guronzan et d'aspirine à  celui qui trouve comment faire...
(plus sérieusement je serais même prêt à  acheter un tel programme)

«1

Réponses

  • ChachaChacha Membre
    décembre 2005 modifié #2
    C'est un problème d'algorithmique, ça...
    Voici une solution très simple et efficace:

    Comment représenter une somme partiiculière de toutes les sommes possibles ? Avec un ensemble de 0 et de 1 associés à  chaque terme de la liste. Si la liste contient <n> terme, il y a donc 2^n possibilités.
    Pour parcourir toutes les possibilités, il suffit de faire l'analogie avec un nombre en binaire :
    Par exemple, pour 4 termes:
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    ...

    C'est la seule idée utilisée dans ce code... voici donc le code que je propose (pratiquement tout en C)
    <br />//<br />//  Solver.m<br />//  toto<br />//<br />//  Created by Pierre Chatelier on 28/12/05.<br />//  Copyright 2005 __MyCompanyName__. All rights reserved.<br />//<br /><br />#import &quot;Solver.h&quot;<br /><br /><br />@implementation Solver<br /><br />//pour le tri d&#39;un tableau d&#39;entier (sera un parametre de la fonction qsort)<br />int integerComparator(const void* p1, const void* p2)<br />{<br />  return (*(int*)(p1) - *(int*)(p2));<br />}<br /><br />//somme des produits terme a terme<br />int produitScalaire(int* tab1, int* tab2, unsigned int size)<br />{<br />  int result = 0;<br />  unsigned int i = 0;<br />  for(i= 0 ; i&lt;size ; ++i)<br />    result += tab1[i]*tab2[i];<br />  return result;<br />}<br /><br />//recherche &lt;number&gt; dans &lt;tab&gt;<br />//cet algorithme peut etre optimise si tab est trie (recherche dichotomique)<br />BOOL recherche(int number, int* tab, unsigned int size)<br />{<br />  BOOL trouve = NO;<br />  unsigned int i = 0;<br />  for(i = 0 ; !trouve &amp;&amp; (i&lt;size) ; ++i)<br />    trouve = (tab[i] == number);<br />  return trouve;<br />}<br /><br />//tab est un tableau de 0 et de 1 representant un nombre binaire<br />//ici, on l&#39;incremente de 1<br />int incremente(int* tab, unsigned int size)<br />{<br />  unsigned int i = 0;<br />  int retenue = 1;<br />  for(i = 0 ; retenue &amp;&amp; (i&lt;size) ; ++i)<br />  {<br />    if (tab[i])<br />      tab[i] = 0;<br />    else<br />    {<br />      tab[i] = 1;<br />      retenue = 0;<br />    }<br />  }<br />  return retenue;<br />}<br /><br />//simplement afficher un resultat (c&#39;est basique)<br />void report(int sum, int* numbers, int* factors, unsigned int size)<br />{<br />  printf(&quot;%d = &quot;, sum);<br />  unsigned int i = 0;<br />  for(i = 0 ; i&lt;size ; ++i)<br />  {<br />    if (factors[i])<br />      printf(&quot;%d+&quot;, numbers[i]);<br />  }<br />  printf(&quot;&#092;n&quot;);<br />}<br /><br />//resoudre<br />-(IBAction) solve:(id)sender<br />{<br />  //d&#39;abord, creer les listes de nombres, triees<br />  //on suppose que list1TextField et list2TextField sont reliés à  des éléments de l&#39;interface avec<br />  //des IBOutlet<br />  NSArray* list1OfStrings = [[list1TextField stringValue] componentsSeparatedByString:@&quot; &quot;];<br />  NSArray* list2OfStrings = [[list2TextField stringValue] componentsSeparatedByString:@&quot; &quot;];<br /><br />  unsigned int size1 = [list1OfStrings count];<br />  unsigned int size2 = [list2OfStrings count];<br />  <br />  //l&#39;algo travaillera sur des tableaux en C<br />  int* numbers1 = (int*)malloc(size1*sizeof(int));<br />  int* numbers2 = (int*)malloc(size2*sizeof(int));<br />  <br />  //on remplit les tableaux<br />  unsigned int i = 0;<br />  for(i = 0 ; i&lt;size1 ; ++i)<br />    numbers1[i] = [[list1OfStrings objectAtIndex:i] intValue];<br />  for(i = 0 ; i&lt;size2 ; ++i)<br />    numbers2[i] = [[list2OfStrings objectAtIndex:i] intValue];<br /><br />  //on trie les tableaux (le courageux pourra ainsi optimiser la fonction recherche)<br />  qsort(numbers1, size1, sizeof(int), integerComparator);<br />  qsort(numbers2, size2, sizeof(int), integerComparator);<br />        <br />  //maintenant, l&#39;algo<br /><br />  //factors est un tableau de 0 et de 1 representant un nombre binaire<br />  //il a le meme nombre de &quot;bits&quot; que de cases dans &lt;numbers1&gt;<br />  //de ce fait, il represente une des sommes possible du tableau<br />  int* factors = (int*) calloc(size1, sizeof(int)); //initialise a 0<br />  <br />  BOOL fini = NO;<br />  while(!fini)<br />  {<br />    //on calcule la somme correspondant au &lt;factors&gt; courant<br />    int sum = produitScalaire(numbers1, factors, size1);<br />    <br />    //si cette somme est dans le tableau 2...<br />    BOOL trouve = recherche(sum, numbers2, size2);<br />    if (trouve)//...alors on le dit<br />      report(sum, numbers1, factors, size1);<br />      <br />    fini = incremente(factors, size1);//on s&#39;arrete quand factors repasse a 0<br />    //(c&#39;est a dire la retenue n&#39;est pas repassee a 0)<br />  }<br />  <br />  free(numbers1);<br />  free(numbers2);<br />  free(factors);<br />}<br /><br />@end<br />


    Je joint avec un projet XCode qui marche

    +
    Chacha

    PS : s'il y a un bug, n'hesitez pas a m'insulter, mais j'ai essayé de faire un code simple. Je me suis limité au C car tout le monde ne connaà®t pas la STL du C++, mais le code serait plus facile à  écrire pour être vraiment optimal.

    [Fichier joint supprimé par l'administrateur]
  • AliGatorAliGator Membre, Modérateur
    décembre 2005 modifié #3
    Moi j'aurais directement travaillé sur un integer, et optimisé le produit scalaire avec des masques et des shifts. Voici mon implémentation, qui n'utilise que 2 méthodes simples et que du Cocoa.

    si N est le nombre de nombres dans la liste 1 et listeOperandes est le NSArray représentant la liste 1
    soit F le nombre qui, représenté sous forme binaire, dira si on doit ajouter (1) ou non (0) le nombre correspondant. F est donc un integer, mais qu'il faut imaginer comme représenté sous forme d'un nombre binaire de N bits

    (int) partialSumOf:(NSArray*)listeOperandes withMask:(int)F<br />{<br />  int mask = F;<br />  int result = 0;<br />  int N = [listeOperandes count];<br />  for(i=0;i&lt;N;i++)<br />  {<br />    if (mask &amp; 0x01) result =+ [[listeOperandes objectAtIndex:i] intValue];<br />    mask = mask &gt;&gt; 1;<br />  }<br />  return result;<br />}


    mask & 0x01 permet de savoir si le dernier bit (le plus à  droite) de mask est à  1 ou pas, et si oui, on ajoute le i-ème élément de listeOperandes à  result. Comme après on décale mask de 1 bit vers la droite, au prochain coup on regardera encore le bit le plus à  droite de mask, qui sera le 2e bit de F en partant de la droite. et au 3e passage, le 3e bit de F, etc, etc.

    Voilà  donc le code pour le produit scalaire.
    Maintenant il suffit d'initialiser le NSArray* listeOperandes, puis de faire une boucle sur F : 
    NSArray* listeOperandes = ...;<br />NSArray* listeResultats = ...; // on va travailler avec des NSArray de NSString,<br />//puisque ce ne sont que des entiers, il n&#39;y aura pas de risque de comparer @&quot;1.0&quot; avec @&quot;1&quot; et de<br />// croire qu&#39;ils sont différents. Mais sinon on peut faire un NSArray de NSNumber, et<br />// modifier en conséquence la ligne avec containsObject ;)<br /><br />maxF = 1&lt;&lt;[listeOperandes count];<br />int F, somme;<br />for(F=0;F&lt;maxF;F++)<br />{<br />  somme = [self partialSumOf:listeOperandes withMask:F];<br />  if ([listeResultats containsObject:[stringWithFormat:@&quot;%d&quot;,somme]])<br />    [self afficheResultatForList:listeOperandes withMask:F];<br />}
    Bon après le petit plus, la fonction pour afficher un résultat trouvé de façon esthétique (dans le NSLog, à  adapter pour l'afficher dans l'interface)
    <br />(void)afficheResultatForList:(NSArray*)L withMask:(int)M andResult:(int)R<br />{<br />  int i, mask=M, N = [L count];<br />  NSMutableArray* lst;<br />  for(i=0;i&lt;N;i++)<br />  {<br />    if (mask &amp; 0x01)<br />      [lst addObject:[L objectAtIndex:i]];<br />  }<br />  NSLog(@&quot;%@ = %@&quot;,R,[lst componentsJoinedByString:@&quot; + &quot;]);<br />}


    En faisant tout en Cocoa je trouve ça beaucoup plus simple à  écrire, non ? et plus compréhensible/lisible :p ;) Après chacun son choix, et puis Chacha t'as eu le mérite de tester ta soluce, et de fournir le projet Xcode, alors que moi je laisse le soin de faire le copier-coller et de tester :p
  • ChachaChacha Membre
    décembre 2005 modifié #4
    dans 1135804168:

    Moi j'aurais directement travaillé sur un integer

    Oui mais dans ton cas, la liste ne peut pas contenir plus de 32 nombres (disons 64). Par contre, c'est sûr que sous cette contrainte, on peut carrément optimiser.
    Bah, l'intérêt c'était de trouver un algorithme pas trop dur à  écrire. C'était pas mal, cette idée de nombre binaire, non ?
    Par contre, je pense que ce n'est pas optimal d'un point de vue théorique. En effet, le produit scalaire est linéaire, alors que si on ne considérait pas les éléments pondérés par 0, on aurait moins d'opérations. À vue de pif, on perd un logarithme de complexité.
    Mais bon, si c'est suffisant pour l'usage de Cargo...

    [edit]
    Au passage, on peut étendre l'algorithme à  des sommes pondérées. En retouchant un peu la fonction <incremente>, on peut gérer des nombres en base 3, 4, ..., n, ce qui autorise des sommes avec des facteurs 2, 3, ... n-1
    [/edit]
  • cargocargo Membre
    12:13 modifié #5
    Je suis sur le c... !!!!!  <3 <br />BRAVO CHACHA ! En un temps record en plus...
    Incroyable, ça fonctionne très bien, je ne pensais pas que c'était aussi facile à  faire !
    Enfin, "facile", pour toi apparemment, moi je n'ai pas encore tout compris en ce qui concerne l'analogie avec des nombres en binaire.
    Et dire que je me croyais bon en maths (à  l'époque j'ai fait une terminale C)... ::)

    Tu ne peux pas imaginer quel somme de travail "manuel" en moins ça représente !
    Le plus beau cadeau de noël ça, crois moi !!!
    Merci mille fois...

    Je vais tester la solution d'Aligator aussi, mais là  il me faut un peu de temps : je débute en programmation.

    Mais bon puisque c'est trop facile pour vous c'est pas du jeu, compliquons l'histoire pour être pleinement efficace et bâtir un programme véritablement intelligent :

    Voilà  la solution que me renvoie l'appli de chacha pour les 2 listes exemples
    soit une première liste de nombres :
    15 47 22 105 93 38 59
    soit une deuxième liste de nombres :
    37 21 212 178 43
    résultat dans le log :
    37 = 15+22+
    178 = 38+47+93+
    212 = 22+38+59+93+
    212 = 22+38+47+105+

    Le résultat que je retiens "manuellement" est :
    37 = 15+22+
    178 = 38+47+93+
    La somme qui donne 212 ne m'intéresse pas a priori parce que elle utilise dans les 2 combinaisons proposées le 22 et le 38 qui sont déjà  affectés aux sommes 37 et 178
    Donc une condition supplémentaire est : un nombre constituant d'une somme ne peut être utilisé qu'une fois, les sommes doivent représenter des ensembles distincts en fait.
    Donc ici je retiens soit les 2 nombres 37 et 178, soit seulement le nombre 212 avec l'une ou l'autre des combinaisons proposée peu importe.
    Mais la deuxième condition est que mon but est de "remplir" un maximum voire tous les nombres de la 2ème liste donc mon choix final se porte sur 37 et 178 plutôt que sur 212 uniquement.

    Comment modéliser ces 2 conditions ? Peut-être en opérant un tri sur les résultats obtenus avec des conditions adéquates, non ?

    ps1: la limitation à  32 nombres est rédhibitoire
    ps2: je comprends de moins en moins ce qui se dit dans ce thread ;)
  • AliGatorAliGator Membre, Modérateur
    décembre 2005 modifié #6
    En même temps j'ai mis un int, mais tu peux prendre un long, mais aussi gérer une concaténation de longs surtout, pour dépasser la limitation de 32.
    En tout cas ça simplifie à  mon gout l'utilisation d'une fonction incrémente et tout le tatoin.

    Ce que j'aime de ma solution Cocoa c'est que d'une part c'est moins prise de tête (pourquoi convertir ton tableau en tableau C, pour utiliser qsort dessus, définir des fonctions recherche, etc, alors que tout existe déjà  sur les tableaux NSArray de Cocoa ?), et que la fonction incrémente se simplifie aussi, justement. Et puis c'est une solution en 3 fonctions de 8 lignes chacune seulement (y compris la fonction pour afficher proprement le résultat), ce que je trouve plus concis :P

    ---

    Pour résumer le problème, cela revient à  faire le test sur toutes les combinaisons linéaires à  facteur binaire (on se limite à  des multiplicateurs 0 ou 1)
    Par contre chercher la solution qui donne le plus d'utilisations des nombres de la liste 2, là  ça n'est plus vraiment de l'algorithmique, c'est plutôt de l'optimisation mathématique. C'est un peu autre chose.
    Et du coup la solution la plus simple si tu sais que tu n'auras pas des masses de nombres dans tes listes c'est peut-être de chercher toutes les possibilités de combinaisons, et ensuite de filtrer les résultats, plutôt que de chercher à  écrire un code qui sort de suite la solution (d'autant qu'en réalité il peut y avoir plusieurs solutions qui utilisent le même nombre de nombres dans la liste 2)

    ----

    Sinon, pour l'analogie avec un nombre binaire, il faut voir ça comme si tu "cochais" les nombres à  additionner. Imagine ça comme un tableau à  2 colonnes : dans la colonen 1 tu écris tes nombres de la liste 1, et dans la colonne 2 tu coches si oui ou non tu sélectionnes le nombre pour l'addition en cours. Et le tout est de faire toutes les possibilités d'additions possibles, donc toutes les combinaisons possible de cases cochées/décochées.
    Et là  c'est un coup classique d'analogie avec les nombres binaires : si tu imagines un nombre représenté sous sa forme binaire, et que tu associes à  0 une case non cochée (le nombre en face non "sélectionné" pour l'additionà  et à  un 1 une case cochée (nombre sélectionné), il devient simple de parcourir toutes les possibilités.
  • ChachaChacha Membre
    décembre 2005 modifié #7
    dans 1135858234:

    En même temps j'ai mis un int, mais tu peux prendre un long, mais aussi gérer une concaténation de longs surtout, pour dépasser la limitation de 32.

    Je dirais même plus, en C++, on utiliserait un bitset, ou un truc du genre


    Ce que j'aime de ma solution Cocoa c'est que d'une part c'est moins prise de tête (pourquoi convertir ton tableau en tableau C, pour utiliser qsort dessus, définir des fonctions recherche, etc, alors que tout existe déjà  sur les tableaux NSArray de Cocoa ?),

    Pour un c½ur algorithmique comme celui-là , le Cocoa me paraà®t beaucoup trop lourd. On serait obligé de travailler avec des objets, des appels de méthode... c'est drôlement moins efficace. Le C++ est sans-doute le truc le plus adapté à  un c½ur algorithmique (la STL est super pour ça).


    Pour résumer le problème, cela revient à  faire le test sur toutes les combinaisons linéaires à  facteur binaire (on se limite à  des multiplicateurs 0 ou 1)

    Je suis d'accord. Dans la catégorie "pas optimal mais simple", on peut appliquer exactement le même principe ! Je m'explique : ce que tu cherches, parmi toutes les sommes possibles, c'est un sous-ensemble de sommes, le plus grand possible, qui ne mette pas des termes en conflit (utilisation multiple). De ce fait, tu peux représenter un sous-ensemble par un nombre binaire, avec autant de "bits" que tu as trouvé de somme possibles. Et là , même topo : tu testes toutes les combinaisons de sommes, et tu gardes celles pour lesquelles il n'y avait pas de conflit.

    Et comme je suis sympa et que ça m'a amusé, je t'ai même fait le code (Joyeux Noël).
    Alors plusieurs détails :
    -Pour sauvegarder l'ensemble des solutions, j'utilise des NSArray. Mais comme je sauvegarde des pointeurs, j'encapsule ces derniers dans des NSNumber
    -Pour optimiser un peu, le nombre binaire qui représente un sous-ensemble, au lieu de le faire aller de 000....000 à  111...111, je le fais décrémenter de 111...111 à  000...000. De cette façon, on commence par repérer les plus grands sous-ensembles, et on s'arrête quand on ne peut pas faire mieux.
    -Dans mon code, ça complique un peu, mais on garde bien tous les sous-ensemble maximaux de même taille; on n'en privilégie pas un par rapport aux autres. En effet, il peut y avoir plusieurs solutions optimales équivalentes.

    Voilà 

    +
    Chacha

    Le code est ci-après, mais je l'ai aussi joint en attachement sous forme de projet XCode.

    <br />//<br />//&nbsp; Solver.m<br />//&nbsp; toto<br />//<br />//&nbsp; Created by Pierre Chatelier on 28/12/05.<br />//&nbsp; Copyright 2005 __MyCompanyName__. All rights reserved.<br />//<br /><br />#import &quot;Solver.h&quot;<br /><br /><br />@implementation Solver<br /><br />//pour le tri d&#39;un tableau d&#39;entier (sera un parametre de la fonction qsort)<br />int integerComparator(const void* p1, const void* p2)<br />{<br />&nbsp; return (*(int*)(p1) - *(int*)(p2));<br />}<br /><br />//somme des produits terme a terme<br />int produitScalaire(const int* tab1, const int* tab2, unsigned int size)<br />{<br />&nbsp; int result = 0;<br />&nbsp; unsigned int i = 0;<br />&nbsp; for(i= 0 ; i&lt;size ; ++i)<br />&nbsp; &nbsp; result += tab1[i]*tab2[i];<br />&nbsp; return result;<br />}<br /><br />//recherche &lt;number&gt; dans &lt;tab&gt;<br />//cet algorithme peut etre optimise si tab est trie (recherche dichotomique)<br />BOOL recherche(int number, const int* tab, unsigned int size)<br />{<br />&nbsp; BOOL trouve = NO;<br />&nbsp; unsigned int i = 0;<br />&nbsp; for(i = 0 ; !trouve &amp;&amp; (i&lt;size) ; ++i)<br />&nbsp; &nbsp; trouve = (tab[i] == number);<br />&nbsp; return trouve;<br />}<br /><br />//tab est un tableau de 0 et de 1 representant un nombre binaire<br />//ici, on l&#39;incremente de 1<br />int incremente(int* tab, unsigned int size)<br />{<br />&nbsp; unsigned int i = 0;<br />&nbsp; int retenue = 1;<br />&nbsp; for(i = 0 ; retenue &amp;&amp; (i&lt;size) ; ++i)<br />&nbsp; {<br />&nbsp; &nbsp; if (tab[i])<br />&nbsp; &nbsp; &nbsp; tab[i] = 0;<br />&nbsp; &nbsp; else<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; tab[i] = 1;<br />&nbsp; &nbsp; &nbsp; retenue = 0;<br />&nbsp; &nbsp; }<br />&nbsp; }<br />&nbsp; return retenue;<br />}<br /><br />//tab est un tableau de 0 et de 1 representant un nombre binaire<br />//ici, on le decremente de 1<br />int decremente(int* tab, unsigned int size)<br />{<br />&nbsp; unsigned int i = 0;<br />&nbsp; int retenue = 1;<br />&nbsp; for(i = 0 ; retenue &amp;&amp; (i&lt;size) ; ++i)<br />&nbsp; {<br />&nbsp; &nbsp; if (tab[i] == 1)<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; tab[i] = 0;<br />&nbsp; &nbsp; &nbsp; retenue = 0;<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; else<br />&nbsp; &nbsp; &nbsp; tab[i] = 1;<br />&nbsp; }<br />&nbsp; return retenue;<br />}<br /><br />//simplement afficher un resultat (c&#39;est basique)<br />void report(const int sum, const int* numbers, const int* factors, unsigned int size)<br />{<br />&nbsp; printf(&quot;%d = &quot;, sum);<br />&nbsp; unsigned int i = 0;<br />&nbsp; for(i = 0 ; i&lt;size ; ++i)<br />&nbsp; {<br />&nbsp; &nbsp; if (factors[i])<br />&nbsp; &nbsp; &nbsp; printf(&quot;%d+&quot;, numbers[i]);<br />&nbsp; }<br />&nbsp; printf(&quot;&#092;n&quot;);<br />}<br /><br />//effectue un &quot;ET&quot; binaire et renvoie le nombre de &quot;bits&quot; a 1<br />unsigned int binaryAnd(const int* tab1, const int* tab2, int* result, unsigned int size)<br />{<br />&nbsp;  unsigned int sum = 0;//compte le nombre de bits a 1<br />&nbsp;  unsigned int i = 0;<br />&nbsp;  for(i = 0 ; i&lt;size ; ++i)<br />&nbsp;  {<br />&nbsp; &nbsp;  result[i] = tab1[i]*tab2[i]; //le &quot;ET&quot; binaire peut se faire avec une multiplication<br />&nbsp; &nbsp;  if (result[i])<br />&nbsp; &nbsp; &nbsp;  ++sum;<br />&nbsp;  }<br />&nbsp;  return sum;<br />}<br /><br />//compte le nombre de bits a 1<br />unsigned int sumOfBits(const int* tab, unsigned int size)<br />{<br />&nbsp;  unsigned int sum = 0;<br />&nbsp;  unsigned int i = 0;<br />&nbsp;  for(i = 0 ; i&lt;size ; ++i)<br />&nbsp;  {<br />&nbsp; &nbsp;  if (tab[i])<br />&nbsp; &nbsp; &nbsp;  ++sum;<br />&nbsp;  }<br />&nbsp;  return sum;<br />}<br /><br />//resoudre<br />-(IBAction) solve:(id)sender<br />{<br />&nbsp; //d&#39;abord, creer les listes de nombres, triees<br />&nbsp; NSArray* list1OfStrings = [[list1TextField stringValue] componentsSeparatedByString:@&quot; &quot;];<br />&nbsp; NSArray* list2OfStrings = [[list2TextField stringValue] componentsSeparatedByString:@&quot; &quot;];<br /><br />&nbsp; unsigned int size1 = [list1OfStrings count];<br />&nbsp; unsigned int size2 = [list2OfStrings count];<br />&nbsp; <br />&nbsp; //l&#39;algo travaillera sur des tableaux en C<br />&nbsp; int* numbers1 = (int*)malloc(size1*sizeof(int));<br />&nbsp; int* numbers2 = (int*)malloc(size2*sizeof(int));<br />&nbsp; <br />&nbsp; //on remplit les tableaux<br />&nbsp; unsigned int i = 0;<br />&nbsp; for(i = 0 ; i&lt;size1 ; ++i)<br />&nbsp; &nbsp; numbers1[i] = [[list1OfStrings objectAtIndex:i] intValue];<br />&nbsp; for(i = 0 ; i&lt;size2 ; ++i)<br />&nbsp; &nbsp; numbers2[i] = [[list2OfStrings objectAtIndex:i] intValue];<br /><br />&nbsp; //on trie les tableaux (le courageux pourra ainsi optimiser la fonction recherche)<br />&nbsp; qsort(numbers1, size1, sizeof(int), integerComparator);<br />&nbsp; qsort(numbers2, size2, sizeof(int), integerComparator);<br />&nbsp; &nbsp; &nbsp; &nbsp; <br />&nbsp; //maintenant, l&#39;algo<br /><br />&nbsp; //factors est un tableau de 0 et de 1 representant un nombre binaire<br />&nbsp; //il a le meme nombre de &quot;bits&quot; que de cases dans &lt;numbers1&gt;<br />&nbsp; //de ce fait, il represente une des sommes possible du tableau<br />&nbsp; int* factors = (int*) calloc(size1, sizeof(int)); //initialise a 0<br />&nbsp; <br />&nbsp; NSMutableArray* allPossibleSums = [NSMutableArray array];<br />&nbsp; <br />&nbsp; BOOL fini = NO;<br />&nbsp; while(!fini)<br />&nbsp; {<br />&nbsp; &nbsp; //on calcule la somme correspondant au &lt;factors&gt; courant<br />&nbsp; &nbsp; int sum = produitScalaire(numbers1, factors, size1);<br />&nbsp; &nbsp; <br />&nbsp; &nbsp; //si cette somme est dans le tableau 2...<br />&nbsp; &nbsp; BOOL trouve = recherche(sum, numbers2, size2);<br />&nbsp; &nbsp; if (trouve)//...alors on garde cette solution<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; int* solutionAGarder = (int*) malloc(size1*sizeof(int));<br />&nbsp; &nbsp; &nbsp; memcpy(solutionAGarder, factors, size1*sizeof(int));<br />&nbsp; &nbsp; &nbsp; //on conserve le pointeur, encapsulé dans un NSNumber<br />&nbsp; &nbsp; &nbsp; [allPossibleSums addObject:[NSNumber numberWithUnsignedLong:(unsigned long)solutionAGarder]];<br />&nbsp; &nbsp; &nbsp; //on liberera &lt;solution&gt; quand on détruire le tableau &lt;allPossibleSums&gt;<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; <br />&nbsp; &nbsp; fini = incremente(factors, size1);//on s&#39;arrete quand factors repasse a 0<br />&nbsp; &nbsp; //(c&#39;est a dire la retenue n&#39;est pas repassee a 0)<br />&nbsp; }<br />&nbsp; <br />&nbsp; //On a maintenant emmagasine toutes les solutions. Il faut trouver un sous-ensemble<br />&nbsp; //maximal de ces solutions qui ne genere pas de &quot;conflit&quot;<br />&nbsp; //ce sous-ensemble est un masque binaire, encore...<br />&nbsp; unsigned int sizeOfAllPossibleSums = [allPossibleSums count];<br />&nbsp; int* sousEnsemble = (int*) calloc(sizeOfAllPossibleSums,sizeof(int));<br />&nbsp; decremente(sousEnsemble, sizeOfAllPossibleSums);//initialise avec rien que des 1<br />&nbsp; <br />&nbsp; unsigned int tailleDuPlusGrandSousEnsemble = 0;//servira a conserver l&#39;info de la meilleure taille obtenue<br />&nbsp; NSMutableArray* solutionsToKeep = [NSMutableArray array];//plusieurs sous-ensembles pourront atteindre cette taille<br />&nbsp; fini = NO;<br />&nbsp; while(!fini)<br />&nbsp; {<br />&nbsp; &nbsp; unsigned int conflict = 0; //compte le nombre de bits d&#39;un conflit (0 = pas de conflit)<br />&nbsp; &nbsp; <br />&nbsp; &nbsp; //test des conflits<br />&nbsp; &nbsp; int* temp = (int*) calloc(size1, sizeof(int));<br />&nbsp; &nbsp; BOOL premierTerme = YES;<br />&nbsp; &nbsp; for(i = 0 ; !conflict &amp;&amp; (i&lt;sizeOfAllPossibleSums) ; ++i)<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; if (sousEnsemble[i])<br />&nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; int* sommePossible = (int*)[[allPossibleSums objectAtIndex:i] unsignedLongValue];<br />&nbsp; &nbsp; &nbsp; &nbsp; if (premierTerme)<br />&nbsp; &nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; memcpy(temp, sommePossible, size1*sizeof(int));<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; premierTerme = NO;<br />&nbsp; &nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; &nbsp; else<br />&nbsp; &nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; conflict = binaryAnd(temp, sommePossible, temp, size1);<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; memcpy(temp, sommePossible, size1*sizeof(int));<br />&nbsp; &nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; free(temp);<br />&nbsp; &nbsp; <br />&nbsp; &nbsp; //s&#39;il n&#39;y avait pas de conflit, le sous-ensembel actuel est peut etre une solution a garder<br />&nbsp; &nbsp; if (!conflict)<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; //onne garde le sous-ensemble que s&#39;il est meilleur que ceux deja obtenus<br />&nbsp; &nbsp; &nbsp; unsigned int tailleDuSousEnsemble = sumOfBits(sousEnsemble, sizeOfAllPossibleSums);<br />&nbsp; &nbsp; &nbsp; if (tailleDuSousEnsemble &gt;= tailleDuPlusGrandSousEnsemble)<br />&nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; tailleDuPlusGrandSousEnsemble = tailleDuSousEnsemble;<br />&nbsp; &nbsp; &nbsp; &nbsp; int* sousEnsembleAGarder = (int*) malloc(sizeOfAllPossibleSums*sizeof(int));<br />&nbsp; &nbsp; &nbsp; &nbsp; memcpy(sousEnsembleAGarder, sousEnsemble, sizeOfAllPossibleSums*sizeof(int));<br />&nbsp; &nbsp; &nbsp; &nbsp; [solutionsToKeep addObject:[NSNumber numberWithUnsignedLong:(unsigned long)sousEnsembleAGarder]];<br />&nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; <br />&nbsp; &nbsp; //on s&#39;arrete 1) si le prochain sous-ensemble ne pourra qu&#39;etre moins bon<br />&nbsp; &nbsp; // ou&nbsp; &nbsp; &nbsp; &nbsp;  2) quand on a explore toutes les solutions<br />&nbsp; &nbsp; fini = (sumOfBits(sousEnsemble, sizeOfAllPossibleSums) &lt; tailleDuPlusGrandSousEnsemble)<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  || decremente(sousEnsemble, sizeOfAllPossibleSums);//on s&#39;arrete quand on revient a 0<br />&nbsp; }<br />&nbsp; <br />&nbsp; //affichage des solutions<br />&nbsp; NSEnumerator* enumerator = nil;<br />&nbsp; NSNumber* adresse = nil;<br /><br />&nbsp; enumerator = [solutionsToKeep objectEnumerator];<br />&nbsp; while((adresse = [enumerator nextObject])) //onj parcourt tous les sous-ensembles qu&#39;on a gardes<br />&nbsp; {<br />&nbsp; &nbsp; int* sousEnsemble = (int*) [adresse unsignedLongValue];<br />&nbsp; &nbsp; if (sumOfBits(sousEnsemble, sizeOfAllPossibleSums) == tailleDuPlusGrandSousEnsemble) //s&#39;il est maximal<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; for(i = 0 ; i&lt;sizeOfAllPossibleSums ; ++i)<br />&nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; if (sousEnsemble[i])<br />&nbsp; &nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int* solution = (int*) [[allPossibleSums objectAtIndex:i] unsignedLongValue];<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int somme = 0;<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; unsigned int j = 0;<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(j = 0 ; j&lt;size1 ; ++j)<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (solution[j])<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; somme += numbers1[j];<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf(&quot;%d+&quot;, numbers1[j]);<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf(&quot;=%d&#092;n&quot;, somme);<br />&nbsp; &nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; }//fin du parcours du sous-ensemble<br />&nbsp; &nbsp; &nbsp; printf(&quot;----------&#092;n&quot;);<br />&nbsp; &nbsp; }//fin du teste de maximalite<br />&nbsp; }//fin du parcours de tous les sous-ensembles<br />&nbsp; <br />&nbsp; //liberation des ressources<br />&nbsp; free(sousEnsemble);<br />&nbsp; <br />&nbsp; enumerator = [solutionsToKeep objectEnumerator];<br />&nbsp; while((adresse = [enumerator nextObject]))<br />&nbsp; &nbsp; free((int*)[adresse unsignedLongValue]);<br /><br />&nbsp; enumerator = [allPossibleSums objectEnumerator];<br />&nbsp; while((adresse = [enumerator nextObject]))<br />&nbsp; &nbsp; free((int*)[adresse unsignedLongValue]);<br /><br />&nbsp; free(numbers1);<br />&nbsp; free(numbers2);<br />&nbsp; free(factors);<br />}<br /><br />@end<br />


    [Fichier joint supprimé par l'administrateur]
  • cargocargo Membre
    12:13 modifié #8
    super !!!
    après quelques tests :
    - ça mouline grave à  partir de 11 chiffres dans la liste 1, obligé de forcer à  quitter ; le but c'est de pouvoir travailler avec beaucoup de chiffres en liste 1 pour "combler" tous les chiffres en liste 2 (on va dire jusqu'à  une bonne centaine de nombres).
    - j'ai fait un essai en ajoutant à  chaque fois un nombre dans la liste 2, ce qui augmente les possibilités de combinaisons, il me diminue parfois le nombre de combinaisons trouvées cà d il en trouve 3, je rajoute un nombre dans la liste 2 et il n'en trouve plus que 2, il en zappe une au passage...

    ps : chacha si t'arrive à  finaliser ce truc promis tu seras récompensé !
  • ChachaChacha Membre
    12:13 modifié #9
    dans 1135876527:

    le but c'est de pouvoir travailler avec beaucoup de chiffres en liste 1 (...) (on va dire jusqu'à  une bonne centaine de nombres).

    Ah ouais, mais dans ce cas, pas pareil ! Là  il est clair qu'un code simple ne peut pas suffire. Le mien ayant une complexité théorique trop élevée, il est bon à  jeter. Il faut réfléchir à  une autre méthode, certainement plus compliquée. J'ai une idée, je vais voir.
    Au fait : ça m'arrangerait si tu me disais que tous tes nombres sont forcément positifs.


    - j'ai fait un essai en ajoutant à  chaque fois un nombre dans la liste 2, ce qui augmente les possibilités de combinaisons, il me diminue parfois le nombre de combinaisons trouvées cà d il en trouve 3, je rajoute un nombre dans la liste 2 et il n'en trouve plus que 2, il en zappe une au passage...

    Ah, tiens, tu peux me donner ton test-case ? Que je cherche le bug..

    Une dernière chose : il est clair que la taille de la liste1 est le facteur limitant. Il est donc important de vérifier dans une phase de pré-processing si on ne peut pas la réduire avant de lancer l'algo. Genre : tant que le max de la liste 1 est plus grand que le max de la liste 2, on peut le virer (dans le cas où tous les nombres sont positifs, là  encore).

    +
    Chacha
  • ChachaChacha Membre
    12:13 modifié #10
    Bon, voilà  mon idée :
    Je crois qu'elle est correcte, mais en tous cas elle semble l'être. Et finalement, le code est encore plus simple (à  écrire, pas à  comprendre).

    Voici : on prend le premier nombre de la liste1, et on le stocke dans la "solution courante"
    -On soustrait ce nombre à  tous les termes de la liste2
    -si un des termes de la liste2 devient 0, alors on vient de trouver une somme qui marche (pour l'instant de 1 terme), et on stocke la "solution courante"
    -maintenant, on enlève le nombre pris dans la liste 1, et on recommence avec la nouvelle liste 1.
    -on prend le "nouveau" premier terme (qui était anciennement le second), et on l'ajoute à  la "solution courante" (elle a maintenant deux termes), et on itère ainsi de suite
    -quand la liste 1 est vide, on a fini notre exploration
    -donc on "remonte d'un cran" : on enlève le dernier terme de la solution courante, et on l'additionne aux nombres de la liste 2 (on la "remet en état", donc)

    Bon, c'est éminement récursif, et ça donne le code suivant, qui a l'air de très bien marcher !
    Attention, ça génère toutes les solutions.
    Pour filtrer les solutions, on peut garder le principe du masque binaire des posts précédents. Je te laisse fusionner les deux codes.

    <br />//<br />//  Solver2.m<br />//  toto<br />//<br />//  Created by Pierre Chatelier on 28/12/05.<br />//  Copyright 2005 __MyCompanyName__. All rights reserved.<br />//<br /><br />#import &quot;Solver2.h&quot;<br /><br /><br />@implementation Solver2<br /><br />void resoudre(int* numbers1, unsigned int size1, int* numbers2, unsigned int size2,<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; NSMutableArray* currentSolution, NSMutableArray* allSolutions)<br />{<br />&nbsp; int i = 0;<br />&nbsp; for(i = 0 ; i&lt;size1 ; ++i)<br />&nbsp; {<br />&nbsp; &nbsp; NSAutoreleasePool* ap = [[NSAutoreleasePool alloc] init];//bon, là  c&#39;est du détail, c&#39;est pour économiser de la mémoire<br />&nbsp; &nbsp; NSNumber* n = [NSNumber numberWithInt:numbers1[i]];<br />&nbsp; &nbsp; [currentSolution addObject:n];<br />&nbsp; &nbsp; int j = 0;<br />&nbsp; &nbsp; for(j = 0 ; j&lt;size2 ; ++j)<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; numbers2[j] -= numbers1[i];<br />&nbsp; &nbsp; &nbsp; if (numbers2[j] == 0)<br />&nbsp; &nbsp; &nbsp; &nbsp; [allSolutions addObject:[[currentSolution mutableCopy] autorelease]];<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; [ap release];<br />&nbsp; &nbsp; resoudre(numbers1+i+1, size1-i-1, numbers2, size2, currentSolution, allSolutions);<br />&nbsp; &nbsp; for(j = 0 ; j&lt;size2 ; ++j)<br />&nbsp; &nbsp; &nbsp; numbers2[j] += numbers1[i];<br />&nbsp; &nbsp; [currentSolution removeObject:n];<br />&nbsp; }<br />}<br /><br />//resoudre<br />-(IBAction) solve:(id)sender<br />{<br />&nbsp; //d&#39;abord, creer les listes de nombres, triees<br />&nbsp; NSArray* list1OfStrings = [[list1TextField stringValue] componentsSeparatedByString:@&quot; &quot;];<br />&nbsp; NSArray* list2OfStrings = [[list2TextField stringValue] componentsSeparatedByString:@&quot; &quot;];<br /><br />&nbsp; unsigned int size1 = [list1OfStrings count];<br />&nbsp; unsigned int size2 = [list2OfStrings count];<br />&nbsp; <br />&nbsp; //l&#39;algo travaillera sur des tableaux en C<br />&nbsp; int* numbers1 = (int*)malloc(size1*sizeof(int));<br />&nbsp; int* numbers2 = (int*)malloc(size2*sizeof(int));<br />&nbsp; <br />&nbsp; //on remplit les tableaux<br />&nbsp; unsigned int i = 0;<br />&nbsp; for(i = 0 ; i&lt;size1 ; ++i)<br />&nbsp; &nbsp; numbers1[i] = [[list1OfStrings objectAtIndex:i] intValue];<br />&nbsp; for(i = 0 ; i&lt;size2 ; ++i)<br />&nbsp; &nbsp; numbers2[i] = [[list2OfStrings objectAtIndex:i] intValue];<br />&nbsp; &nbsp; &nbsp;  <br />&nbsp; //maintenant, l&#39;algo<br />&nbsp; NSMutableArray* currentSolution = [NSMutableArray array];<br />&nbsp; NSMutableArray* allSolutions = [NSMutableArray array];<br />&nbsp; resoudre(numbers1, size1, numbers2, size2, currentSolution, allSolutions);<br />&nbsp; <br />&nbsp; NSLog(@&quot;allSolutions = %@&quot;, allSolutions);<br />&nbsp; NSEnumerator* enumerator = [allSolutions objectEnumerator];<br />&nbsp; NSArray* array = nil;<br />&nbsp; while((array = [enumerator nextObject]))<br />&nbsp; {<br />&nbsp; &nbsp; int somme = 0;<br />&nbsp; &nbsp; NSEnumerator* enumerator2 = [array objectEnumerator];<br />&nbsp; &nbsp; NSNumber* number = nil;<br />&nbsp; &nbsp; while((number = [enumerator2 nextObject]))<br />&nbsp; &nbsp; &nbsp; somme += [number intValue];<br />&nbsp; &nbsp; NSLog(@&quot;%@ = %d&quot;, array, somme);<br />&nbsp; }<br /><br />&nbsp; free(numbers1);<br />&nbsp; free(numbers2);<br />}<br /><br />@end<br />


    [Fichier joint supprimé par l'administrateur]
  • cargocargo Membre
    12:13 modifié #11
    - les nombres sont forcéments des entiers positifs dans les 2 listes
    - il y aura toujours moins de nombres dans la liste 2 que dans la liste 1
    - il est possible de faire sauter les nombres de la liste 1 qui dépassent le nombre maxi de la liste 2 , même si ce pré test peut être utile, la gain ne sera pas conséquent, en effet le but est de "remplir" tous les nombres de la liste 2 : pour ce faire on ajoute des nombres dans la liste 1 (dont on a pas le choix des valeurs bien évidemment) jusqu'à  ce que les nombres de la liste 2 soient tous remplis, ou on a aussi la possibilité de faire varier les valeurs de tous les nombres de la liste 1 mais là  encore on ne maà®trise pas les variations individuelles de ces nombres (on les divise tous par 1 même coefficient en fait)
    - je n'arrive pas à  reproduire l'anomalie (c'est peut être moi qui ai louché en regardant le run log finalement) ; j'aurais du immédiatement noter mes manips, je n'ai pas encore les bons réflexes d'un programmateur ou d'un beta testeur  ::)
    - je suis allé faire un petit tour sur ton site perso, je comprends maintenant que ce petit algorithme c'est de la rigolade pour toi.. :)
    - je ne comprends pas pourquoi ça ne marcherait plus avec un grande liste de nombres, même si je pige que ton système de "matrice" augmente le nombre de calculs à  faire de façon exponentielle au fur et à  mesure que l'on ajoute des nombres dans la liste 1: c'est trop pour le processeur ? la mémoire de l'appli se sature ?

  • cargocargo Membre
    décembre 2005 modifié #12
    pfff ! j'ai même pas le temps de rédiger une réponse qu'il a déjà  pondu un nouveau code...y a de quoi vous décourager quand vous en êtes à  essayer de comprendre le fonctionnement d'un NSArray ou d'une tableView !!!  :crackboom:-

    tiens c'est marrant j'avais eu l'intuition de passer par des soustractions (mais bon c'en est resté au stade d'idée mal dégrossie dans mon cerveau)...
  • ChachaChacha Membre
    12:13 modifié #13
    dans 1135881582:

    pfff ! j'ai même pas le temps de rédiger une réponse qu'il a déjà  pondu un nouveau code...y a de quoi vous décourager quand vous en êtes à  essayer de comprendre le fonctionnement d'un NSArray ou d'une tableView !!!  :crackboom:-


    Ouais mais bon, j'ai fait des études d'informatique...
    Tiens, cadeau  : j'a mis à  jour mon code pour qu'il ne garde que les solutions maximales...

    +
    Chacha

    [Fichier joint supprimé par l'administrateur]
  • ChachaChacha Membre
    décembre 2005 modifié #14
    dans 1135881422:

    - les nombres sont forcéments des entiers positifs dans les 2 listes

    Super ! Comme ça tu vas vraiment pouvoir optimiser encore l'algo (là  je te laisse faire)
    En effet, si tous les nombres sont positifs, tu peux faire en sorte de "virer" de la liste 2 les nombres qui passent en négatif. (bien sûr, il faudra les restaurer après; idée : trier le tableau et ne travailler que sur le sous-tableau des positifs).
    Une première version simple d'optimisation : c'est la même fonction "resoudre" sauf qu'il y a trois lignes en plus avec la variable "allNegatives"
    <br />void resoudre(int* numbers1, unsigned int size1, int* numbers2, unsigned int size2,<br />              NSMutableSet* currentSolution, NSMutableArray* allSolutions)<br />{<br />  int i = 0;<br />  for(i = 0 ; i&lt;size1 ; ++i)<br />  {<br />    NSAutoreleasePool* ap = [[NSAutoreleasePool alloc] init];//bon, là  c&#39;est du détail, c&#39;est pour économiser de la mémoire<br />    NSNumber* n = [NSNumber numberWithInt:numbers1[i]];<br />    [currentSolution addObject:n];<br />    BOOL allNegatives = YES; //++++++++<br />    int j = 0;<br />    for(j = 0 ; j&lt;size2 ; ++j)<br />    {<br />      numbers2[j] -= numbers1[i];<br />      if (numbers2[j] == 0)<br />        [allSolutions addObject:[[currentSolution mutableCopy] autorelease]];<br />      allNegatives &amp;= (numbers2[j] &lt;= 0); //++++++++<br />    }<br />    [ap release];<br />    if (!allNegatives) //++++++++<br />      resoudre(numbers1+i+1, size1-i-1, numbers2, size2, currentSolution, allSolutions);<br />    for(j = 0 ; j&lt;size2 ; ++j)<br />      numbers2[j] += numbers1[i];<br />    [currentSolution removeObject:n];<br />  }<br />}<br />



    - il est possible de faire sauter les nombres de la liste 1 qui dépassent le nombre maxi de la liste 2 , même si ce pré test peut être utile, la gain ne sera pas conséquent,

    Oh, si ! Enlever un seul nombre de la liste1 est déjà  un très gros gain !


    - je n'arrive pas à  reproduire l'anomalie

    Tant mieux :-P


    - je ne comprends pas pourquoi ça ne marcherait plus avec un grande liste de nombres, même si je pige que ton système de "matrice" augmente le nombre de calculs à  faire de façon exponentielle au fur et à  mesure que l'on ajoute des nombres dans la liste 1: c'est trop pour le processeur ? la mémoire de l'appli se sature ?

    Dès que c'est exponentiel, ça devient impraticable. En effet, imagine que <n> soit la taille dela liste1.
    S'il faut environ exp(n) opérations pour résoudre, la différence est ENORME entre n et n+1 !!!
    Y'a qu'à  regarder l'écart entre exp(11) et exp(12), par exemple...
    Donc oui, quand une exponentielle traà®ne, on est très très vite limité.

    +
    Chacha
  • cargocargo Membre
    12:13 modifié #15
    bon maintenant ça pédale pour faire le tri des solutions : all solutions s'affiche de façon instantanée mais pas final solutions, ce qui me parait logique car le tri s'effectue selon le principe de "matrice" que tu as utilisé dans ton premier code.
    en fait on peut utiliser le principe de la soustraction pour faire le tri aussi : prendre la première solution, soustraire les nombres qui la composent avec chacun des nombres qui composent chacune des autres solutions et ainsi de suite avec le deuxième nombre, puis la deuxième solutions, etc...
    principe : quand le programme trouve un ensemble de soustractions dont les résultats diffèrent de 0 il garde les 2 ou 3 ou 4 etc solutions qui vont bien ensemble et ainsi de suite.
    au final je pense qu'il est facile alors de "choisir" l'ensemble de solutions qui contient le plus de solutions

    qu'en penses-tu ? j'essaye de modéliser ça, je dis bien "j'essaye"... :o
  • AliGatorAliGator Membre, Modérateur
    12:13 modifié #16
    Moi je vous laisse, je n'ai plus cherché à  suivre les derniers posts, je vois que chacha s'en charge :p <3 :kicking:
  • ChachaChacha Membre
    12:13 modifié #17
    dans 1135941607:

    bon maintenant ça pédale pour faire le tri des solutions

    Oui, j'ai constaté aussi. Effectivement, ce n'est pas adapté à  de grandes listes.


    en fait on peut utiliser le principe de la soustraction pour faire le tri aussi :

    Heu... je n'ai pas compris ta méthode du tout...


    au final je pense qu'il est facile alors de "choisir" l'ensemble de solutions qui contient le plus de solutions


    Ma nouvelle idée est la suivante, mais je ne sais pas a priori si elle est pratiquable :
    générer tous les sous-ensembles de solution, mais en utilisant les capacités des NSSet, ce qui devrait être bien plus efficace que la technique "nombre binaire". Et au fur et à  mesure, on ne conserve que les plus grands ensembles.
    J'y réfléchis... dans les prochains jours ! Là  j'ai un nouvel an à  faire ;-)

    +
    Chacha
  • cargocargo Membre
    12:13 modifié #18
    voici 3 solutions inspirées de l'exemple :
    15 +22 = 37
    105 + 22 + 47 + 38 = 212
    47 + 93 +38 = 178
    principe de la soustraction (on part de la première solution) :
    15 -105 est différent de 0
    15 - 22  est différent de 0
    15 - 47 est différent de 0
    15 - 38 est différent de 0 jusque là  les solutions 1 et 2 sont compatibles on continue avec 22
    22 -105 est différent de 0
    22 - 22 = 0 stop ! les solutions sont incompatibles entre elles, elles utilisent le même chiffre
    ...et ainsi de suite
    en comparant les solutions 37 et 178 , ça matche, donc le programme stocke (dans un array ?) cette "paire"  de solutions compatibles et il la rejettera à  la fin si il trouve une "triplette".
    à  partir de ton code j'ai commencé à  écrire ça en supposant que allPossibleSums est un tableau contenant les termes des sommes des solutions :

    <br />unsigned int sizeOfAllPossibleSums = [allPossibleSums count];<br />int i = 0;<br /><br />for(i = 0 ; (i&lt;sizeOfAllPossibleSums) ; ++i)<br />{	<br />	{int j = 0; <br />	 for(j = 0 ; (j&lt;sizeOfAllPossibleSums) ; ++j)<br />		{if((int*)[allPossibleSums objectAtIndex:i] - (int*)[allPossibleSums objectAtIndex:j] != 0)<br />			...<br />


    :o

    Mais bon, "on ne va pas passer le réveillon là -dessus"...Y a mieux à  faire... ;)

    Bon jour de l'an à  toi et à  tout le monde   :kicking:  :p   :p   <3   :adios!:
  • ChachaChacha Membre
    12:13 modifié #19
    dans 1136023834:

    voici 3 solutions inspirées de l'exemple :


    Ah, d'accord. Mais en fait, tester les "conflits" n'est pas un problème, les solutions étant stockées dans des NSSet, il suffit d'utiliser la méthode "intersectsSet", qui sera optimale. Par contre, la difficulté, c'est bien d'énumérer tous les sous-ensembles de solutions et de ne garder que le(s) meilleur(s).
    À première vue, c'est toujours super lent. Mais bon, c'est de la combinatoire...

    +
    Chacha
  • SystemSystem
    12:13 modifié #20
    Si je n'arrive pas trop tard, j'avais mis dans l'annuaire un bouquin d'algorithmique. Et voici la page qui pourrait vous intéresser: http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE152.HTM#SECTION03135000000000000000
  • ChachaChacha Membre
    janvier 2006 modifié #21
    Salut, c'est pour une mauvaise nouvelle (enfin, y'a plus grave quand même). Apparemment, il ne peut y avoir de solution efficace au problème du filtrage de tes solutions.
    J'explique (attention c'est technique):
    Supposons que l'on dispose de l'ensemble des solutions, chaque solution étant représentée par le sommet d'un graphe, et les arêtes du graphe représentant les "conflits" entre les paires de solution. Et bien dans ce cas, trouver le "meilleur sous-ensemble" revient à  chercher le plus grand sous-graphe stable, ou en dual, la clique maximale. Et ce problème est NP-complet (j'avais dit que ce serait technique).
    Bref, à  moins que j'aie été pessimiste dans la modélisation du problème, il n'existe pas à  ce jour de méthode qui sera rapide pour un grand nombre de solutions.
    Du coup, il faudrait taper dans les heuristiques, c'est-à -dire, des méthodes pas forcément exactes, mais qui donnent quand même un résultat exploitable.
    Foilà  foilà  foilà 

    +
    Chacha

    [edit]
    Je relis mon message plusieurs minutes plus tard; en fait il donne carrément l'impression que je me la pète grave ! Ce n'est pas le but; le vocabulaire est compliqué mais précis : ceux qui ont appris la théorie des graphes comprendront tout de suite. Pour ceux qui n'ont jamais eu de cours de théorie des graphes, je serais ravi de donner des explications supplémentaires.
    [/edit]
  • AliGatorAliGator Membre, Modérateur
    janvier 2006 modifié #22
    Les problèmes NP-complets : c'est quoi ?
    :) ;D <3 <br />
    Ceci dit puisque c'est nous qui créons l'arbre, et en plus en utilisant la réccurence, ne peut-on pas étiqueter chaque branche de l'arbre par la profondeur du sous-arbre ?
    Cela rendrait la recherche de la solution optimale automatique et directe.

    En gros le principe c'est qu'en même temps que l'on construit notre arbre des solutions, on fait remonter l'information de la profondeur de chaque sous-arbre. Ce qui n'est pas bien sorcier puisqu'on a construit notre arbre par réccurence, la profondeur de la reccurence est facile à  construire (=1 si on arrive à  la condition d'arret donc à  une feuille, et = ancienne profondeur + 1 si on fait un appel reccurent).
    Au final au sommet-racine de notre arbre on aura pour chaque branche la profondeur du sous-arbre et on pourra donc faire une alpha-coupe très rapide, non ?

    Ceci dit je ne suis pas sûr non plus à  100% que l'on parle du même arbre, comment représenterais-tu dans ta vision tes sous-arbres des solutions conflictuelles ? A détailler.
  • ChachaChacha Membre
    12:13 modifié #23
    Mon problème est NP-complet parce que je le représente par un graphe.
    Tu as une idée pour le représenter avec un arbre ?

    +
    Chacha
  • cargocargo Membre
    janvier 2006 modifié #24
    je vais à  la pharmacie acheter du tranxène et je reviens... ;)

    la théorie des graphes je vois vaguement ce que c'est...

    pour être concret, il n'est pas forcément indispensable que le programme donne la meilleure solution, si il donne les sous-ensembles de solutions compatibles entre elles c'est déjà  bien ! le choix pourra se faire "à  l'oeil nu" ensuite, mais d'après ce que je comprends c'est déjà  un problème de trouver les solutions compatibles et ce de façon exhaustive.

    je reviens à  mon histoire de soustraction, ça me parait possible ça : le programme soustrait le premier nombre de la première solution avec tous les autres nombres et ça lui donne une indication sur les solutions compatibles, dès qu'il en trouve une il la stocke, et ainsi de suite.
    c'est le même raisonnement que la première partie du programme : remplacer une méthode "binaro-matricielle" trop lente (moi aussi j'essaye de me la péter en mettant des mots compliqués, mais les miens, ils n'existent pas  :)... ), par une méthode basée sur un calcul simple d'opération.

    ben d'après l'url et mes souvenirs un problème NP-complet c'est justement un arbre...

  • AliGatorAliGator Membre, Modérateur
    12:13 modifié #25
    Désolé j'avais lu arbre au lieu de graphes, comme tu as dû le comprendre.
    Du coup j'avais l'impression que tu avais mal représenté le problème, qu'un sommet d'un arbre était pour toi la valeur d'un résultat, et ses branches les éléments à  additionner pour obtenir ce résultat... Ce qui aurait convenu pour un autre problème formulé un peu comme ça :
    Soit une (unique) liste de nombre, trouver toutes les combinaisons de sommes de ces nombres pour obtenir un résultat donné (exemple : trouver les combinaisons des nombres 2,3,5,6,7,10,13 pour obtenir le résultat 18).

    Bref, en effet, j'ai bien relu la représentation que tu avais en tête je comprend mieux. Elle ne correspond qu'à  la phase "résolution de conflits des solutions" et n'intervient pas dans la phase "construction de toutes les solutions possibles" et là  en effet...
  • ChachaChacha Membre
    12:13 modifié #26
    dans 1136320114:

    Bref, en effet, j'ai bien relu la représentation que tu avais en tête je comprend mieux. Elle ne correspond qu'à  la phase "résolution de conflits des solutions" et n'intervient pas dans la phase "construction de toutes les solutions possibles" et là  en effet...


    Ouaip, c'est effectivement ce que j'obtiens en séparant les deux phases. Cela dit, la représentation d'une solution doit aussi pouvoir se faire à  l'aide d'un treillis (chouette encore un mot compliqué. Je parle d'inf-irréductibles, maintenant ?). Mais les treillis, j'ai jamais rien compris.
    L'avantage du treillis, c'est qu'il prendrait directement en compte les relations entre les solutions.

    Désolé, cargo, mais ton problème va vraiment chercher super loin !
    Cela dit, effectivement, ça finira peut-être avec une heuristique pas trop compliquée...

    +
    Chacha
  • ChachaChacha Membre
    12:13 modifié #27
    Salut,

    J'ai du nouveau !
    Un algorithme simple pour le filtrage. Honnêtement, je ne sais pas s'il est exact, mais il me paraà®t efficace dans tous les sens du terme.
    Voici l'idée :
    (rappel : on essaye de trouver des <nombres2> avec des sommes de <nombres1>)
    Pour chaque nombre2, on connaà®t l'ensemble des sommes qui pourraient convenir.
    Pour chaque nombre2, on choisit la plus petite de ces possibilités (en taille)
    Parmi toutes ces possibilités sélectionnées, pour tous les nombres2, on garde la plus petite
    On l'enlève. Du coup, les <nombres1> disponibles deviennent moins nombreux, on les met à  jour.
    Et on recommence, tant qu'on trouve des solutions à  garder.

    Avec cette méthode, on essaye de minimiser les conflits, puisque qu'on ne garde que les plus petites solutions à  chaque fois. Après, bon, est-ce que ça donnera le résultat exact...

    Voilà  le code et le projet XCode qui va avec:

    <br />  //on a toutes les solutions dans &quot;allSolutions&quot; (NSArray de NSSet)<br />  NSLog(@&quot;allSolutions = %@&quot;, allSolutions);<br /><br />  //filtrage des solutions :<br />  NSMutableArray* finalSolutions = [NSMutableArray array];<br />  <br />  //d&#39;abord, on cree le dico des relations : a un nombre2 est associe un tableau de solutions<br />  NSLog(@&quot;filtrage&quot;);<br />  NSMutableDictionary* links = [NSMutableDictionary dictionary];<br />  enumerator = [allSolutions objectEnumerator];<br />  solution = nil;<br />  while((solution = [enumerator nextObject]))<br />  {<br />    NSNumber* key = [NSNumber numberWithInt:somme(solution)];<br />    NSMutableArray* value = [links objectForKey:key];<br />    if (value)<br />      [value addObject:solution];<br />    else<br />      [links setObject:[NSMutableArray arrayWithObject:solution] forKey:key];<br />  }<br />  //pour chaque tableau de solutions, tri des solutions par ordre croissant<br />  enumerator = [links objectEnumerator];<br />  NSMutableArray* linkedSolutions = nil;<br />  while((linkedSolutions = [enumerator nextObject]))<br />    [linkedSolutions sortUsingSelector:@selector(compareCount:)];//compareCount est une methode a moi<br /><br />  //principe : pour chaque nombre2, on cherche sa plus petite solution possible<br />  //parmi toutes ces solutions possibles, on choisit la plus petite<br />  //on recommence tant qu&#39;il reste des nombres et qu&#39;ils ont des solutions possibles<br />  NSMutableSet* freeNumbers1 = [[numbers1set mutableCopy] autorelease];//les nombres1 libres restant<br />    <br />  BOOL fini = NO;<br />  while(!fini)<br />  {<br />    NSAutoreleasePool* ap1 = [[NSAutoreleasePool alloc] init];<br />    //on va conserver pour chaque nombre2 sa plus petite possibilite<br />    NSMutableDictionary* smallestRemainingPossibilities = [NSMutableDictionary dictionary];<br /><br />    //et il faudra conserver la plus petite de toutes!<br />    NSSet* smallestPossibilityForAllNumbers = nil;<br />    NSNumber* numberForSmallestPossibility = nil;<br />    <br />    //on parcourt les nombres2<br />    NSEnumerator* numbers2Enumerator = [links keyEnumerator];<br />    NSNumber* number2 = nil;<br />    while((number2 = [numbers2Enumerator nextObject]))<br />    {<br />      //il a un certains nombres de solutiosn associees, pas forcement encore possible<br />      //(en fonction des nombres1 libres restant)<br />      NSMutableArray* solutions = [links objectForKey:number2];<br />      <br />      //parcouront toutes ces solutions (elles sont normalement triees par taille croissante)<br />      unsigned int nbSolutions = [solutions count];<br />      for(i = 0 ; i&lt;nbSolutions ; ++i)<br />      {<br />        NSSet* solution = [solutions objectAtIndex:i];<br />        //la solution est possible si elle est sous-ensemble des nombres1 libres<br />        if ([solution isSubsetOfSet:freeNumbers1])<br />        {<br />          //dans ce cas, on met a jour les infos<br />          [smallestRemainingPossibilities setObject:solution forKey:number2];<br />          if (!smallestPossibilityForAllNumbers || ([solution count] &lt; [smallestPossibilityForAllNumbers count]))<br />          {<br />            smallestPossibilityForAllNumbers = solution;<br />            numberForSmallestPossibility = number2;<br />          }<br />          break;//et on arrete de chercher, puisque les solutiosn suivantes sont plus grandes<br />        }<br />      }<br />      //si on a trouve une solution pour notre nombre, on peut enlever celles qui n&#39;etaient pas bonnes<br />      if ([smallestRemainingPossibilities objectForKey:number2])<br />        [solutions removeObjectsInRange:NSMakeRange(0, i)];<br />    }//end for each number2<br />    <br />    //maintenant, parmi toutes ces possibilites pour tous les nombres, on ne garde que la plus petite<br />    if (smallestPossibilityForAllNumbers)<br />    {<br />      [links removeObjectForKey:numberForSmallestPossibility];<br />      [finalSolutions addObject:smallestPossibilityForAllNumbers];<br />      [freeNumbers1 minusSet:smallestPossibilityForAllNumbers];<br />    }<br />    fini = (smallestPossibilityForAllNumbers == nil);<br />    [ap1 release];<br />  }<br />  <br />  NSLog(@&quot;final solutions = %@&quot;, finalSolutions);<br />



    [Fichier joint supprimé par l'administrateur]
  • AliGatorAliGator Membre, Modérateur
    janvier 2006 modifié #28
    Le hic c'est que si tu parcours la liste des résultats <R> (que tu appelles <nombres2>) dans un certain ordre ou dans un autre, tu n'auras pas le même résultat.
    J'appelle pour ma part <R> la liste des Résultats de sommes que l'on veut obtenir (liste 2), et <Op> la liste des Opérandes que l'on a le droit d'utiliser (liste1)

    Exemple :
    - tu prends le premier nombre R1 de la liste <R> et regarde quels sont les nombres de <Op> qui, en les additionnant, donne ce nombre R1. Tu trouves qu'une seule solution, Op1+Op2+Op3=R1
    - Pour R2 tu trouves qu'une solution aussi, qui est Op1+Op2=R2, mais vu que tu as supprimé Op1,Op2 et Op3 (ayant trouvé R1 à  l'étape précédente), elle n'est pas trouvé. Et tu ne trouves rien d'autre.
    - Et pour R3 tu trouves Op3+Op5 mais qui n'est plus possible puisque tu as supprimé les Op1 à  Op6, et rien d'autre comme possibilité.

    Conclusion :
    - ton algo trouve R1=Op1+Op2+Op3 et c'est tout
    La bonne solution devrait donner le max d'utilisation des nombres de nos listes, et donc cette solution qui en plus utilise à  la fois plus d'éléments de <R> mais aussi plus de la liste <Op>, aurait dû être trouvée :
    - {R1 --> pas de somme associé, R2=Op1+Op2, R3=Op3+Op5}
    Donc 2 éléments de <R> et 4 de <Op> contre 1 et 3 !

    Par contre tu aurais parcouru ta liste <R> en regardant R1 en dernier, tu aurais trouvé la bonne solution.

    Donc comme dirait le perroquet dans Tintin (l'oreille cassé, de mémoire :)) : Carrrrammmbbaa, Encorrrrre Rrrattéé !
  • ChachaChacha Membre
    janvier 2006 modifié #29
    dans 1136587956:

    - Pour R2 tu trouves plusieurs solutions. La seule et donc plus courte est Op1+Op2=R2, mais vu que tu as supprimé Op1,Op2 et Op3 (ayant trouvé R1 à  l'étape précédente), elle n'est pas trouvé.


    Et non ! Je n'ai pas encore supprimé Op1, Op2 et Op3, puisque je n'étais pas sûr que je n'aurais pas mieux !

    Parmi toutes ces possibilités sélectionnées, pour tous les nombres2, on garde la plus petite


    Mon algo fonctionne donc ainsi:
    je trouve que
    R1 = Op1+Op2+Op3
    R2 = Op1+Op2
    R3 = Op3+Op5
    -La première passe me donne que la plus petite de ces trois solutions est Op1+Op2 (ou Op3+Op5)
    -Je l'enlève
    Il me reste:
    R1 = Op1+Op2+Op3 //devenu impossible, donc non
    R3 = Op3+Op5
    je choisis donc R3
    et voilà 

    Donc Carrramba, ça marche ;-)

    +
    Chacha
  • AliGatorAliGator Membre, Modérateur
    janvier 2006 modifié #30
    Ah ok j'avais mal compris ton explication de ton algo (et j'avais pas lu une seule ligne de code de ton implémentation, non plus ;D)

    Bon et alors si on a :
    R1 = Op1+Op2+Op3
    R2 = Op2+Op4
    R3 = Op4+Op5+Op6

    Première passe il trouve que c'est R2 le plus court. Et il enlève les solutions contenant donc Op2 et/ou Op4
    Deuxième passe : il n'y a plus rien.
    Alors que le mieux aurait été de garder R1 et R3 comme solutions... non ?
    Ca fait 2éléments de <R> et 6 de <Op> contre 1 et 2 :)

    Je sens que tu vas encore me démontrer que c'est pas encore comme ça que ton truc marche  :)beta:
  • ChachaChacha Membre
    janvier 2006 modifié #31
    dans 1136593077:

    Je sens que tu vas encore me démontrer que c'est pas encore comme ça que ton truc marche  :)beta:

    Ben non, cette fois tu as raison. Donc  il fallait bien avoir des doutes, cet algo n'est pas optimal. Par contre il est très rapide, je pense que cargo pourra quand même s'en servir.
    En tous cas bravo à  toi pour les contre-exemples, c'est pas forcément évident à  pondre !

    Au passage, ça m'a donné une idée. Et si pour la "meilleure des meilleures" liste, au lieu de "la plus courte" on prenait celle qui a "le moins de conflits avec les autres" ? ça poserait encore des problèmes (genre pour le premier passage de choix des meilleures listes, on choisit toujours arbitrairement la plus courte), mais ça améliorerait un peu.

    voici le code à  modifier:
    <br />&nbsp; &nbsp; //maintenant, parmi toutes ces possibilites pour tous les nombres, on ne garde que la meilleure<br />&nbsp; &nbsp; //si la meilleure est la plus petite:<br />&nbsp; &nbsp; /*if (smallestPossibilityForAllNumbers)<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; [links removeObjectForKey:numberForSmallestPossibility];<br />&nbsp; &nbsp; &nbsp; [finalSolutions addObject:smallestPossibilityForAllNumbers];<br />&nbsp; &nbsp; &nbsp; [freeNumbers1 minusSet:smallestPossibilityForAllNumbers];<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; fini = (smallestPossibilityForAllNumbers == nil);<br />&nbsp; &nbsp; */<br />&nbsp; &nbsp; //autre choix : la meilleure est celle qui pose le moins de conflits:<br />&nbsp; &nbsp; NSNumber* number2WithMinimalNumberOfConflicts = nil;<br />&nbsp; &nbsp; unsigned int smallestNumberOfConflicts = 0;<br />&nbsp; &nbsp; numbers2Enumerator = [smallestRemainingPossibilities keyEnumerator];<br />&nbsp; &nbsp; number2 = nil;<br />&nbsp; &nbsp; while((number2 = [numbers2Enumerator nextObject]))<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; NSSet* solutionOfNumber2 = [smallestRemainingPossibilities objectForKey:number2];<br />&nbsp; &nbsp; &nbsp; unsigned int nbConflicts = 0;<br />&nbsp; &nbsp; &nbsp; NSEnumerator* otherNumber2Enumerator = [smallestRemainingPossibilities keyEnumerator];<br />&nbsp; &nbsp; &nbsp; NSNumber* otherNumber2 = nil;<br />&nbsp; &nbsp; &nbsp; while((otherNumber2 = [otherNumber2Enumerator nextObject]))<br />&nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; NSSet* solutionOfOtherNumber2 = [smallestRemainingPossibilities objectForKey:otherNumber2];<br />&nbsp; &nbsp; &nbsp; &nbsp; if ((otherNumber2 != number2) &amp;&amp; [solutionOfNumber2 intersectsSet:solutionOfOtherNumber2])<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++nbConflicts;<br />&nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; &nbsp; if (!number2WithMinimalNumberOfConflicts || (nbConflicts &lt; smallestNumberOfConflicts))<br />&nbsp; &nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; &nbsp; number2WithMinimalNumberOfConflicts = number2;<br />&nbsp; &nbsp; &nbsp; &nbsp; smallestNumberOfConflicts = nbConflicts;<br />&nbsp; &nbsp; &nbsp; }<br />&nbsp; &nbsp; }<br />&nbsp; &nbsp; if (number2WithMinimalNumberOfConflicts)<br />&nbsp; &nbsp; {<br />&nbsp; &nbsp; &nbsp; solution = [smallestRemainingPossibilities objectForKey:number2WithMinimalNumberOfConflicts];<br />&nbsp; &nbsp; &nbsp; [links removeObjectForKey:number2WithMinimalNumberOfConflicts];<br />&nbsp; &nbsp; &nbsp; [finalSolutions addObject:solution];<br />&nbsp; &nbsp; &nbsp; [freeNumbers1 minusSet:solution];<br />&nbsp; &nbsp; }<br /><br />&nbsp; &nbsp; fini = (number2WithMinimalNumberOfConflicts == nil);<br />


    +
    Chacha
Connectez-vous ou Inscrivez-vous pour répondre.