Bagaimana cara menulis fungsi kombinatorik di postgres?

Setelah saya tidur di atasnya, saya memiliki ide yang benar-benar baru, lebih sederhana, dan lebih cepat:

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

Telepon:

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

512 baris, total waktu proses:2,899 md

Jelaskan

• Perlakukan kasus khusus dengan NULL dan larik kosong.
• Bangun kombinasi untuk dua larik primitif.
• Array yang lebih panjang dipecah menjadi:
  • kombinasi untuk larik yang sama dengan panjang n-1
  • ditambah semua yang digabungkan dengan elemen n .. secara rekursif .

Sangat sederhana, begitu Anda mendapatkannya.

• Berfungsi untuk larik bilangan bulat 1 dimensi yang dimulai dengan subskrip 1 (lihat di bawah).
• 2-3 kali lebih cepat dari solusi lama, skala lebih baik.
• Berfungsi untuk apa saja tipe elemen lagi (menggunakan tipe polimorfik).
• Termasuk array kosong dalam hasil seperti yang ditampilkan dalam pertanyaan (dan seperti yang ditunjukkan @Craig kepada saya di komentar).
• Lebih pendek, lebih elegan.

Ini mengasumsikan subskrip array mulai dari 1 (Bawaan). Jika Anda tidak yakin dengan nilai Anda, panggil fungsi seperti ini untuk menormalkan:

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

Tidak yakin apakah ada cara yang lebih elegan untuk menormalkan subskrip array. Saya memposting pertanyaan tentang itu:
Normalkan subskrip array untuk array 1 dimensi sehingga mereka mulai dengan 1

Solusi lama (lebih lambat)

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

Telepon:

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

Berfungsi untuk array bilangan bulat 1 dimensi. Ini dapat dioptimalkan lebih lanjut, tetapi itu tentu saja tidak diperlukan untuk cakupan pertanyaan ini.
ORDER BY untuk memaksakan urutan yang ditampilkan dalam pertanyaan.

Berikan NULL atau array kosong, sebagai NULL disebutkan di komentar.

Diuji dengan PostgreSQL 9.1, tetapi harus bekerja dengan versi modern setengah jalan.array_lower() dan array_upper() telah ada setidaknya sejak PostgreSQL 7.4. Hanya default parameter yang baru di versi 8.4. Dapat dengan mudah diganti.

Performanya lumayan.

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

511 baris, total waktu proses:7,729 md

Penjelasan

Itu dibangun di atas formulir sederhana ini yang hanya membuat semua kombinasi elemen tetangga:

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

Tapi ini akan gagal untuk sub-array dengan lebih dari dua elemen. Jadi:

• Untuk setiap sub-array dengan 3 elemen, satu array hanya dengan dua elemen terluar ditambahkan. ini adalah jalan pintas untuk kasus khusus ini yang meningkatkan kinerja dan tidak sepenuhnya diperlukan .

• Untuk setiap sub-array dengan lebih dari 3 elemen, saya mengambil dua elemen terluar dan isi dengan semua kombinasi elemen dalam dibangun oleh fungsi yang sama secara rekursif .