Hur skriver man kombinatorisk funktion i postgres?

Efter att jag sovit över den fick jag en helt ny, enklare, snabbare idé:

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$;

Ring:

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

512 rader, total körtid:2,899 ms

Förklara

• Behandla specialfall med NULL och tom array.
• Skapa kombinationer för en primitiv uppsättning av två.
• Alla längre arrayer delas upp i:
  • kombinationerna för samma array med längden n-1
  • plus alla dessa kombinerade med element n .. rekursivt .

Verkligen enkelt, när du väl fick det.

• Fungerar för 1-dimensionella heltalsmatriser som börjar med subscript 1 (se nedan).
• 2-3 gånger så snabbt som den gamla lösningen, skalas bättre.
• Fungerar för alla elementtyp igen (med polymorfa typer).
• Inkluderar den tomma arrayen i resultatet som visas i frågan (och som @Craig påpekade för mig i kommentarerna).
• Kortare, mer elegant.

Detta förutsätter arrayprenumerationer från 1 (Standard). Om du inte är säker på dina värden, anropa funktionen så här för att normalisera:

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

Inte säker på om det finns ett mer elegant sätt att normalisera array-subskript. Jag ställde en fråga om det:
Normalisera arraysubscripts för 1-dimensionell array så att de börjar med 1

Gammal lösning (långsammare)

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$;

Ring:

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

Fungerar för 1-dimensionella heltalsmatriser. Detta skulle kunna optimeras ytterligare, men det behövs verkligen inte för den här frågans omfattning.
ORDER BY för att införa den ordning som visas i frågan.

Ange NULL eller tom array, som NULL nämns i kommentarerna.

Testad med PostgreSQL 9.1, men bör fungera med alla halvvägs moderna versioner.array_lower() och array_upper() har funnits åtminstone sedan PostgreSQL 7.4. Endast parameterstandarder är nya i version 8.4. Kan lätt bytas ut.

Prestanda är anständigt.

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

511 rader, total körtid:7,729 ms

Förklaring

Den bygger på denna enkla form som bara skapar alla kombinationer av angränsande element:

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$;

Men detta kommer att misslyckas för sub-arrayer med mer än två element. Så:

• För varje sub-array med 3 element läggs en array med bara de två yttre elementen till. det här är en genväg för det här specialfallet som förbättrar prestandan och som inte absolut behövs .

• För varje sub-array med mer än 3 element tar jag de yttre två elementen och fyll i med alla kombinationer av inre element byggd av samma funktion rekursivt .