Power Set

From Rosetta Code

Jump to: navigation, search

Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.

Code examples should be formatted along the lines of one of the existing prototypes.
A Set is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be seen as an associative array (partial mapping) in which the value of each key-value pair is ignored.

Given a set S, the Power Set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.
Task : By using a library or build-in set type, or defining a set type with necessary operations, write a function with a set S as input that yields a power set 2S of S.

Contents

[edit] Ada

 
with Ada.Text_IO;  use Ada.Text_IO;
 
procedure Power_Set is
   type Universe is (A,B,C,D,E);
 
   -- The type Set are subsets of Universe
   type Set is array (Universe) of Boolean;
   Empty : constant Set := (others => False);
   function Cardinality (X : Set) return Natural is
      N : Natural := 0;
   begin
      for I in X'Range loop
         if X (I) then
            N := N + 1;
         end if;
      end loop;
      return N;
   end Cardinality;
   function Element (X : Set; Position : Positive) return Universe is
      N : Natural := 0;
   begin
      for I in X'Range loop
         if X (I) then
            N := N + 1;
            if N = Position then
               return I;
            end if;
         end if;
      end loop;
      raise Constraint_Error;
   end Element;
   procedure Put (X : Set) is
      Empty : Boolean := True;
   begin
      for I in X'Range loop
         if X (I) then
            if Empty then
               Empty := False;
               Put (Universe'Image (I));
            else
               Put ("," & Universe'Image (I));
            end if;
         end if;
      end loop;
      if Empty then
         Put ("empty");
      end if;
   end Put;
 
   -- Set_Of_Set are sets of subsets of Universe
   type Set_Of_Sets is array (Positive range <>) of Set;
 
   function Power (X : Set) return Set_Of_Sets is
      Length : constant Natural := Cardinality (X);
      Index  : array (0..Length) of Integer := (others => 0);
      Result : Set_Of_Sets (1..2**Length)   := (others => Empty);
   begin
      for N in Result'Range loop
         for I in 1..Length loop -- Index determines the sample N
            exit when Index (I) = 0;
            Result (N) (Element (X, Index (I))) := True;
         end loop;
         for I in 1..Length loop -- Computing the index of the following sample
            Index (I) := Index (I) + 1;
            exit when Index (I) <= Length;
            Index (I) := Index (I - 1) + 1;
         end loop;
      end loop;
      return Result;
   end Power;
 
   P : Set_Of_Sets := Power ((A|C|E => True, others => False));
begin
   for I in P'Range loop
      New_Line;
      Put (P (I));
   end loop;
end Power_Set;
 

This example computes the power set of {A,C,E}. Sample output: 

empty
A
C
E
A,C
A,E
C,E
A,C,E

[edit] D

Implements an (incomplete) immutable set type mimic python's frozenset, then the powset function is defined. 

module powset ;
import std.stdio, std.format : fmx = format ;
 
class Set(T) {
  alias Set!(T) Z ;
  alias bool[T] S ; 
  private const S set ;
  private const size_t len ;
  private const hash_t hash ;
  private T[] memberList ;
  static Z emptySet() { return new Z ; }
  this() { this(cast(T[])null) ; }
  this(T k) { this([k]) ; }
  this(T[] k) { 
    S mset ; 
    foreach(e ; k) mset[e] = true ; 
    set = mset ; 
    memberList = set.keys.sort ;
    len = set.length ;
    hash_t h ;
    foreach(e ; memberList)
      h = h*0xfff1 + typeid(T).getHash(&e) ;
    hash = h ;
  }
  Z dup() { return new Z(memberList) ; }
  alias add opCat ;
  Z add(T k) { return new Z(memberList ~ k) ; }
  Z add(T[] k) { return new Z(memberList ~ k) ; }
  Z add(Z k) { return new Z(memberList ~ k.members) ; }
  alias contains opIn_r;
  bool contains(T k) { return (k in set)||false ; }
  bool isEmpty() { return len == 0 ; }
  T[] members() { return memberList.dup ; }
  size_t length() { return len ; }
  hash_t toHash() { return hash ; }
  string toString() { return fmx("<%s>", fmx("%s", memberList)[1..$-1]) ; } 
  private Z toZ(Object o) { 
    auto c = cast(Z) o ;
    if(c is null) throw new Exception("Compare to different type") ;
    return c ;
  }
  int opEquals(Object rhs) { return hash == toZ(rhs).toHash ;  }
  // opCmp only for sort, should not be equivalent <= to subsetof
  int opCmp(Object rhs) { return len - toZ(rhs).length ;  }
  int opApply(int delegate(inout T) dg) {
    foreach(e ; memberList) if(dg(e)) break ;
    return 1 ;
  } 
}
 
Set!(Set!(T)) powSet(T)(Set!(T) set) {
    Set!(T)[] ps = [Set!(T).emptySet] ;
    foreach(e ; set)
      foreach(ss ; ps)
        ps ~= ss.add(e) ;
    return new Set!(Set!(T))(ps) ;
}
 
void main() {
  Set!(int) iset = new Set!(int)([2,1]) ;
 
  auto pset = powSet(iset) ;
  writefln(iset) ;
  writefln(pset) ;
  writefln("set is in its powset? ", iset in pset) ;
  writefln(powSet(pset)) ;
}

Short alternative version, using just arrays: 

 
import std.stdio: writefln;
 
T[][] powerset(T)(T[] s) {
    auto r = new T[][](1, 0);
    foreach (e; s) {
        T[][] rs;
        foreach (x; r)
            rs ~= x ~ [e];
        r ~= rs;
    }
    return r;
}
 
void main() {
    writefln(powerset([1, 2, 3]));
}
 

[edit] Haskell

import Data.Set
import Control.Monad

powerset :: Ord a => Set a -> Set (Set a)
powerset = fromList . fmap fromList . listPowerset . toList

listPowerset :: [a] -> [[a]]
listPowerset = filterM (const [True, False])

listPowerset describes the result as all possible (using the list monad) filterings (using filterM) of the input list, regardless (using const) of each item's value. powerset simply converts the input and output from lists to sets.

Examples: 

*Main> listPowerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
*Main> powerset (Data.Set.fromList [1,2,3])
{{},{1},{1,2},{1,2,3},{1,3},{2},{2,3},{3}}

[edit] J

See J Wiki: Power Set.

Testing that there are no repeated values can occur through either error-avoidance or boolean result: 

nrv=: 3 : 'assert. y -: ~.y'
allunique=: -: ~.

[edit] Java

Works with: Java version 1.5+

[edit] Recursion

This implementation sorts each subset, but not the whole list of subsets (which would require a custom comparator). It also destroys the original set. 

public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> powSet(
		LinkedList<T> A){
	LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
	if(A.size() == 1){//if there's only one element, we know the answer
		ans.add(new LinkedList<T>());//empty set
		LinkedList<T> temp= new LinkedList<T>();
		temp.add(A.get(0));//and the only element in the original set
		ans.add(temp);
	}else{
		T first= A.remove(0);//save the first element
		LinkedList<LinkedList<T>> partial= powSet(A);//recursion call
		for(LinkedList<T> subset: partial){//for each set in the partial set
			ans.add(subset);//add it to the answer
			LinkedList<T> temp= new LinkedList<T>(subset);
			temp.add(first);//add the saved element to it
			Collections.sort(temp);//sort that set
			ans.add(temp);//add the new set to the answer
		}
	}
	return ans;
}

[edit] Binary String

This implementation works on idea that each element in the original set can either be in the power set or not in it. With n elements in the original set, each combination can be represented by a binary string of length n. To get all possible combinations, all you need is a counter from 0 to 2n - 1. If the kth bit in the binary string is 1, the kth element of the original set is in this combination. 

public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet(
		LinkedList<T> A){
	LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
	int ansSize = (int)Math.pow(2, A.size());
	for(Integer i= 0;i< ansSize;++i){
		String bin= Integer.toString(i, 2); //convert to binary
		while(bin.length() < A.size())bin = "0" + bin; //pad with 0's
		LinkedList<T> thisComb = new LinkedList<T>(); //place to put one combination
		for(int j= 0;j< A.size();++j){
			if(bin.charAt(j) == '1')thisComb.add(A.get(j));
		}
		Collections.sort(thisComb); //sort it for easy checking
		ans.add(thisComb); //put this set in the answer list
	}
	return ans;
}

[edit] OCaml

The standard library already implements a proper Set datatype. As the base type is unspecified, the powerset must be parameterized as a module. Also, the library is lacking a map operation, which we have to implement first. 

 
module PowerSet(S: Set.S) =
struct
 
  include Set.Make (S)
 
  let map f s =
    let work x r = add (f x) r in
    fold work s empty
  ;;
 
  let powerset s = 
    let base = singleton (S.empty) in
    let work x r = union r (map (S.add x) r) in 
    S.fold work s base
  ;;
 
end;; (* PowerSet *)
 

[edit] Python

def list_powerset(lst):
    # the power set of the empty set has one element, the empty set
    result = [[]]
    for x in lst:
        # for every additional element in our set
        # the power set consists of the subsets that don't
        # contain this element (just take the previous power set)
        # plus the subsets that do contain the element (use list
        # comprehension to add [x] onto everything in the
        # previous power set)
        result.extend([subset + [x] for subset in result])
    return result
 
# the above function in one statement
def list_powerset2(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])
 
def powerset(s):
    return frozenset(map(frozenset, list_powerset(list(s))))

list_powerset computes the power set of a list of distinct elements. powerset simply converts the input and output from lists to sets. We use the frozenset type here for immutable sets, because unlike mutable sets, it can be put into other sets.

Example: 

>>> list_powerset([1,2,3])
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
>>> powerset(frozenset([1,2,3]))
frozenset([frozenset([3]), frozenset([1, 2]), frozenset([]), frozenset([2, 3]), frozenset([1]), frozenset([1, 3]), frozenset([1, 2, 3]), frozenset([2])])

A short recursive solution: 

 
def powerset(s):
    r = [[]]
    for e in s:
        r += [x+[e] for x in r]
    return r
 
print powerset([1, 2, 3])
 

The output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

[edit] Ruby

 
# Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ 
# See the link if you want a shorter version. This was intended to show the reader how the method works. 
class Array  
  # Adds a power_set method to every array, i.e.: [1, 2].power_set
  def power_set  
 
    # Injects into a blank array of arrays.
    # acc is what we're injecting into
    # you is each element of the array
    inject([[]]) do |acc, you|
 
      # Set up a new array to add into
      ret = []
 
      # For each array in the injected array,
      acc.each do |i|
 
        # Add itself into the new array
        ret << i
 
        # Merge the array with a new array of the current element
        ret << i + [you]
      end
 
      # Return the array we're looking at to inject more.
      ret
 
    end
 
  end
 
end
 
Retrieved from "http://rosettacode.org/wiki/Power_Set"
Personal tools