Re: powerset?

[Michael Fuhr <mike@xxxxxxxx>]

On Fri, Sep 22, 2006 at 11:38:12PM -0700, Ben wrote:
> Does anybody have a stored proc they'd like to share (preferably pl/ 
> pgsql) that generates the power set of an array?

Here's an attempt:

CREATE FUNCTION powerset(a anyarray) RETURNS SETOF anyarray AS $$
DECLARE
    retval  a%TYPE;
    alower  integer := array_lower(a, 1);
    aupper  integer := array_upper(a, 1);
    j       integer;
    k       integer;
BEGIN
    FOR i IN 0 .. (1 << (aupper - alower + 1)) - 1 LOOP
        retval := '{}';
        j := alower;
        k := i;

        WHILE k > 0 LOOP
            IF k & 1 = 1 THEN
                retval := array_append(retval, a[j]);
            END IF;

            j := j + 1;
            k := k >> 1;
        END LOOP;

        RETURN NEXT retval;
    END LOOP;

    RETURN;
END;
$$ LANGUAGE plpgsql IMMUTABLE STRICT;

Since this is a set-returning function you'd call it as follows:

SELECT * FROM powerset(ARRAY[1,2,3]);
 powerset 
----------
 {}
 {1}
 {2}
 {1,2}
 {3}
 {1,3}
 {2,3}
 {1,2,3}
(8 rows)

If you wrap the PL/pgSQL function with an SQL function then you
could call it from the SELECT list:

CREATE FUNCTION powerset2(anyarray) RETURNS SETOF anyarray AS $$
    SELECT * FROM powerset($1);
$$ LANGUAGE sql IMMUTABLE STRICT;

CREATE TABLE foo (id serial PRIMARY KEY, a integer[]);
INSERT INTO foo (a) VALUES ('{1,2}');
INSERT INTO foo (a) VALUES ('{10,20,30}');

SELECT id, powerset2(a) FROM foo;
 id | powerset2  
----+------------
  1 | {}
  1 | {1}
  1 | {2}
  1 | {1,2}
  2 | {}
  2 | {10}
  2 | {20}
  2 | {10,20}
  2 | {30}
  2 | {10,30}
  2 | {20,30}
  2 | {10,20,30}
(12 rows)

Will that work for you?

-- 
Michael Fuhr