Tuesday, December 27, 2011

Find all the subsets of a given set

public class Subset {


public static List subset( List input ) {
double r = input.size();
int finalsize = (int)Math.pow( 2d, r );
List ret = new ArrayList( finalsize );
int one = 0x0001;
for ( int i = 1; i < finalsize; i++ ) {
int count = 0;
StringBuilder sb = new StringBuilder();
while ( count < finalsize ) {
int k = (i >> count) & one;
if ( k == 1 ) {
sb.append( input.get( count ) ).append(",");
}
count++;

}
ret.add( sb.toString() );
}
return ret;
}

public static void print( List in ) {
int i =1;
for ( String s : in ) {
System.out.println( "count_" + (i++) + " :" + s );
}
}

public static void main( String[] args ) {
List in = new ArrayList();
in.add( "a" );
in.add( "b" );
in.add( "c" );
in.add( "d" );
print ( subset( in) );
}
}

Find permutation of a String or character array

/**
* Finds premutation of an array of characters
* @author Nitesh
*
*/
public class Permutation {

public static void main( String[] args ) {
Permutation perm = new Permutation();
String s = "abcde";
char[] c = s.toCharArray();
char[][] ret = perm.permut( c , 0, c.length-1 );
perm.print( ret );
}


/**
* Begin = begin index
* end = end index
* input = char input
*
* @param input
* @param begin
* @param end
* @return
*/
public char[][] permut( char[] input, int begin, int end ) {

int len = end - begin + 1;
if (len == 1 ) {
char[][] ret = new char[1][];
ret[0] = input;
return ret;
}
if ( len == 2 ) {
char[][] ret = new char[2][];
ret[0] = input;
char[] a = copy( input );
a = swap( a , begin, end );
ret[1] = a;
return ret;
}
char pivot = input[begin];
int pivot_index = begin;
char[][] per = permut( input, begin+1, end );
return merge ( begin, per );

}

char[][] merge( int pivotIndex, char[][] input ) {
int rows = input.length;
int cols = input[0].length - pivotIndex;
int len = rows * cols;
char[][] ret = new char[len][];
for ( int i = 0; i < rows; i++ ) {
ret[i] = input[i];
}
int k = rows;
char[][] cir;
for ( int i = 0; i < rows; i++ ) {
cir = getCir( ret[i], pivotIndex );
for ( int j =0; j < cir.length; j++ ) {
ret[ k++ ] = cir[j];
}
}
return ret;

}

public void print( char[][] c ) {
for ( int i = 0; i< c.length; i ++ ) {
System.out.println( "count_" + (i+1) + "=" + new String( c[i] ) );
}
}

char[][] getCir( char[] c , int ele ) {
char[][] ret = new char[c.length -ele - 1][];

for ( int i = ele + 1, j=0; i < c.length; i++, j++ ) {
char[] cop = copy( c );
cop = swap( cop, ele, i );
ret[j] = cop;
}
return ret;
}

char[] copy( char[] input ) {
char[] ret = new char[ input.length ];
for ( int i = 0; i < input.length; i++ ) {
ret[i] = input[i];
}
return ret;
}

char[] swap( char[] a , int begin, int end ) {
char c = a[begin];
a[begin] = a [end];
a[end] = c;
return a;
}


}