CareerCup

For a set of size n, generate all binary numbers from 0 to 2^n-1

suppose the set is {'a','b','c'} (size =3)

Binary numbers from 0 to 7 are
000
001
010
011
100
101
110
111

For any binary number, say 101, look at the position of 1 and replace that from the set
ie for 101 = ac
for 011 = bc
111 = abc
000 = {}
010 = b

and so on..

using System;

namespace Testing
{
public class PowerSet
{
public static void GeneratePowerSet(int[] array, int index, string str)
{
if (index >= array.Length)
{
Console.WriteLine(str.Trim());
}
else
{
GeneratePowerSet(array, ++index, str);
if (index < array.Length)
{
str = str + " " + array[index];
GeneratePowerSet(array, index, str);
}
}
}
}

public sealed class MAIN
{
public static void Main()
{
int[] array = new int[] { 1,2,3,4 };
PowerSet.GeneratePowerSet(array, -1, string.Empty);
Console.ReadLine();
}
}
}

@champakla, would you plz explain the idea a little?
I'm always poor too catch up such code where there is tail-recursion (i.e. recursive function calls in the tail part of initial recursion call) :(

Thanks.

the idea goes like this:

a subset in a powerset can contain an element or it can not. so for every element, we have two choices.

Suppose the first element is taken, or not taken, this would form 2 subsets.
similarly, second element can be taken or not taken, and these 2 possibilities can be hooked to the previous two, generating 4 solutions...
so on and so forth. Now, as soon as we have accounted for presence and absence of all the elements one by one, we can print their respective subsets. the subsets so formed are 2^n for n elements. that's why they are called powersets, as they are exponential.
for more details, contact me on priyodit[AT]gmail [DOT] com as i don't visit here often.

idea is to generate all numbers from 0 to 2^length_of_set... java code goes below...

public class PowerSet {
	public static void main(String[] args) {
		int[] a = {1, 2, 3, 10, 11};
		printPowerSet(a);
	}
	
	public static void printPowerSet(int[] a){
		int number = (int)Math.pow(2, a.length);
		
		System.out.println("1: {}");
		for(int i=1; i<number; i++){
			System.out.print((i+1) + " : {");
			for(int j=0; j< a.length; j++){
				if(((i >> j) & 1) == 1){
					System.out.print(a[j] + "  ");
				}
			}
			System.out.println("}" );
		}
	}
}

Same Idea what binary gave us

public class PowerSet {
	public static void main(String args[]){
		char[] set = {'a','b','c'};
		int max = ~(~0<<(set.length));
		for(int i=0;i<=max;i++){
			int k=set.length;
			System.out.print("{");
			for(int j=0;j<k;j++){
				if((i&(1<<j))>0){
					System.out.print(set[j]);
				}
			}
			System.out.print("}");
		}
	}
}

<pre lang="java" line="1" title="CodeMonkey82374" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class PowerSet
{
public static void main(String[] args) {

char[] set = {'a','b','c'};

int max = 1 << set.length;

for(int i=1; i<=max; i++){

int k = set.length;

System.out.print("{");

for(int j=0; j<k; j++){

if( (i & (1<<j)) != 0){
System.out.print(set[j]);
}
}

System.out.print("}");

}
}
}

</pre><pre title="CodeMonkey82374" input="yes">

</pre>

Can we not also do this by using recursion & dynamic programming ?

time complexity of the above algorithm is
O (n * 2^n)

def power_set(S):
  if not S:
    return []
  T = power_set(S[1:])
  return T + [[S[0]] + t for t in T]

print power_set(S)