Hoe de combinatorische functie in postgres te schrijven?

Nadat ik erover geslapen had, had ik een heel nieuw, eenvoudiger en sneller 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$;

Bel:

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

512 rijen, totale looptijd:2,899 ms

Uitleggen

Behandel speciale gevallen met NULL en lege array.
Bouw combinaties voor een primitieve reeks van twee.
Elke langere array wordt onderverdeeld in:
- de combinaties voor dezelfde array met lengte n-1
- plus al die gecombineerd met element n .. recursief .

Heel eenvoudig, als je het eenmaal door hebt.

Werkt voor 1-dimensionale integer-arrays die beginnen met subscript 1 (zie hieronder).
2-3 keer zo snel als oude oplossing, schaalt beter.
Werkt voor elke elementtype opnieuw (met behulp van polymorfe typen).
Neemt de lege array op in het resultaat zoals weergegeven in de vraag (en zoals @Craig mij in de opmerkingen heeft aangegeven).
Korter, eleganter.

Dit veronderstelt array-subscripts beginnend bij 1 (Standaard). Als u niet zeker bent van uw waarden, roept u de functie als volgt aan om te normaliseren:

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

Ik weet niet zeker of er een elegantere manier is om array-subscripts te normaliseren. Ik heb daarover een vraag gepost:
Normaliseer array-subscripts voor 1-dimensionale array, zodat ze beginnen met 1

Oude oplossing (langzamer)

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

Bel:

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

Werkt voor 1-dimensionale integer-arrays. Dit kan verder worden geoptimaliseerd, maar dat is zeker niet nodig voor de reikwijdte van deze vraag.
ORDER BY om de volgorde op te leggen die in de vraag wordt weergegeven.

Geef NULL of lege array op, als NULL wordt vermeld in de opmerkingen.

Getest met PostgreSQL 9.1, maar zou moeten werken met elke half moderne versie.array_lower() en array_upper() bestaan al sinds PostgreSQL 7.4. Alleen de standaardinstellingen van parameters zijn nieuw in versie 8.4. Kan gemakkelijk worden vervangen.

Prestaties zijn redelijk.

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

511 rijen, totale looptijd:7,729 ms

Uitleg

Het bouwt voort op deze eenvoudige vorm die alleen alle combinaties van aangrenzende elementen creëert:

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

Maar dit zal mislukken voor sub-arrays met meer dan twee elementen. Dus:

Voor elke subarray met 3 elementen wordt één array met alleen de buitenste twee elementen toegevoegd. dit is een snelkoppeling voor dit speciale geval dat de prestaties verbetert en is niet strikt nodig .
Voor elke subarray met meer dan 3 elementen neem ik de buitenste twee elementen en vul in met alle combinaties van innerlijke elementen gebouwd door dezelfde functie recursief .