Как да напиша комбинаторна функция в postgres?

След като го преспах, имах напълно нова, по-проста и по-бърза идея:

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

Обаждане:

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

512 реда, общо време на изпълнение:2,899 ms

Обяснете

• Третиране на специални случаи с NULL и празен масив.
• Изградете комбинации за примитивен масив от две.
• Всеки по-дълъг масив се разбива на:
  • комбинациите за същия масив с дължина n-1
  • плюс всички тези, комбинирани с елемент n .. рекурсивно .

Наистина просто, след като го разберете.

• Работи за едномерни масиви с цели числа, започващи с долен индекс 1 (вижте по-долу).
• 2-3 пъти по-бързо от старото решение, мащабира се по-добре.
• Работи за всеки тип елемент отново (използвайки полиморфни типове).
• Включва празния масив в резултата, както е показано във въпроса (и както @Craig ми посочи в коментарите).
• По-къси, по-елегантни.

Това предполага индекси на масив започва от1 (По подразбиране). Ако не сте сигурни за вашите стойности, извикайте функцията по този начин, за да нормализирате:

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

Не съм сигурен дали има по-елегантен начин за нормализиране на индексите на масива. Публикувах въпрос за това:
Нормализиране на индексите на масива за 1-измерен масив, така че да започват с 1

Старо решение (по-бавно)

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

Обаждане:

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

Работи за едномерни масиви с цели числа. Това може да бъде допълнително оптимизирано, но това със сигурност не е необходимо за обхвата на този въпрос.
ORDER BY за налагане на реда, показан във въпроса.

Осигурете NULL или празен масив, като NULL се споменава в коментарите.

Тестван с PostgreSQL 9.1, но трябва да работи с всяка съвременна версия.array_lower() и array_upper() съществуват поне от PostgreSQL 7.4. Само параметрите по подразбиране са нови във версия 8.4. Може лесно да се замени.

Производителността е прилична.

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

511 реда, общо време на изпълнение:7,729 ms

Обяснение

Той се основава на тази проста форма който създава само всички комбинации от съседни елементи:

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

Но това няма да успее за подмасиви с повече от два елемента. И така:

• За всеки подмасив с 3 елемента се добавя един масив само с външните два елемента. това е пряк път за този специален случай, който подобрява производителността и не е строго необходим .

• За всеки подмасив с повече от 3 елемента вземам външните два елемента и попълнете с всички комбинации от вътрешни елементи изграден от същата функция рекурсивно .