Pour les bruts en algo

Dev
1

Salut à tous,

Mon problème n’est pas lié à un langage déterminé. C’est un problème d’algo pur.

Je dois trouver l’ensemble des combinaisons que l’on peut former avec un ensemble d’élément.

P’tit exemple :

$myArray = array(‘a’, ‘b’, ‘c’);

Je dois me retrouver avec :

A B C

A C B

B A C

B C A

C A B

C B A

J’ai trouvé différents algos qui me font ça et ça m’a l’air de marcher plutot pas mal.

En revanche maintenant j’aurais besoin d’avoir aussi toutes les combinaisons en enlevant des éléments…

re-P’tit exemple :

$myArray = array(‘a’, ‘b’, ‘c’);

Je dois me retrouver avec :

A B C

A C B

B A C

B C A

C A B

C B A

A B

A C

B A

B C

C A

C B

Et la, je dois dire que les cours d’algo que j’ai jamais eu me manque vraiment.

Suis preneur d’explication et d’exemple en n’importe quel langage, ce que je veux c’est le principe.

Merci d’avance.

2

Hmmm, je dis ptet une connerie, mais pourquoi tout simplement ne pas
créer des sous-groupe avec chacun l’un des elements en moins, et ce
recursivement jusqu’à ce que tu obtiennes tous les groupes possibles,
auquel tu appliquera ton algo de base ?

edit : pas taper hein, avec les greves l’an dernier on a pas vu le chapitre “algo”, donc j’y connais qued’ de qued’
Ce message a été édité par Clad le 03/03/2004

3

ca me rappelles quelques choses… cherche un post de moi dans segfault… un truc sur les tournois poules en php…

4

Compte rendu de la journée a plancher sur cette saloperie de probleme. J’avais pensé faire comme tu me dis Clad garder mon beau petit algo et l’appeler avec un array différent. Le problème se posait donc de recoder un nouvel algo qui me pondrait les sus-dits array.

Bon après quelques tests plus ou moins réussi et plusieurs litres de café on a conclu que c’était super lourd et que ca devenait une bonne petite usine à gaz.

Donc réu demain pour voir si on garde l’idée de départ ou si on se contente de l’array initial et que l’on ne retranche pas des éléments.
Suivant la conclusion je me pencherais sur ton problème de poules.

Et même si on abandonne l’idée je pense que je chercherais tout de même la soluce. Un peu têtu le Pisko.

En tout cas merci pour la participation.

5

Tu dev’ en quelle langage car j’ai deja eu des idédimplementations qui doit pas etre trop loud si j’ai le temps on sait jamais

Koubiiak

6

tousse tousse tousse…

Bon les gars, vous nous faites des etincelles la les gars… bon prenons le premier tableau :

A B C

A C B

B A C

B C A

C A B

C B A

et puis le deuxieme tableau

A B

A C

B A

B C

C A

C B

maintenant, imaginez que vous avez une scie a tableau pour enlever une colonne du tableau A, enlevez la troisieme colonnes, et la au mondieumaiscestfoutca, le premier tableau, moins la 3 colonnes est egale au deuxieme tableau, fou non ?

et sinon, a mon avis, avec n loop imbriquees, on doit pouvoir avoir toutes les version de maniere assez trivial.

Et voilaaaa!!!

(et je ne dis pas « 2, nul, salle, mal fait » parce que je ne veux pas etre medisant :stuck_out_tongue: )

7

oui mais aprés si tu dynamises ton alphabet ?

Donc on se transforme en recursif …

Koubiiak

8

c’est a dire ? avec un nombre variable de lettres, pas forcement dans le meme ordre ?
meme dans ce cas la, ca devrait marcher pareille, tu generes pour 4 puis tu coupe sur 3 puis tu coupes sur 2 et puis vla… sans recursion et avec interation
(en meme temps moi, mes reponses sont exactent dans un cadre precis hein… )

9

muf

Bon ok ok Enfin sinon la solution que j’ai pas donné resembler foutrement a la tienne

KOuby

10

La scie perd en efficacitée à chaque découpe (elle s’use ?)

Le premier coup de scie ote la dernière colonne, déduite des précédentes. Chaque ligne du tableau résultant est unique.

Le second coup de scie donne un tableau avec des doublons (les deux colonnes otés sont intervertibles)

Le troisième donne des hexions (?) et ainsi de suite

Ex : imaginons un ensemble à 5 elements A B C D E

Le sous ensemble à 2 éléments A B peut venir de

A B C D E
A B C E D
A B D C E
A B D E C
A B E C D
A B E D C

il faut donc donner un coup de balayette à chaque tour… ce qui alourdit l’algo qui semblait trop simple pour être vrai

Edit : je pense qu’en construisant le tableau correctement, cela doit pouvoir facilier les découpes horizontales (on coupe en 1 puis en 2 puis en 3…)
Ce message a été édité par zontrax le 04/03/2004

11

[quote]
zontrax a dit:


Edit : je pense qu’en construisant le tableau correctement, cela doit pouvoir facilier les découpes horizontales (on coupe en 1 puis en 2 puis en 3…)
Ce message a été édité par zontrax le 04/03/2004
Le truc, c'est que a ce moment, tu sais que quand tu en ai a n-2, tu ne dois prendre qu'1 resultat toutes les 2 lignes, puis un resultat toutes les 4, et puis etc... etc... etc...
12

[quote][quote]Edit : je pense qu’en construisant le tableau correctement, cela doit pouvoir facilier les découpes horizontales (on coupe en 1 puis en 2 puis en 3…)
Ce message a été édité par zontrax le 04/03/2004[/quote]Le truc, c’est que a ce moment, tu sais que quand tu en ai a n-2, tu ne dois prendre qu’1 resultat toutes les 2 lignes, puis un resultat toutes les 4, et puis etc… etc… etc…
[/quote]oui, si le tableau est bien construit, parce que sinon ça peut donner n’importe quoi.
Puis c’est un resultat toutes les 1 lignes à la premiere itération, puis toutes les 2 lignes à la seconde, toutes les 3 à la troisième (sur le tableau résultant). Voir plus efficace, on scie le tableau dans l’autre sens (première colonne en premier) et on ne garde que la 1/n première partie.

Cela etant dit, l’algo de création de tableau initial est soit itératif, soit récursif, mais dans tous les cas les colonnes sont classées par entropie (ça bouge plus ou moins) et l’ordre est déterministe. On peut donc assumer que le tableau est bien construit.

13

Ouai enfin a mon avis c’est le genre d’exo modele pour la question qui tue “quand est ce que la recursion ca sert a qqch d’utile?”. Faire ce genre de trucs en iteratif c’est s’embeter beaucoup pour pas grand chose.

14

ben c’est net que je pense qu’y a bien moyen en récursif avec juste le nombre d’élements que t’as au départ…
Tu tournes jusqu’à ce que ton nombre d’élements =2 comme ça t’as tout ce que tu veux.

Si j’ai bien compris ton problème…

Ce qui n’est pas sur.

15

ce qu’il te faut, c’est une fonction recursive, c’est e-vi-dent, mais laquelle… ca aussi, c’est e-vi-dent (j’fais bien le lourd hein ? le mec qu’étale sa science sans expliquer… ah que c’est facile d’être prof à la fac, pourquoi j’ai pas fait ca, mon dieu).

La où ton raisonnement n’a surement pas pu aboutir, c’est parceque le premier tableau à 2 dimensions est un cas particulier (y’a toutes les lettres, et en plus, dans ton exemple, tu n’a pas pris qqchose au hasard, tu as pris des lettres de l’alphabet qui se suivent).

LA fonction qu’il te faut, c’est la fonction qui, à partir d’une liste d’elements et d’une longueur ‘n’, te renvoie toutes les combinaisons de ‘n’ elements (quand je dis que c’est évident).
Mais où c’est que je case la récursion ?

Et bien toutes les combinaisons de ‘n’ elements, correspond en fait à toutes les combinaisons formées par 1 des elements suivi de toutes les combinaisons d’au plus ‘n-1’ elements avec pour liste d’entrée la même liste mais en enlevant l’élément déjà choisi… oula… j’suis pas clair.

toutes les combinaisons à 3 elements à partir de A,B,C,D c’est
A|BC
A|BD
A|CB
A|DB
A|B
A|C
A|D
A

B|AC
B|AD
B|CA
B|DA
B|A
B|C
B|D
B

C|AB
C|AD
C|BA
C|DA
C|A
C|B
C|D
C

D|AC
D|AD
D|CA
D|DA
D|A
D|B
D|C
D

soit A suivi de toutes les combinaisons de 2 elements (ou moins) à partir de B,C,D; plus B suivi de toutes les combi de 2 elt (ou moins) à partir de A,C,D; plus C suivi toutes les combi de 2 elt (ou moins) à partir de A,B,D; et enfin D suivi toutes les combi de 2 elt (ou moins) à partir de A,B,C

Là j’ai pas mis la limite à 2 elt minimum, vu que ca simplifie carrement l’algo (combinaisons à 1 lettre à partir de A,B,C… pfiou… dur… alors qu’avec 2 lettres, tu va doubler la taille de la fonction ! ie. passer de 3 à 6 lignes )
Suivant ce que tu veux faire du résultat, il sera très certainement préférable de passer également, en entrée de la fonction, les lettres déjà selectionnées (sinon faut prendre le résultat de la fonction et refaire un autre tableau en rajoutant ta lettre à chaque fois, et ca recursivement, ca te fais une usine à gaz aussi lente qu’un steak qui glisse sur un plat de nouilles. Oui, je sais, ca veut rien dire).

16

Pas bête du tout le coup de la scie !

J’y avais pas pensé du tout. C’est vrai que l’on se retrouve avec des doublons mais après soit on se débrouille pour faire le tri avant ou après… à voir…

Sinon pour la question du langage à la base ça devait être du PHP mais vu la lourdeur de la bête (au vue des donnée gérées, ca va pas resté à vie des ‘a’, ‘b’, ‘c’…), j’ai recodé le truc en Python ce qui est déjà plus clean et rapide.

Suite au prochain numéro.

17

urdle>pour un mec qui commence juste à toucher à la récursivité (mal à la tête ), il a quelle tête ton algo ???

18

[quote]urdle>pour un mec qui commence juste à toucher à la récursivité (mal à la tête

19

sans la limite “une combinaison de 1 elt ca existe pas”, l’algo en pseudo-code (à ma sauce) ressemblerait à

fonction F(IN LIGNE elts_choisis, IN LISTE liste_elts_dispo, IN ENTIER num, IN/OUT TABLEAU resultat)
{
  si num = 0
{
  ajoute_ligne ( resultat, elts_choisis )
  }
sinon // num > 0
  {
  pour chaque elt dans liste_elts_dispo
  F( elts_choisis + elt , liste_elts_dispo - elt, num - 1, resultat )
  }
}

et on appelle
F ("" , (“A”,“B”,“C”,“D”), 3, tableau_resultat)
affiche (tableau_resultat)

j’vous laisse vous amuser à derouler si ca vous chante
certains diront que le fait d’avoir une variable qui soit l’entrée et la sortie (resultat) c’est pas propre, mais tant pis (enfin bon, y’a qu’un variable en sortie, alors c’est facile à rendre propre et ca simplifie l’explication, je pense)

20

Bon si ça interesse quelqu’un voici le source en Python finalement utilisé :
(Le fichier passé en parametre contient mes différents tableaux a permuter)

#!/usr/bin/python import sys, string

def arrangement(listedemots):
 m=[]
 if len(listedemots)==1:
m= [[listedemots[0]]]
 else:
m=[]
for i in range(0,len(listedemots)):
 ss=[]
 l= arrangement(listedemots[0:i]+listedemots[i+1:])
 for n in l:
m=m+[[listedemots[i]]+n]
 return m
 
def isInArray(tab, elt):
 if elt in tab:
return 1
 else:
return 0

if name == “main”:
 if (len(sys.argv) > 1):
fileName = sys.argv[1]

fp = open(fileName, “r”)
for lines in fp.readlines():
 print(lines)
 listedemots = string.split(lines, " “)
 arrayPermut = arrangement(listedemots)
 cpt = 0
 arraySortie = []
 
 for i in arrayPermut:
arraySortie.append(i)
for j in range(1, len(i)-1):
 if isInArray(arraySortie, i[0:-j]) is 0:
arraySortie.append(i[0:-j])
 
 fp = open(”.sortiePermut", “a”)
 for i in arraySortie:
cpt = cpt+1
fp.write("%d %s
" % (cpt, i))
 fp.close()
 else:
print(“Nombre de parametre insuffisant”)
[/quote]La méthode utilisée est celle de la scie préconisée plus haut. Avant d’insérer dans le tableau je vérifie que la combinaison n’y est pas et on boucle… on boucle… on boucle…

Je vais voir ce que l’on peut faire avec ton idée urdle.

En tout cas merci à tous de votre aide.