Unique constraint for permutations across multiple columns

You could use hstore to create the unique index:

CREATE UNIQUE INDEX hidx ON test USING BTREE (hstore(ARRAY[a,b,c], ARRAY[a,b,c]));

Fiddle

UPDATE

Actually

CREATE UNIQUE INDEX hidx ON test USING BTREE (hstore(ARRAY[a,b,c], ARRAY[null,null,null]));

might be a better idea since it will work the same but should take less space (fiddle).

For only three columns this unique index using only basic expressions should perform very well. No additional modules like hstore or custom function needed:

CREATE UNIQUE INDEX t_abc_uni_idx ON t (
  LEAST(a,b,c)
, GREATEST(LEAST(a,b), LEAST(b,c), LEAST(a,c))
, GREATEST(a,b,c)
);

SQL fiddle

Also needs the least disk space:

SELECT pg_column_size(row(hstore(t))) AS hst_row
      ,pg_column_size(row(hstore(ARRAY[a,b,c], ARRAY[a,b,c]))) AS hst1
      ,pg_column_size(row(hstore(ARRAY[a,b,c], ARRAY[null,null,null]))) AS hst2
      ,pg_column_size(row(ARRAY[a,b,c])) AS arr
      ,pg_column_size(row(LEAST(a,b,c)
                        , GREATEST(LEAST(a,b), LEAST(b,c), LEAST(a,c))
                        , GREATEST(a,b,c))) AS columns
FROM t;

 hst_row | hst1 | hst2 | arr | columns
---------+------+------+-----+---------
      59 |   59 |   56 |  69 |      30

Numbers are bytes for index row in the example in the fiddle, measured with pg_column_size(). My example uses only single characters, the difference in size is constant.

You can do this by creating a unique index on a function which returns a sorted array of the values in the columns:

CREATE OR REPLACE FUNCTION sorted_array(anyarray)
RETURNS anyarray
AS $BODY$
  SELECT array_agg(x) FROM (SELECT unnest($1) AS x FROM test ORDER BY x) AS y;
$BODY$
LANGUAGE sql IMMUTABLE;

CREATE UNIQUE index ON test (sorted_array(array[first,second,third]));