Thread: powerset?

Does anybody have a stored proc they'd like to share (preferably pl/
pgsql) that generates the power set of an array? For instance:

select powerset({1,2,3});

....would give 8 rows:

{}
{1}
{2}
{3}
{1,2}
{2,3}
{1,3}
{1,2,3}

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

On Sat, Sep 23, 2006 at 11:47:59PM -0600, Michael Fuhr wrote:
>     FOR i IN 0 .. (1 << (aupper - alower + 1)) - 1 LOOP

To handle empty arrays this should be:

FOR i IN 0 .. COALESCE((1 << (aupper - alower + 1)) - 1, 0) LOOP

--
Michael Fuhr

Very nice, thanks!

On Sep 23, 2006, at 10:47 PM, Michael Fuhr wrote:

> 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