Hvordan skriver man kombinatorisk funktion i postgres?

Efter at jeg havde sovet over det, fik jeg en helt ny, enklere og hurtigere 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 til:

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

512 rækker, samlet køretid:2.899 ms

Forklar

• Behandle særlige tilfælde med NULL og tom matrix.
• Byg kombinationer til en primitiv række af to.
• Enhver længere matrix er opdelt i:
  • kombinationerne for samme array med længde n-1
  • plus alle dem kombineret med element n .. rekursivt .

Virkelig enkelt, når du først har fået det.

• Fungerer for 1-dimensionelle heltalsarrays, der starter med subscript 1 (se nedenfor).
• 2-3 gange så hurtigt som en gammel løsning, skalerer bedre.
• Fungerer for alle elementtype igen (ved brug af polymorfe typer).
• Inkluderer det tomme array i resultatet, som det vises i spørgsmålet (og som @Craig påpegede for mig i kommentarerne).
• Kortere, mere elegant.

Dette forudsætter array-abonnementer starter ved 1 (Standard). Hvis du ikke er sikker på dine værdier, skal du kalde funktionen som denne for at normalisere:

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

Ikke sikker på, om der er en mere elegant måde at normalisere array-abonnementer på. Jeg stillede et spørgsmål om det:
Normaliser array-underskrifter for 1-dimensionelle array, så de starter med 1

Gammel løsning (langsommere)

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 til:

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

Fungerer til 1-dimensionelle heltalsarrays. Dette kunne optimeres yderligere, men det er bestemt ikke nødvendigt for dette spørgsmåls omfang.
ORDER BY for at pålægge den rækkefølge, der vises i spørgsmålet.

Angiv NULL eller tom matrix som NULL er nævnt i kommentarerne.

Testet med PostgreSQL 9.1, men burde fungere med enhver halvvejs moderne version.array_lower() og array_upper() har eksisteret i det mindste siden PostgreSQL 7.4. Kun parameterstandarder er nye i version 8.4. Kunne nemt udskiftes.

Ydeevnen er anstændig.

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

511 rækker, samlet køretid:7,729 ms

Forklaring

Den bygger på denne enkle form der kun skaber alle kombinationer af tilstødende elementer:

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 dette vil mislykkes for sub-arrays med mere end to elementer. Så:

• For ethvert underarray med 3 elementer tilføjes et array med kun de ydre to elementer. dette er en genvej til dette specielle tilfælde, der forbedrer ydeevnen og er ikke strengt nødvendigt .

• For enhver sub-array med mere end 3 elementer tager jeg de ydre to elementer og udfyld med alle kombinationer af indre elementer bygget af den samme funktion rekursivt .