Como escrever a função combinatória no postgres?

Depois de dormir sobre ele, tive uma ideia completamente nova, mais simples e mais rápida:

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

Ligar:

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

512 linhas, tempo de execução total:2,899 ms

Explicar

Trate casos especiais com NULL e matriz vazia.
Crie combinações para uma matriz primitiva de dois.
Qualquer array mais longo é dividido em:
- as combinações para o mesmo array de comprimento n-1
- mais todos aqueles combinados com o elemento n .. recursivamente .

Realmente simples, uma vez que você conseguiu.

Funciona para matrizes inteiras unidimensionais começando com subscrito 1 (veja abaixo).
2 a 3 vezes mais rápido que a solução antiga, escalável melhor.
Funciona para qualquer tipo de elemento novamente (usando tipos polimórficos).
Inclui a matriz vazia no resultado, conforme exibido na pergunta (e como @Craig apontou para mim nos comentários).
Curto, mais elegante.

Isso pressupõe subscripts de matriz começando em 1 (Predefinição). Se você não tiver certeza sobre seus valores, chame a função assim para normalizar:

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

Não tenho certeza se existe uma maneira mais elegante de normalizar subscritos de matriz. Postei uma pergunta sobre isso:
Normalize os subscritos de matriz para matriz unidimensional para que comecem com 1

Solução antiga (mais 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$;

Ligar:

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

Funciona para matrizes inteiras unidimensionais. Isso pode ser otimizado ainda mais, mas certamente não é necessário para o escopo desta questão.
ORDER BY para impor a ordem exibida na pergunta.

Forneça NULL ou array vazio, como NULL é mencionado nos comentários.

Testado com o PostgreSQL 9.1, mas deve funcionar com qualquer versão meio moderna.array_lower() e array_upper() existem pelo menos desde o PostgreSQL 7.4. Apenas os padrões de parâmetro são novos na versão 8.4. Poderia ser facilmente substituído.

O desempenho é decente.

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

511 linhas, tempo de execução total:7,729 ms

Explicação

Ele se baseia neste forma simples que apenas cria todas as combinações de elementos vizinhos:

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

Mas isso falhará para submatrizes com mais de dois elementos. Então:

Para qualquer sub-array com 3 elementos, um array com apenas os dois elementos externos é adicionado. este é um atalho para este caso especial que melhora o desempenho e não é estritamente necessário .
Para qualquer sub-matriz com mais de 3 elementos, tomo os dois elementos externos e preencha com todas as combinações de elementos internos construído pela mesma função recursivamente .