Jak napisać funkcję kombinatoryczną w postgresie?

Po przespaniu się wpadłem na zupełnie nowy, prostszy i szybszy pomysł:

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

Zadzwoń:

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

512 rzędów, całkowity czas pracy:2,899 ms

Wyjaśnij

Traktuj specjalne przypadki za pomocą NULL i pusta tablica.
Zbuduj kombinacje dla podstawowej tablicy dwóch.
Każda dłuższa tablica jest podzielona na:
- kombinacje dla tej samej tablicy o długości n-1
- plus wszystkie te połączone z elementem n .. rekurencyjnie .

Naprawdę proste, gdy już to zrobisz.

Działa dla 1-wymiarowych tablic liczb całkowitych zaczynających się od indeksu dolnego 1 (patrz poniżej).
2-3 razy szybciej niż stare rozwiązanie, skaluje się lepiej.
Działa dla każdego typ elementu ponownie (używając typów polimorficznych).
Zawiera pustą tablicę w wyniku, tak jak jest to wyświetlane w pytaniu (i jak @Craig wskazał mi w komentarzach).
Krótszy, bardziej elegancki.

Zakłada się, że indeksy tablicy od 1 (Domyślna). Jeśli nie jesteś pewien swoich wartości, wywołaj funkcję w ten sposób, aby znormalizować:

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

Nie jestem pewien, czy istnieje bardziej elegancki sposób normalizacji indeksów tablicy. Wysłałem pytanie na ten temat:
Normalizuj indeksy tablicy dla tablicy 1-wymiarowej, aby zaczynały się od 1

Stare rozwiązanie (wolniej)

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

Zadzwoń:

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

Działa z jednowymiarowymi tablicami liczb całkowitych. Można to dalej zoptymalizować, ale z pewnością nie jest to potrzebne w przypadku zakresu tego pytania.
ORDER BY aby narzucić kolejność wyświetlaną w pytaniu.

Podaj NULL lub pustą tablicę, jako NULL jest wymieniony w komentarzach.

Przetestowane z PostgreSQL 9.1, ale powinno działać z każdą nowoczesną wersją w połowie drogi.array_lower() i array_upper() istnieje przynajmniej od czasu PostgreSQL 7.4. Tylko wartości domyślne parametrów są nowe w wersji 8.4. Można go łatwo wymienić.

Wydajność jest przyzwoita.

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

511 wierszy, całkowity czas pracy:7,729 ms

Wyjaśnienie

Opiera się na tym prostym formularzu który tworzy tylko wszystkie kombinacje sąsiednich elementów:

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

Ale to się nie powiedzie w przypadku podtablic z więcej niż dwoma elementami. A więc:

Dla każdej podtablicy z 3 elementami dodawana jest jedna tablica z dwoma zewnętrznymi elementami. jest to skrót do tego szczególnego przypadku, który poprawia wydajność i nie jest ściśle potrzebny .
Dla każdej podtablicy z więcej niż 3 elementami biorę dwa zewnętrzne elementy i wypełnij wszystkie kombinacje elementów wewnętrznych zbudowany przez tę samą funkcję rekurencyjnie .