Comment écrire une fonction combinatoire dans postgres?

Après avoir dormi dessus, j'ai eu une idée complètement nouvelle, plus simple et plus rapide :

CREATE OR REPLACE FUNCTION f_combos(_arr anyarray)
  RETURNS TABLE (combo anyarray) LANGUAGE plpgsql AS
$BODY$
BEGIN
    IF array_upper(_arr, 1) IS NULL THEN
        combo := _arr; RETURN NEXT; RETURN;
    END IF;

    CASE array_upper(_arr, 1)
--  WHEN 0 THEN -- does not exist
    WHEN 1 THEN
        RETURN QUERY VALUES ('{}'), (_arr);
    WHEN 2 THEN
        RETURN QUERY VALUES ('{}'), (_arr[1:1]), (_arr), (_arr[2:2]);
    ELSE
        RETURN QUERY
        WITH x AS (
            SELECT f.combo FROM f_combos(_arr[1:array_upper(_arr, 1)-1]) f
            )
        SELECT x.combo FROM x
        UNION ALL
        SELECT x.combo || _arr[array_upper(_arr, 1)] FROM x;
    END CASE;
END
$BODY$;

Appel :

SELECT * FROM f_combos('{1,2,3,4,5,6,7,8,9}'::int[]) ORDER BY 1;

512 lignes, durée d'exécution totale :2,899 ms

Expliquez

• Traiter les cas particuliers avec NULL et tableau vide.
• Créer des combinaisons pour un tableau primitif de deux.
• Tout tableau plus long est décomposé en :
  • les combinaisons pour un même tableau de longueur n-1
  • plus tous ceux combinés avec l'élément n .. récursivement .

Vraiment simple, une fois que vous l'avez compris.

• Fonctionne pour les tableaux d'entiers unidimensionnels commençant par indice 1 (voir ci-dessous).
• 2 à 3 fois plus rapide que l'ancienne solution, s'adapte mieux.
• Fonctionne pour tous type d'élément à nouveau (en utilisant des types polymorphes).
• Inclut le tableau vide dans le résultat tel qu'il est affiché dans la question (et comme @Craig me l'a fait remarquer dans les commentaires).
• Plus court, plus élégant.

Cela suppose indices de tableau à partir de 1 (Défaut). Si vous n'êtes pas sûr de vos valeurs, appelez la fonction comme celle-ci pour normaliser :

SELECT * FROM  f_combos(_arr[array_lower(_arr, 1):array_upper(_arr, 1)]);

Je ne sais pas s'il existe un moyen plus élégant de normaliser les indices de tableau. J'ai posté une question à ce sujet :
Normaliser les indices de tableau pour un tableau à une dimension afin qu'ils commencent par 1

Ancienne solution (plus lente)

CREATE OR REPLACE FUNCTION f_combos2(_arr int[], _a int[] = '{}', _z int[] = '{}')
 RETURNS SETOF int[] LANGUAGE plpgsql AS
$BODY$
DECLARE
   i int;
   j int;
   _up int;
BEGIN
   IF array_length(_arr,1) > 0 THEN 
      _up := array_upper(_arr, 1);

      FOR i IN array_lower(_arr, 1) .. _up LOOP
         FOR j IN i .. _up  LOOP
            CASE j-i
            WHEN 0,1 THEN
               RETURN NEXT _a || _arr[i:j] || _z;
            WHEN 2 THEN
               RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
               RETURN NEXT _a || _arr[i:j] || _z;
            ELSE
               RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
               RETURN QUERY SELECT *
               FROM f_combos2(_arr[i+1:j-1], _a || _arr[i], _arr[j] || _z);
            END CASE;
         END LOOP;
      END LOOP;
   ELSE
      RETURN NEXT _arr;
   END IF;
END;
$BODY$;

Appel :

SELECT * FROM f_combos2('{7,15,48}'::int[]) ORDER BY 1;

Fonctionne pour les tableaux d'entiers unidimensionnels. Cela pourrait être encore optimisé, mais ce n'est certainement pas nécessaire pour la portée de cette question.
ORDER BY pour imposer l'ordre affiché dans la question.

Indiquez NULL ou un tableau vide, comme NULL est mentionné dans les commentaires.

Testé avec PostgreSQL 9.1, mais devrait fonctionner avec n'importe quelle version semi-moderne.array_lower() et array_upper() existent depuis au moins depuis PostgreSQL 7.4. Seules les valeurs par défaut des paramètres sont nouvelles dans la version 8.4. Pourrait facilement être remplacé.

Les performances sont correctes.

SELECT DISTINCT * FROM f_combos('{1,2,3,4,5,6,7,8,9}'::int[]) ORDER BY 1;

511 lignes, durée d'exécution totale :7,729 ms

Explication

Il s'appuie sur ce formulaire simple qui ne crée que toutes les combinaisons d'éléments voisins :

CREATE FUNCTION f_combos(_arr int[])
  RETURNS SETOF int[] LANGUAGE plpgsql AS
$BODY$
DECLARE
   i  int;
   j  int;
  _up int;
BEGIN
   _up := array_upper(_arr, 1);

   FOR i in array_lower(_arr, 1) .. _up LOOP
      FOR j in i .. _up LOOP
         RETURN NEXT _arr[i:j];
      END LOOP;
   END LOOP;
END;
$BODY$;

Mais cela échouera pour les sous-tableaux avec plus de deux éléments. Donc :

• Pour tout sous-tableau avec 3 éléments, un tableau avec seulement les deux éléments extérieurs est ajouté. ceci est un raccourci pour ce cas particulier qui améliore les performances et n'est pas strictement nécessaire .

• Pour tout sous-tableau avec plus de 3 éléments, je prends les deux éléments externes et remplissez avec toutes les combinaisons d'éléments intérieurs construit par la même fonction récursivement .