Algorithme récursif pour trouver les couples possibles

Version imprimable

20/11/2017, 10h28
Soni0368

Algorithme récursif pour trouver les couples possibles

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 !
20/11/2017, 11h45
Matt_Houston

Citation:

Envoyé par Soni0368

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

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

Citation:

Envoyé par Soni0368

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 ?
20/11/2017, 11h50
Soni0368

Citation:

Envoyé par Matt_Houston

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

Des couples polygammes :weird: ? 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... !
20/11/2017, 13h28
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.
20/11/2017, 13h31
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).
20/11/2017, 16h33
Soni0368

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

Merci encore pour l'aide !
22/11/2017, 18h37
Soni0368

Citation:

Envoyé par 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.

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.
22/11/2017, 20h28
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:

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.

Merci encore pour votre investissement et votre apprentissage ! C'est très formateur !

-- Function: powerset(anyarray)

-- DROP FUNCTION powerset(anyarray);

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
CREATE OR REPLACE FUNCTION twouplets(a anyarray)
  RETURNS SETOF anyarray AS
$BODY$
DECLARE
    retval  a%TYPE;
    size  integer := array_upper(a, 1);
    i       integer;
    j       integer;
BEGIN
	i := 0;
	j := 1;
 
    FOR i IN 1 .. size LOOP
	FOR j IN 1 .. size-i LOOP
	retval := '{}';
	RAISE NOTICE '%-%',a[i],a[i+j];
                retval := array_append(retval, a[i]);
                retval := array_append(retval, a[i+j]);
                RETURN NEXT retval;
	END LOOP;
    END LOOP;
 
	RETURN; 
 
END;
$BODY$
  LANGUAGE plpgsql IMMUTABLE STRICT
  COST 100
  ROWS 1000;
ALTER FUNCTION twouplets(anyarray)
  OWNER TO postgres;

23/11/2017, 07h54
Matt_Houston

Je viens de voir que tu avais mentionné PL/SQL, et pas SQL tout court, raison pour laquelle tu l'as écrit de manière procédurale. Ça ressemble à cela, en effet.

Mais d'un point de vue pratique, je pensais plutôt à une simple requête SQL (select, join, group by..) auprès du moteur de base de données que tu utilises dans ton projet. Sauf besoin vraiment spécifique ce sera sans doute plus concis et performant. Tu peux rapidement tester tes brouillons sur un moteur en ligne comme SQL Fiddle.
23/11/2017, 08h18
Soni0368

Pour plus de faciliter de traitement je préfère le gérer dans du pl/sql (plus précisément pg/sql car sous postgres), car l'algorithme de 2-uplets est qu'une petite partie de mon algorithme...

Je rencontre malheureusement pas un autre problème lié à la complexité du calcul, pour traiter 100k ligne cela a mis 3minutes mais pour 3000k lignes ça fait maintenant 7h que ça tourne et je ne vois pas à quelle ligne j'en suis... (c'est une erreur j'aurais dû afficher le numéro de ligne de traitement).