Jak napsat kombinatorickou funkci v postgresu?

Když jsem se nad tím vyspal, dostal jsem úplně nový, jednodušší a rychlejší nápad:

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

Volejte:

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

512 řádků, celková doba běhu:2,899 ms

Vysvětlete

• Zvláštní případy ošetřete pomocí NULL a prázdné pole.
• Vytvářejte kombinace pro primitivní pole dvou.
• Jakékoli delší pole je rozděleno na:
  • kombinace pro stejné pole délky n-1
  • plus všechny zkombinované s prvkem n .. rekurzivně .

Opravdu jednoduché, jakmile to máte.

• Funguje pro jednorozměrná celočíselná pole začínající dolním indexem 1 (viz níže).
• 2–3krát rychlejší než staré řešení, lépe se škáluje.
• Funguje pro jakékoli znovu typ prvku (pomocí polymorfních typů).
• Zahrnuje do výsledku prázdné pole, jak je zobrazeno v otázce (a jak mě @Craig upozornil v komentářích).
• Kratší, elegantnější.

To předpokládá dolní indexy pole od 1 (Výchozí). Pokud si svými hodnotami nejste jisti, zavolejte funkci takto pro normalizaci:

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

Nejste si jisti, zda existuje elegantnější způsob normalizace dolních indexů pole. Poslal jsem k tomu otázku:
Normalizujte dolní indexy pole pro jednorozměrné pole, aby začínaly 1

Staré řešení (pomalejší)

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

Volejte:

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

Funguje pro jednorozměrná celočíselná pole. Toto by mohlo být dále optimalizováno, ale pro rozsah této otázky to rozhodně není potřeba.
ORDER BY uložit příkaz zobrazený v otázce.

Zadejte NULL nebo prázdné pole jako NULL je uvedeno v komentářích.

Testováno s PostgreSQL 9.1, ale mělo by fungovat s jakoukoli napůl moderní verzí.array_lower() a array_upper() existují minimálně od PostgreSQL 7.4. Ve verzi 8.4 jsou nové pouze výchozí parametry. Lze snadno vyměnit.

Výkon je slušný.

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

511 řádků, celková doba běhu:7,729 ms

Vysvětlení

Staví na tomto jednoduchém formuláři který vytváří pouze všechny kombinace sousedních prvků:

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

To se však nezdaří u dílčích polí s více než dvěma prvky. Takže:

• Pro jakékoli dílčí pole se 3 prvky se přidá jedno pole pouze s vnějšími dvěma prvky. toto je zkratka pro tento speciální případ, který zlepšuje výkon a není nezbytně nutný .

• Pro jakékoli dílčí pole s více než 3 prvky beru vnější dva prvky a vyplňte všemi kombinacemi vnitřních prvků vytvořené stejnou funkcí rekurzivně .