Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Here's a Python translation, which prints square brackets instead of squigglies, but otherwise similar logic:
def power_set(big_lst):
n = len(big_lst)
power_set = []
for i in range(1 << n):
lst = []
for j in range(n):
if i&(1<<j):
lst.append(big_lst[j])
power_set.append(lst)
return power_set
lst = [10, 20, 30]
print power_set(lst)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void PrintVariant(vector<int>& v, vector<bool>& vb, int idx)
{
if (idx<0) {
cout<< "{";
for (int i=0; i<v.size(); i++)
if (vb[i]) cout << v[i] << " ";
cout<< "}"<<endl;
return;
}
PrintVariant(v, vb, idx-1);
vb[idx] = false;
PrintVariant(v, vb, idx-1);
vb[idx] = true;
}
void PrintPowerSet(vector<int>& v)
{
vector<bool> vb(v.size(), true);
PrintVariant(v, vb, v.size()-1);
}
int main(int argc, char** argv)
{
int a[] = {1, 2, 3};
vector<int> v (a, a+(sizeof(a)/sizeof(int)));
cout << "Input is : ";
for (int i=0; i<v.size(); i++) cout << v[i] << " ";
cout << endl;
PrintPowerSet(v);
}
Python Power Set.
This basically does binary counting to mutate a list of True/False values that determine which elements get included in the next subset.
def power_set(s):
lst = list(s)
bools = [False] * len(lst)
while True:
yield set([lst[i] for i, b in enumerate(bools) if b])
i = 0
while i < len(lst):
if not bools[i]: break
i += 1
if i >= len(lst):
break
bools[i] = True
for j in range(i):
bools[j] = False
def test():
s = set([10, 20, 30])
for sublist in power_set(s):
print sublist
test()
Also easy to do recursively:
def power_set(lst):
if not lst:
return [[]]
else:
head = lst.pop()
ps = power_set(lst)
return ps + [[head] + s for s in ps]
if using the standard library (Python) is allowed:
from itertools import combinations, chain
print [ps for ps in chain(*[[list(z) for z in combinations(lst, i) ] for i in range(len(lst))])]
Or, if the {..} format is absolutely required, -
print ", ".join(["{%s}"%repr(l)[1:-1] for l in chain(*[[list(z) for z in combinations(lst, i) ] for i in range(len(lst)+1)])])
import java.util.*;
public class Powerset {
public static void main(String[] args) {
int ar[]=new int[10];
int n;
Scanner sc=new Scanner(System.in);
System.out.println("enrter the length of the set");
n=sc.nextInt();
System.out.println("enter the set elements");
for(int a=0;a<n;a++)
ar[a]=sc.nextInt();
System.out.print("{"+0+"} ");
int nn=n;
//int x=0;
for(int i=0;i<n-1;i++)
{
int j=0;
for(int p=0;p<nn;p++)
{
System.out.print("{");
int y=0;
for(;y<i;y++)
{
System.out.print(ar[y]+",");
}
j=y+p;
System.out.print(ar[j]);
System.out.print("} ");
}
nn--;
}
System.out.print("{");
for(int l=0;l<n;l++)
System.out.print(ar[l]+",");
System.out.print("}");
}
}
sample o/p:enrter the length of the set
5
enter the set elements
1
2
3
4
5
{0} {1} {2} {3} {4} {5} {1,2} {1,3} {1,4} {1,5} {1,2,3} {1,2,4} {1,2,5} {1,2,3,4} {1,2,3,5} {1,2,3,4,5,}
This could be done using combinations, here is JS code (run it in nodejs):
(function powerset(array) {
function _powerset(array, result, tmp, length, startIndex) {
for (var i = startIndex; i < length; ++i) {
tmp.push(array[i]);
result.push('{' + tmp.join(',') + '}');
if (i < length - 1) {
_powerset(array, result, tmp, length, i + 1);
}
--tmp.length;
}
}
var result = [];
var tmp = [];
_powerset(array, result, tmp, array.length, 0);
console.log(result.join(' '));
}([1, 2, 3]));
Output:
{1} {1,2} {1,2,3} {1,3} {2} {2,3} {3}
I think it may work but it wont produce the o/p in given order.........
#include<conio.h>
#include<iostream.h>
int n,a[10],b[10];
void display(int k)
{
cout<<"{";
for(int i=0;i<k;i++)
cout<<b[i]<<",";
cout<<"\b},";
}
void func(int i,int j,int k,int m)
{
b[m]=a[j];
display(k);
for(;j<n-1;j++)
{
func(i,j+1,k+1,m+1);
}
}
void main()
{
int i,j,k;
clrscr();
cout<<"Number of trems";
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
if(a[i]>a[j])
{
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
for(i=0;i<n;i++)
{
func(i,i,1,0);
}
getch();
}
My solution in Javascript. The idea is to iteratively fetch an object and combine it with all the sets that are already in the superset being created:
function powerset(array) {
var i, j, len,
powerset = [[]];
for (i=0; i<array.length; i++) {
for (j=0, len=powerset.length; j<len; j++) {
powerset.push(powerset[j].concat(array[i]));
}
}
return powerset;
}
#include <stdio.h>
typedef int bool;
#define true 1
#define false 0
void genpowset(bool *check, int i, int N, int *arr)
{
int j;
if (i == N)
{
printf("{");
for (j=0;j<N;j++)
{
if (check[j])
printf("%d",arr[j]);
}
printf("}\n");
}
if (i < (N))
{
check[i] = true;
genpowset(check,i+1,N,arr);
check[i] = false;
genpowset(check,i+1,N,arr);
}
}
main ()
{
int N, i;
scanf("%d",&N);
int arr[N];
bool checkArr[N];
for(i=0;i<N;i++)
scanf("%d",&arr[i]);
genpowset(checkArr,0,N,arr);
}
Recursive solution in C#.
public static class Solution
{
public static void Do(int[] data)
{
DoRec(data, new List<int>(), 0);
}
private static void DoRec(int[] data, List<int> subset, int i)
{
PrintSet(subset);
for (int j = i; j < data.Length; ++j)
{
subset.Add(data[j]);
DoRec(data, subset, j + 1);
subset.RemoveAt(subset.Count - 1);
}
}
private static void PrintSet(List<int> subset)
{
StringBuilder sb = new StringBuilder("{");
foreach (int x in subset)
{
sb.Append(x);
sb.Append(",");
}
if (sb.Length > 1)
sb.Remove(sb.Length - 1, 1);
sb.Append("}");
System.Console.WriteLine(sb.ToString());
}
}
>>> for i in range(1,8):
new=[]
while (i >1):
new.append(i%2)
i=int(i/2)
if i ==1:
new.append(i)
if len(new)==1:
new.append(0)
new.append(0)
if len(new)==2:
new.append(0)
new.reverse()
#print new
new1=[]
for m in range(len(new)):
if new[m]<>0:
new1.append(list[m])
print new1
['3']
['2']
['2', '3']
['1']
['1', '3']
['1', '2']
['1', '2', '3']
Here is the simple solution in PHP:
<?php
$set = array(1,2,3,4,5);
function displaySets($set, $level, $maxLevel, $fromIndex, $setString)
{
if ($level == 0) $setString = "{";
if ($level == $maxLevel)
{
echo $setString . '}';
}
else
{
for($i = $fromIndex; $i < count($set); $i++)
{
$setString2 = $setString . $set[$i];
if ($level+1 < $maxLevel) $setString2 .= ',';
displaySets($set, $level+1, $maxLevel, $i+1, $setString2);
}
}
}
function findPowerSets($set)
{
for($i = 0; $i <= count($set); $i++)
displaySets($set, 0, $i, 0, "");
}
findPowerSets($set);
This code will be ok.
void Trace(std::vector<std::vector<int> > & rs, std::vector<int> & path, std::vector<int> & v, int k) {
if (k == v.size()) {
rs.push_back(path);
} else {
Trace(rs, path, v, k + 1);
path.push_back(v[k]);
Trace(rs, path, v, k + 1);
path.pop_back();
}
}
std::vector<std::vector<int> > PSet(std::vector<int> & v) {
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, path, v, 0);
return rs;
}
You can use bit operators, here is how I would do it:
for( int i =0 ; i < 1<<n; i++) { // iterate through all possible combinations cout<<"{"; for(int j = 0 ; j<n; j++) { if( (i&(1<<j)) > 0 ) { cout<<a[j]<<","; } } cout<<"}, "; }I am generating all the possible bit values till n 0, 1, 00, 01, 10, 11 and so on. Then i run another loop and pick only those number whose index bits are set.
- HauntedGhost March 06, 2013