Re: powerset?

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