Programming Praxis

9 Responses to “Powerset”

1. FA said

   July 7, 2015 at 10:07 AM

   Scala:
   package programmingpraxis

   object PowerSet {
   val s = Set[Int](1, 2, 3) //> s : scala.collection.immutable.Set[Int] = Set(1, 2, 3)

   //Scala default algorythm:
   s.subsets().toList //> res0: List[scala.collection.immutable.Set[Int]] = List(Set(), Set(1), Set(2),
   //| Set(3), Set(1, 2), Set(1, 3), Set(2, 3), Set(1, 2, 3))

   //Own dummy algo:
   def subsets[T](s: Set[T]): Set[Set[T]] = {
   if (s.isEmpty) Set(s);
   else {
   Set(s)++((for (i subsets: [T](s: Set[T])Set[Set[T]]

   subsets(Set(1, 2,3)) //> res1: Set[Set[Int]] = Set(Set(), Set(1, 3), Set(2), Set(1, 2), Set(2, 3), Se
   //| t(3), Set(1, 2, 3), Set(1))
   }
2. Francesco said

   July 7, 2015 at 2:47 PM

   Haskell:

   import Control.Monad
   let f xs = filterM (\x -> [True, False]) xs
   

   λ> f [1,2,3]
   [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
3. Mike said

   July 7, 2015 at 9:22 PM

   import itertools as it
   
   def powerset(lst):
   	for n in range(len(lst)+1):
   		yield from it.combinations(lst, n)
   
4. Jussi Piitulainen said

   July 8, 2015 at 6:16 AM

   Python’s itertools.compress filters data elements in at 1-bits (True), out at 0-bits (False):

   from itertools import compress
   def poweriter(data):
       for n in range(2 ** len(data)):
           yield list(compress(data, map(int, reversed(bin(n)[2:]))))
   
5. Catalin Cristu (@catalin_c) said

   July 8, 2015 at 12:38 PM

   A Java version:

   import java.math.BigInteger;
   import java.util.*;
   
   import static java.math.BigInteger.ONE;
   import static java.math.BigInteger.ZERO;
   
   public class PowerSet {
   
     public static <T> Set<Set<T>> of(Set<T> set) {
       List<T> items = new ArrayList<>(set);
       Set<Set<T>> powerSet = new HashSet<>();
       BigInteger max = new BigInteger("2").pow(set.size());
       for (BigInteger b = ZERO; b.compareTo(max) < 0; b = b.add(ONE)) {
         Set<T> subSet = new HashSet<>();
         for (int i = 0; i < b.bitLength(); i++) {
           if (b.testBit(i)) {
             subSet.add(items.get(i));
           }
         }
         powerSet.add(subSet);
       }
       return powerSet;
     }
   
     public static void main(String[] args) {
       Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3));
       Set<Set<Integer>> powerSet = of(set);
       System.out.println(powerSet);
     }
   
   }
   
6. matthew said

   July 8, 2015 at 7:26 PM

   Here’s three solutions in Haskell – just for fun, we generate the subsets in Gray code order. pset3 also works with lazy lists:

   f t a = t ++ map (a:) (reverse t)
   g t [] = []
   g t (a:s) = u ++ g (t ++ u) s where u = map (a:) (reverse t)
   pset1 = map reverse . foldl f [[]]
   pset2 = map reverse . foldr (flip f) [[]] . reverse
   pset3 = map reverse . ([]:) . g [[]]
   
   main = 
        print (pset1 [1,2,3,4]) >>
        print (pset2 [1,2,3,4]) >>
        print (pset3 [1,2,3,4]) >>
        print (take 16 (pset3 [1..]))
   
   -- [[[],[1],[1,2],[2],[2,3],[1,2,3],[1,3],[3],[3,4],[1,3,4],[1,2,3,4],[2,3,4],[2,4],[1,2,4],[1,4],[4]]
   
7. UndeadPotato said

   July 18, 2015 at 5:07 PM

   Using R7RS Scheme with SRFI-113

   https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/07-07-2015.scm
8. Mark said

   July 25, 2015 at 4:04 AM

   A non-bitset based solution in C++:

   #include 
   #include 
   #include 
   #include 
   #include 
   #include 
   
   using set_t = std::vector;
   
   std::vector powerset(const set_t &set) {
     std::vector result {{}};
     for (const std::string &item : set) {
       std::size_t n = result.size();
       for (std::size_t i = 0; i length() != 0) {
           set.push_back(*it);
         }
       }
   
       auto pset = powerset(set);
       std::cout << '(';
       for (auto it = pset.begin(); it != pset.end(); ++it) {
         if (it != pset.begin()) {
           std::cout << ' ';
         }
         std::cout <begin(); iit != it->end(); ++iit) {
           if (iit != it->begin()) {
             std::cout << ' ';
           }
           std::cout << *iit;
         }
         std::cout << ')';
       }
       std::cout << ')' << std::endl;
     }
   
     return 0;
   }
   
9. Mark said

   July 25, 2015 at 4:06 AM

   Huh… sorry, my posted solution got mangled. Here it is in full:

   
   

   	#include <algorithm>
   	#include <iostream>
   	#include <iterator>
   	#include <regex>
   	#include <string>
   	#include <vector>
   	using set_t = std::vector<std::string>;
   	std::vector<set_t> powerset(const set_t &set) {
   	std::vector<set_t> result {{}};
   	for (const std::string &item : set) {
   	std::size_t n = result.size();
   	for (std::size_t i = 0; i < n; ++i) {
   	set_t rset = result[i];
   	rset.push_back(item);
   	result.push_back(rset);
   	}
   	}
   	return result;
   	}
   	int main() {
   	const std::regex token_re("[(),\\s]+");
   	while (true) {
   	std::string input;
   	set_t set;
   	std::getline(std::cin, input);
   	if (input.length() == 0) {
   	break;
   	}
   	for (auto it = std::sregex_token_iterator(input.begin(), input.end(), token_re, -1);
   	it != std::sregex_token_iterator(); ++it) {
   	if (it->length() != 0) {
   	set.push_back(*it);
   	}
   	}
   	auto pset = powerset(set);
   	std::cout << '(';
   	for (auto it = pset.begin(); it != pset.end(); ++it) {
   	if (it != pset.begin()) {
   	std::cout << ' ';
   	}
   	std::cout << '(';
   	for (auto iit = it->begin(); iit != it->end(); ++iit) {
   	if (iit != it->begin()) {
   	std::cout << ' ';
   	}
   	std::cout << *iit;
   	}
   	std::cout << ')';
   	}
   	std::cout << ')' << std::endl;
   	}
   	return 0;
   	}

   view raw
   
   powerset.cc
   
   hosted with ❤ by GitHub