Come scrivere la funzione combinatoria in postgres?

Dopo averci dormito sopra, ho avuto un'idea completamente nuova, più semplice e più veloce:

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

Chiama:

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

512 righe, tempo di esecuzione totale:2,899 ms

Spiega

Tratta casi speciali con NULL e array vuoto.
Crea combinazioni per un array primitivo di due.
Qualsiasi array più lungo è suddiviso in:
- le combinazioni per lo stesso array di lunghezza n-1
- più tutti quelli combinati con l'elemento n .. ricorsivamente .

Davvero semplice, una volta capito.

Funziona con array di interi unidimensionali che iniziano con pedice 1 (vedi sotto).
2-3 volte più veloce della vecchia soluzione, scala meglio.
Funziona con qualsiasi tipo di elemento di nuovo (usando tipi polimorfici).
Include l'array vuoto nel risultato come mostrato nella domanda (e come mi ha fatto notare @Craig nei commenti).
Più corto, più elegante.

Ciò presuppone indici array a partire da 1 (Predefinito). Se non sei sicuro dei tuoi valori, chiama la funzione in questo modo per normalizzare:

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

Non sono sicuro che esista un modo più elegante per normalizzare gli indici di array. Ho postato una domanda al riguardo:
Normalizza gli indici dell'array per l'array unidimensionale in modo che inizino con 1

Vecchia soluzione (più lenta)

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

Chiama:

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

Funziona per array di interi unidimensionali. Questo potrebbe essere ulteriormente ottimizzato, ma non è certamente necessario per lo scopo di questa domanda.
ORDER BY per imporre l'ordine visualizzato nella domanda.

Fornisci NULL o array vuoto, come NULL è menzionato nei commenti.

Testato con PostgreSQL 9.1, ma dovrebbe funzionare con qualsiasi versione semimoderna.array_lower() e array_upper() sono in circolazione almeno da PostgreSQL 7.4. Solo i parametri predefiniti sono nuovi nella versione 8.4. Potrebbe essere facilmente sostituito.

Le prestazioni sono decenti.

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

511 righe, tempo di esecuzione totale:7,729 ms

Spiegazione

Si basa su questa forma semplice che crea solo tutte le combinazioni di elementi vicini:

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

Ma questo fallirà per i sottoarray con più di due elementi. Quindi:

Per qualsiasi sottoarray con 3 elementi viene aggiunto un array con solo i due elementi esterni. questa è una scorciatoia per questo caso speciale che migliora le prestazioni e non è strettamente necessaria .
Per qualsiasi sottoarray con più di 3 elementi prendo i due elementi esterni e compila con tutte le combinazioni di elementi interni costruito dalla stessa funzione ricorsivamente .