Wie schreibe ich eine Kombinatorik-Funktion in Postgres?

Nachdem ich darüber geschlafen hatte, hatte ich eine ganz neue, einfachere, schnellere Idee:

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

Aufruf:

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

512 Zeilen, Gesamtlaufzeit:2,899 ms

Erklären

• Behandeln Sie Sonderfälle mit NULL und leeres Array.
• Erstellen Sie Kombinationen für ein primitives Array aus zwei.
• Jedes längere Array wird zerlegt in:
  • die Kombinationen für das gleiche Array der Länge n-1
  • plus all jene kombiniert mit Element n .. rekursiv .

Wirklich einfach, sobald Sie es verstanden haben.

• Funktioniert für eindimensionale Integer-Arrays beginnend mit Index 1 (siehe unten).
• 2- bis 3-mal so schnell wie die alte Lösung, skaliert besser.
• Funktioniert für alle Elementtyp erneut (unter Verwendung polymorpher Typen).
• Schließt das leere Array in das Ergebnis ein, wie es in der Frage angezeigt wird (und wie @Craig mich in den Kommentaren darauf hingewiesen hat).
• Kürzer, eleganter.

Dies setzt Array-Subskripte voraus ab 1 (Standard). Wenn Sie sich bezüglich Ihrer Werte nicht sicher sind, rufen Sie die Funktion zum Normalisieren folgendermaßen auf:

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

Ich bin mir nicht sicher, ob es eine elegantere Möglichkeit gibt, Array-Indizes zu normalisieren. Ich habe dazu eine Frage gestellt:
Array-Indizes für eindimensionale Arrays normalisieren, damit sie beginnen 1

Alte Lösung (langsamer)

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

Aufruf:

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

Funktioniert für 1-dimensionale Integer-Arrays. Dies könnte weiter optimiert werden, aber das ist für den Umfang dieser Frage sicherlich nicht erforderlich.
ORDER BY um den in der Frage angezeigten Befehl zu erteilen.

Stellen Sie NULL oder ein leeres Array als NULL bereit wird in den Kommentaren erwähnt.

Getestet mit PostgreSQL 9.1, sollte aber mit jeder halbwegs modernen Version funktionieren. FUNKTIONSTABELLE">array_lower() und array_upper() gibt es mindestens seit PostgreSQL 7.4. Lediglich Parametervorgaben sind neu in Version 8.4. Könnte leicht ersetzt werden.

Die Leistung ist anständig.

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

511 Zeilen, Gesamtlaufzeit:7,729 ms

Erklärung

Es baut auf dieser einfachen Form auf die nur alle Kombinationen benachbarter Elemente erzeugt:

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

Dies wird jedoch bei Unterarrays mit mehr als zwei Elementen fehlschlagen. Also:

• Für jedes Sub-Array mit 3 Elementen wird ein Array mit nur den beiden äußeren Elementen hinzugefügt. Dies ist eine Abkürzung für diesen speziellen Fall, die die Leistung verbessert und nicht unbedingt erforderlich ist .

• Für jedes Subarray mit mehr als 3 Elementen nehme ich die äußeren zwei Elemente und füllen Sie alle Kombinationen innerer Elemente aus von derselben Funktion rekursiv aufgebaut .