Discussion :

[Soni0368]

Bonjour à toutes et à tous,

Voilà je suis devant une difficulté importante pour moi : le développement d'un algorithme récursif !

Je cherche à trouver l'intégralité des couples d'un groupe ( de n membres ) pour une étude importante.

Explications :

Groupe (des chaînes de caractères):
-A1
-A2
-B1
-B2

(Exemple de 4, mais cela peut-être 2, 3, 4, ... , n)

Résultats attendus (les couples possibles) :


A1-A2
A1-A2-B1
A1-A2-B1-B2
A1-A2-B2
A1-B1
A1-B1-B2
A1-B2
A2-B1
A2-B1-B2
A2-B2
B1-B2


ps : Le couple A1-A2 vaut également le couple A2-A1 (tous les membres du groupe sont déjà triés!)
ps2 : Je ne veux pas récupérer les éléments uniques (A1 ; A2 ; etc...) car cela ne forme pas un couple !
ps3 : Je veux réaliser l'algorithme en C mais la finalité étant de le faire fonctionner en PL/SQL... (Je veux le faire travailler pour une base de données...)


Je vois qu'il faut faire un algorithme récursif mais je ne sais pas du tout comment m'y prendre... !

Quelqu'un aurait une piste ou un début d'algorithme pour m'aider ?

Merci d'avance pour votre aide et pour vos explications !!!

A bientôt !

[Matt_Houston]

A1-A2-B1
A1-A2-B1-B2
A1-A2-B2

..ne sont pas des « couples ». Voulais-tu écrire « t-uple » ?

Quelqu'un aurait une piste ou un début d'algorithme pour m'aider ?

Non, ça c'est à toi de nous le fournir.

Comment procèderais-tu, aidé d'une simple feuille de papier et d'un crayon ?

[Soni0368]

..ne sont pas des « couples ». Voulais-tu écrire « t-uple » ?

Des couples polygammes ? Mais oui c'est bien des t-uplés !

Je vais faire des tests de scénarios possible sur papier pour essayer d'en sortir un algo répétitif... !

[Matt_Houston]

À quelques contraintes près, ce que tu cherches à générer se nomme l'ensemble des parties (ou power set en anglais) de l'ensemble de départ.

Puisque tu comptes au final l'appliquer à une base de données autant l'implémenter directement avec une requête SQL.

[Soni0368]

Merci ! Je me doutais que cela existait déjà, mais difficile de trouver sans connaître le terme exact...

Je préfère déjà le faire en C, car c'est plus simple à compiler et executer... ! (pour vérifier que mon algo est bon à 100% avant de me lancer en PL/SQL).

Merci infiniment pour l'aide ! (je posterais l'algo finale ici).

[Soni0368]

J'ai trouvé la solution ici : https://www.postgresql.org/message-i...innie.fuhr.org

Merci encore pour l'aide !

[Soni0368]

À quelques contraintes près, ce que tu cherches à générer se nomme l'ensemble des parties (ou power set en anglais) de l'ensemble de départ.

Puisque tu comptes au final l'appliquer à une base de données autant l'implémenter directement avec une requête SQL.

Connaissez-vous le nom de l'algorithme capable de faire sensiblement la même chose mais uniquement pour les couples : 2-uplets ?

J'ai peur qu'en adaptant l'algorithme powerset pour ressortir uniquement les couples je ralentisse énormément mes performances.

[Matt_Houston]

On ne considère à nouveau que les paires non-ordonnées alors ? On recherche donc l'ensemble des sous-ensembles de l'ensemble de départ dont le cardinal est exactement deux. Je ne sais pas si cet algorithme est connu sous un intitulé particulier, mais il n'est pas très compliqué de le retrouver.

Saurais-tu, par exemple, l'écrire pour le cas particulier de ce sous-ensemble des entiers naturels : { 0, 1, 2, 3, 4 } ? Posons le résultat recherché sur papier, ça devrait t'aider :

Code :

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

1
2
3
4
01 02 03 04
   12 13 14
      23 24
         34

Peux-tu ensuite généraliser le procédé pour un ensemble de départ de cardinal arbitraire ?


Encore une fois, si c'est au final pour exécuter sur une base de données, fais-le en SQL. L'algorithme C n'a probablement rien à voir avec l'implémentation SQL, qui est fait pour ce genre de requête.