View Full Version : Advanced programming exercise: Power set
slavik
June 11th, 2011, 03:20 PM
This particular exercise is not very complicated (should take 15min once you know the algorithm), but I feel it is nonetheless important for anyone to be able to do this.
The idea is that given a bunch of items to generate/output all combinations of the items.
The algorithm that you should eventually discover should be O(2^n).
NovaAesa
June 11th, 2011, 03:35 PM
Do you mean O(2^n) rather than O(n^2)?
Consider a set S whose cardinality is n. Then the cardinality of P(S) is 2^n, so you would need an algorithm at least as complex as O(2^n) to produce P(S).
EDIT:
My answer in scheme:
(define (powerset set)
(if (null? set) '(())
(let ((r (powerset (cdr set))))
(append r
(map (lambda (subset)
(cons (car set) subset))
r)))))
slavik
June 11th, 2011, 04:08 PM
Do you mean O(2^n) rather than O(n^2)?
Consider a set S whose cardinality is n. Then the cardinality of P(S) is 2^n, so you would need an algorithm at least as complex as O(2^n) to produce P(S).
EDIT:
My answer in scheme:
(define (powerset set)
(if (null? set) '(())
(let ((r (powerset (cdr set))))
(append r
(map (lambda (subset)
(cons (car set) subset))
r)))))
fixed, thanks.
krazyd
June 11th, 2011, 05:14 PM
Nonrecursive, in ruby
#!/usr/bin/ruby
def power_set set
p_set = []
(0..2**set.size1).each do bin_size
subset = []
bin_size.to_s(2).split(//).reverse.each_with_index do b,i
subset << set[i1] if b == "1"
end
p_set << subset
end
p_set
end
a = [1,2,3,4]
p power_set a
Reiger
June 11th, 2011, 05:45 PM
This is where Haskell shines:
{
 The idea is to generate a conceptually infinite list of “tails”
 of the input list, then take as many elements from it as we know
 that the real powerset will contain.

 Haskells lazy evaluation will then magically solve all problems.
 The $ to avoid a few parentheses, the let... in construct allows
 us to explicitly evaluate length x only once.
}
powerset = (\x> let l = length x in take (2^l) $ iterate tail x)
Thewhistlingwind
June 11th, 2011, 09:52 PM
The idea is that given a bunch of items to generate/output all combinations of the items.
As a number, or actually output all of them? (The latter is more interesting.)
slavik
June 11th, 2011, 10:39 PM
As a number, or actually output all of them? (The latter is more interesting.)
what you quoted is the answer to your question. :)
BkkBonanza
June 11th, 2011, 10:52 PM
Are you expecting code for set of any size N, or are we able to assume some limit?
I'd like to play with enumerating sets by counting to 2^N but if more than 32 items it gets a bit messy without having BIGNUM type math handy. At least that's what I initially see here.
Thewhistlingwind
June 11th, 2011, 10:57 PM
what you quoted is the answer to your question. :)
Well if it wasn't ambiguous I wouldn't be asking.
slavik
June 11th, 2011, 11:26 PM
Well if it wasn't ambiguous I wouldn't be asking.
it does say to output every combination. :)
slavik
June 11th, 2011, 11:27 PM
Are you expecting code for set of any size N, or are we able to assume some limit?
I'd like to play with enumerating sets by counting to 2^N but if more than 32 items it gets a bit messy without having BIGNUM type math handy. At least that's what I initially see here.
assume any limit you want :)
if you want to limit yourself to n^32, feel free. idea is that there is a bunch of things and you need all combinations of those items.
BkkBonanza
June 12th, 2011, 12:21 AM
Here's my first crack with shell version of Power Set...
# shell script to demo power set enumeration
echo "Enter items (separate with space or enter, end with CtrlD)"
items=( $( </dev/stdin ) )
echo
x=0
while [[ $x lt 2**${#items } ]]; do
c=0
echo n "{"
while [[ $c lt ${#items } ]]; do
if [[ $(($x & 2**$c)) ne 0 ]]; then
echo n "${items[$c]},"
fi
c=$(($c+1))
done
echo "}"
x=$(($x+1))
done
Sample run:
$ ./ps
Enter items (separate with space or enter, end with CtrlD)
sally jill
sue
fran
{}
{sally,}
{jill,}
{sally,jill,}
{sue,}
{sally,sue,}
{jill,sue,}
{sally,jill,sue,}
{fran,}
{sally,fran,}
{jill,fran,}
{sally,jill,fran,}
{sue,fran,}
{sally,sue,fran,}
{jill,sue,fran,}
{sally,jill,sue,fran,}
slavik
June 12th, 2011, 12:57 AM
judging by the quick responses, I think next exercise will go up tomorrow ...
worseisworser
June 12th, 2011, 01:14 AM
http://paste.lisp.org/display/36657
..i think i had a much shorter version of that laying around somewhere, but dunno.. :)
slavik
June 12th, 2011, 11:47 AM
My solution I wrote in 2008, was intended to be an OpenMP program, but that didn't work out for some reason.
/*
* combinations.c
*
* Copyright 2008 Vyacheslav Goltser <slavikg@gmail.com>
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*/
#include <stdio.h>
#include <omp.h>
#define ITEMS 26
inline unsigned long long int po2 (unsigned int p) {
unsigned long long int ret = 1;
while (p > 0) ret <<= 1;
return ret;
}
int main(int argc, char** argv)
{
int items[ITEMS] = {'A','B','C','D','E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
unsigned long long int max = po2(ITEMS)  1;
unsigned long long int counter = 0;
unsigned long long int tmpcounter;
unsigned long long int c;
//omp_set_num_threads(4);
//#pragma omp parallel for default(none) shared(max, items) private(counter, tmpcounter, c)
for (counter = 0; counter <= max; counter++) {
tmpcounter = counter;
c = 0;
while (tmpcounter > 0) {
if (tmpcounter & 1) {
printf("%c,", items[c]);
}
tmpcounter >>= 1;
c++;
}
printf("\b.\n");
}
return 0;
}
krazyd
June 12th, 2011, 12:56 PM
This is where Haskell shines:
{
 The idea is to generate a conceptually infinite list of “tails”
 of the input list, then take as many elements from it as we know
 that the real powerset will contain.

 Haskells lazy evaluation will then magically solve all problems.
 The $ to avoid a few parentheses, the let... in construct allows
 us to explicitly evaluate length x only once.
}
powerset = (\x> let l = length x in take (2^l) $ iterate tail x)
I don't know Haskell at all, but this is very impressive. Is it O(2^n)?
JupiterV2
June 12th, 2011, 09:49 PM
I thought I'd post my solution in C:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* USER: change type to int, char, or char* */
typedef int type;
struct map {
int key;
type value;
};
void
power_set (type* arr, const int sz)
{
int i;
int x = 1;
struct map* m = malloc (sizeof (struct map) * sz);
for (i = 0; i < sz; i++)
{
m[i].key = x << i;
m[i].value = arr[i];
}
printf ("{ ");
for (i = 0; i < pow (2, sz); i++)
{
int tmp = i;
printf ("{");
for (x = sz  1; x >= 0; x)
{
if (tmp  m[x].key >= 0)
{
/* USER: change format to %d, %c, or %s based on 'type' */
printf ("%d", (type) m[x].value);
tmp = m[x].key;
}
}
printf ("}, ");
}
printf ("}\n");
}
int
main (void)
{
/* USER: Uncomment one of the following sets in accordance to the 'type'
selected */
/* type set0[] = {1, 2, 3};*/
type set1[] = {1, 2, 3, 4, 5};
/* type set2[] = {'A', 'B', 'C', 'D', 'E'};*/
/* type* set3[] = {"ape", "bat", "cat", "dog", "elephant", "frog", "gnat"};*/
/* power_set ((void*) set0, sizeof (set0) / sizeof (int));*/
power_set ((void*) set1, sizeof (set1) / sizeof (int));
/* power_set ((void*) set2, sizeof (set2) / sizeof (char));*/
/* power_set ((void*) set3, sizeof (set3) / sizeof (char*));*/
return 0;
}
Due to the strong typing of C, I couldn't think of a truly generic system, so this is the closest I could hack together. I provided 4 test sets to demonstrate how it works.
My result set from the second power set:
{ {}, {1}, {2}, {21}, {3}, {31}, {32}, {321}, {4}, {41}, {42}, {421}, {43}, {431}, {432}, {4321}, {5}, {51}, {52}, {521}, {53}, {531}, {532}, {5321}, {54}, {541}, {542}, {5421}, {543}, {5431}, {5432}, {54321}, }
Time:
real 0m0.002s
user 0m0.000s
sys 0m0.000s
It occurred to me this morning that my solution could be improved in two ways: 1) I could increase efficiency and eliminate the need for the use of a math library by doing a simple bitshift in my 2nd for loop (for (i = 0; i < (1 << sz); i++)), and 2) I could increase the maximum length of the power set by increasing my iterators from int to long int or even long long int. I could squeeze an extra bit out by making them unsigned too. That said, I left my submission to stand as it does without modification.
kingtaurus
June 12th, 2011, 11:02 PM
Solution using templates in C++
(1) it relies upon the fact that elements are unique in std::set<type>
#include <iostream>
#include <set>
using namespace std;
typedef set<int> int_set;
typedef set<int_set> power_set;
typedef set<char> char_set;
typedef set<char_set> power_char_set;
template <typename T>
set<set<T> > make_power_set(const set<T> & a_set, set<set<T> >& power_set)
{
typedef typename set<T>::const_iterator set_citer;
power_set.insert(a_set);//add the set;
for(set_citer iter = a_set.begin(); iter != a_set.end(); ++iter)
{
set<T> copied_set(a_set);//copy the set ( subsequent operations are done on the copy)
copied_set.erase(*iter);//erase the element in copied_set
make_power_set(copied_set, power_set);//call make_power_set
}
return power_set;
}
int main(int argc, char * argv[])
{
int numbers[] = {0, 1, 2, 3, 4};
int_set current_set(numbers, numbers + 5);
char char_array[] = {'a','b','c','d','e','f'};
char_set my_char_set(char_array, char_array + 6);
power_set a;
make_power_set(current_set, a);
power_char_set b;
make_power_set(my_char_set, b);
cout << "size of current_set = " << current_set.size() << endl;
cout << "size of power_set a = " << a.size() << endl;
cout << "size of my_char_set = " << my_char_set.size() << endl;
cout << "size of power_set b = " << b.size() << endl;
for(power_set::iterator iter = a.begin();
iter != a.end();
++iter)
{
cout << "{ ";
char const* prefix = "";
for(int_set::iterator iter2 = iter>begin();
iter2 != iter>end();
++iter2)
{
std::cout << prefix << *iter2;
prefix = ", ";
}
cout << " }\n";
}
for(power_char_set::iterator iter = b.begin();
iter != b.end();
++iter)
{
cout << "{ ";
char const* prefix = "";
for(char_set::iterator iter2 = iter>begin();
iter2 != iter>end();
++iter2)
{
std::cout << prefix << *iter2;
prefix = ", ";
}
cout << " }\n";
}
return 0;
}
Output:
size of current_set = 5
size of power_set a = 32
size of my_char_set = 6
size of power_set b = 64
{ }
{ 0 }
{ 0, 1 }
{ 0, 1, 2 }
{ 0, 1, 2, 3 }
{ 0, 1, 2, 3, 4 }
{ 0, 1, 2, 4 }
{ 0, 1, 3 }
{ 0, 1, 3, 4 }
{ 0, 1, 4 }
{ 0, 2 }
{ 0, 2, 3 }
{ 0, 2, 3, 4 }
{ 0, 2, 4 }
{ 0, 3 }
{ 0, 3, 4 }
{ 0, 4 }
{ 1 }
{ 1, 2 }
{ 1, 2, 3 }
{ 1, 2, 3, 4 }
{ 1, 2, 4 }
{ 1, 3 }
{ 1, 3, 4 }
{ 1, 4 }
{ 2 }
{ 2, 3 }
{ 2, 3, 4 }
{ 2, 4 }
{ 3 }
{ 3, 4 }
{ 4 }
{ }
{ a }
{ a, b }
{ a, b, c }
{ a, b, c, d }
{ a, b, c, d, e }
{ a, b, c, d, e, f }
{ a, b, c, d, f }
{ a, b, c, e }
{ a, b, c, e, f }
{ a, b, c, f }
{ a, b, d }
{ a, b, d, e }
{ a, b, d, e, f }
{ a, b, d, f }
{ a, b, e }
{ a, b, e, f }
{ a, b, f }
{ a, c }
{ a, c, d }
{ a, c, d, e }
{ a, c, d, e, f }
{ a, c, d, f }
{ a, c, e }
{ a, c, e, f }
{ a, c, f }
{ a, d }
{ a, d, e }
{ a, d, e, f }
{ a, d, f }
{ a, e }
{ a, e, f }
{ a, f }
{ b }
{ b, c }
{ b, c, d }
{ b, c, d, e }
{ b, c, d, e, f }
{ b, c, d, f }
{ b, c, e }
{ b, c, e, f }
{ b, c, f }
{ b, d }
{ b, d, e }
{ b, d, e, f }
{ b, d, f }
{ b, e }
{ b, e, f }
{ b, f }
{ c }
{ c, d }
{ c, d, e }
{ c, d, e, f }
{ c, d, f }
{ c, e }
{ c, e, f }
{ c, f }
{ d }
{ d, e }
{ d, e, f }
{ d, f }
{ e }
{ e, f }
{ f }
Reiger
June 13th, 2011, 03:29 AM
I don't know Haskell at all, but this is very impressive. Is it O(2^n)?
EDIT: I was being stupid, I think part of my brain must've been switched off, because that code doesn't compute a powerset at all. Anyway this code does:
{
 Base case the empty set, returns a set consisting of a single empty set.
}
powerset [] = [[]]
{
 Recursive case:
 1 compute the powerset of the tail,
 2 concatenate it with a derivative set,
 3 where each item (subset of the tail) has the original head element appended to it.
}
powerset (x:xs)= let pset = powerset xs in pset ++ (map (x:) pset)
slavik
June 14th, 2011, 07:21 PM
basically, this is recursively generating a powerset of n1 and appends n to it.
Reiger
June 14th, 2011, 11:28 PM
basically, this is recursively generating a powerset of n1 and appends n to it.
Almost. If you literally did what you wrote you would generate the original set. ;)
BkkBonanza
June 15th, 2011, 12:57 AM
This reminds me of my days playing with Turbo Prolog back in the 80s. It's a distant fog now but I bet it would be very sucinct in Prolog (if I could just remember how to write that now).
I'm curious if there is a current day version of Prolog or if that has been left on the dustbin of computer history?
schauerlich
June 15th, 2011, 04:40 AM
I'm curious if there is a current day version of Prolog or if that has been left on the dustbin of computer history?
Check out swiprolog (http://www.swiprolog.org/). I used it last quarter for a computational linguistics course.
Leuchten
July 4th, 2011, 10:54 PM
My entry in Scala (still crummy, but getting better)
object Main {
def main(arg: Array[String]) {
val set = arg toList
val pset = powerSet(set)
println(pset ::: List(List[String]()))
}
def powerSet(set: List[String]): List[List[String]] = {
val part:String = if(set.size > 0) set(0) else null
if(part == null)
return List[List[String]]()
else {
val temp = powerSet(set  part)
val plus = addEach(part,temp)
return temp ::: plus
}
}
def addEach(part: String, set: List[List[String]]): List[List[String]] = {
if(set.size < 1)
return List(List(part))
else
return List((set(0) :+ part).toList) ::: addEach(part, setset(0))
}
}
zobayer1
July 4th, 2011, 11:23 PM
I think this one is simpler:
C++
void gen(int n, int *a, vector<int> *V) {
for(int i = 0; i < (1<<n); i++) {
V[i].clear();
for(int j = 0; j < n; j++) {
if(i & (1<<j)) {
V[i].push_back(a[j]);
}
}
}
}
Here, n is number of items in array a[], V is a vector array, which will contain the sets.
zobayer1
July 4th, 2011, 11:31 PM
Here is my complete implementation:
#include <vector>
#include <cstdio>
using namespace std;
const int MAX = 10;
void gen(int n, int *a, vector<int> *V) {
int i, j;
for(i = 0; i < (1<<n); i++) {
V[i].clear();
for(j = 0; j < n; j++) if(i & (1<<j)) V[i].push_back(a[j]);
}
}
int main() {
int i, j, n, a[MAX];
vector< int > V[1<<MAX];
while(scanf("%d", &n)==1) {
for(i = 0; i < n; i++) scanf("%d", a + i);
gen(n, a, V);
for(i = 0; i < (1<<n); i++) {
printf("Set %d:", i);
if(V[i].empty()) printf(" empty");
else for(j = 0; j < V[i].size(); j++) printf(" %d", V[i][j]);
printf("\n");
}
}
return 0;
}
Leuchten
July 5th, 2011, 03:31 AM
EDIT: I was being stupid, I think part of my brain must've been switched off, because that code doesn't compute a powerset at all. Anyway this code does:
{
 Base case the empty set, returns a set consisting of a single empty set.
}
powerset [] = [[]]
{
 Recursive case:
 1 compute the powerset of the tail,
 2 concatenate it with a derivative set,
 3 where each item (subset of the tail) has the original head element appended to it.
}
powerset (x:xs)= let pset = powerset xs in pset ++ (map (x:) pset)
After reviewing this code some more and learning more about the functional paradigm, I have shrunk my submission.
object Main {
def main(arg: Array[String]) {
val set = arg toList
val pset = powerSet(set)
println(pset)
}
def powerSet(set: List[String]): List[List[String]] = {
if(set.size < 1)
return List(set)
val pset = () => powerSet(set  set(0))
return pset() ++ pset().map((l: List[String]) => set(0) :: l)
}
}
fiddler616
April 26th, 2012, 06:36 PM
SML.
In retrospect, this is basically the same thing as the Haskell version.
fun powerset [] = [[]]
 powerset (x::xs) =
let
val pset = powerset(xs)
in
pset@(map (fn y => x::y) pset)
end;
LemursDontExist
April 28th, 2012, 03:47 AM
Since no one ever posted a Python version, and the elegant Haskell oneliner was already taken...
def powerset(l):
if len(l) == 0:
return [[]]
else:
x = l.pop()
pset = powerset(l)
return pset + [[x] + m for m in pset]
Powered by vBulletin® Version 4.2.2 Copyright © 2019 vBulletin Solutions, Inc. All rights reserved.