COMBINATIONS AND PERMUTATIONS
Integer Partitioning
import java.lang.Math;
class partition {
// Integer partitioning function. Creates all the possible partitions of <num>
// such that the sum of the digits are <= num.
public static void part(int num)
{
for (int a = 0; a <= num; a++)
for (int b = 0; b <= num - a; b++)
for (int c = 0; c <= num - b - a; c++)
for (int d = 0; d <= num - c - b - a; d++)
System.out.println( a + "," + b + "," + c + "," + d );
}
// Produces a 4-column counter that functions much like a speedometer.
// each column counts from 0 to num.
public static void counter_4(int num, int array[][])
{
int row = 0;
for (int a = 0; a <= num; a++)
for (int b = 0; b <= num; b++)
for (int c = 0; c <= num; c++ )
for (int d = 0; d <= num; d++) {
array[row][0] = a;
array[row][1] = b;
array[row][2] = c;
array[row][3] = d;
System.out.println( a + "," + b + "," + c + "," + d );
row++;
}
}
public static void main(String[] arg){
int digitMax = 4; // digit max for each column
int count = (int) Math.pow(digitMax+1,4);
int array[][] = new int[count][4];
counter_4( digitMax, array );
}
}
PARTITION FUNCTION
Counts the ways num can be written as a sum of numbers including itself.
public int countCombinations(int num, int min)
{
int temp = 1;
if (num <= 1)
return 1;
for (int i = 1; i <= Math.floor(num/2); i++)
{
if (i >= min)
temp += countCombinations(num - i, i);
}
return temp;
}
Pairs and Triples
Generate all pairs of values from N to M, inclusive
void pairs(int N, int M )
{
int i, j;
for(i = N; i < M; i++)
for(j = i+1; j <= M; j++)
printf("[%d,%d] ", i, j);
}
Generate all triples from N to M, inclusive
void triples(int N, int M )
{
int i, j, k;
for(i = N; i < M; i++)
for(j = i+1; j <= M; j++)
for(k = j+1; k <= M; k++)
printf("[%d,%d,%d] ", i, j, k);
}
Combinations
Generate all combinations of elements from an array of objects.
public class Combinations
{
/* Generates all combinations of elements from
* an array of objects, including an empty element in
* the first list position.
*/
public static List<Object> combination(Object [ ] data)
{
List<Object> arr = new ArrayList<Object>();
if(data.length == 0)
arr.add("");
else
{
Object [ ] sub = Arrays.copyOfRange(data, 0, data.length - 1);
Object last = data[data.length - 1];
List<Object> result = combination(sub);
for(Object obj: result) {
arr.add(obj);
arr.add(obj+""+last);
}
}
return arr;
}
public static void main(String[] args) {
Object [ ] arr = {"a", "b", "c"};
System.out.println(combination(arr));
}
}
Binomial Coefficent compute N choose M
(C++ version)
#define MAXN 100 /* largest n or m */
long binomial_coefficient(int n, int m)
// compute n, choose m
{
int i,j; /* counters */
long bc[MAXN][MAXN]; /* table of binomial coefficient values */
for (i=0; i<=n; i++) bc[i][0] = 1;
for (j=0; j<=n; j++) bc[j][j] = 1;
for (i=1; i<=n; i++)
for (j=1; j<i; j++)
bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
return( bc[n][m] );
}
General Permutation Function
Generates all permutations on a set of integers 1..N. Initial call should be visit(0). The global variable <level> must be set to -1. The size of the array (in this example) is named numJobs and permutations are stored in the array named <Value>.
void visit(int k) {
int i;
level++;
Value[k] = level;
if (level == numJobs)
usePermutation();
else
{
for ( i = 0; i < numJobs; i++ ) {
if (Value[i] == 0)
visit(i);
}
}
level--;
Value[k] = 0;
}
Alternative- Building a permutation String
Produces all possible permutations of String s in lexicographic order.
class Permutations
{
private ArrayList<String> perms = new ArrayList<String>();
public void permute(String s) {
permute("", s);
}
public void permute(String p, String s)
{
int n = s.length();
if (n==0) {
perms.add(p);
}
else
for (int i=0; i<n; i++)
permute(p+s.charAt(i), s.substring(0,i) + s.substring(i+1, n));
}
public ArrayList<String> getPermutations()
{
return perms;
}
}
Generate All Subsets
(C++ version) Uses binary counter to generate all combinations of 1 and 0, which is an efficient way to identify all subsets.
typedef unsigned char uchar;
// this evaluation function can be customized for the current problem.
bool evaluate( uchar bin[], int length ){
return false;
}
void nextSubset( uchar bin[], unsigned numBits )
{
for(unsigned i = numBits-1; i > 0; i--)
{
if( bin[i] == 1 )
bin[i] = 0;
else {
bin[i]++;
return;
}
}
}
// debugging only
void showSubset( uchar bin[], int numBits )
{
for(int i = 0; i < numBits; i++)
cout < int(bin[i]) < " ";
cout < endl;
}
void GenAllSubsets( unsigned length )
// generates all subsets of a given length (1-31). Pass it a
// the subset length and a boolean evaluation function.
// Anything larger than 24 has excessive run time.
{
uchar bits[32];
for(unsigned i = 0; i < length; i++)
bits[i] = 0;
// calculate the number of possible subsets
// pow(double,double) needs cast to avoid ambiguous arguments
unsigned N = (unsigned) pow(2, double(length))-1;
for(unsigned i = 0; i < N; i++)
{
nextSubset( bits, length );
//showSubset( bits, length );
if( evaluate(bits, length) ) {
return;
}
}
}
SAMPLE PROBLEM SOLUTIONS
Ancient Calculator problem
import java.util.*;
public class AncientCalculator
{
public static HashMap<Integer,ArrayList<Integer> nums =
new HashMap<Integer,ArrayList<Integer>();
public static void main(String[] args)
{
computeNums();
Scanner in = new Scanner(System.in);
while(true)
{
int x = in.nextInt();
if(x == 0)
break;
int y = in.nextInt();
int z = in.nextInt();
int count=0;
for(int xx : nums.get(x))
{
for(int yy : nums.get(y))
{
if(getMillis(xx+yy)==z)
count++;
if(getMillis(xx-yy)==z)
count++;
if(yy!=0 & getMillis(xx/yy)==z)
count++;
if(getMillis(xx*yy)==z)
count++;
}
}
System.out.println(count+" solutions for "+x+" "+y+" "+z);
}
}
public static void computeNums()
{
for(int i=0;i<1000;i++)
{
int num=i;
int total=0;
if (i==0)
total = getMilli(0);
while(num>0)
{
total += getMilli(num%10);
num=num/10;
}
if(!nums.containsKey(total))
nums.put(total, new ArrayList<Integer>());
nums.get(total).add(i);
if(i!=0 & !nums.containsKey(total+5))
nums.put(total+5, new ArrayList<Integer>());
if (i!=0)
nums.get(total+5).add(-i);
}
}
public static int getMillis(int num)
{
if (num==0)
return getMilli(0);
if (num<-999 || num >999)
return 0;
int total = 0;
boolean neg = num < 0;
num = Math.abs(num);
while(num>0)
{
total += getMilli(num%10);
num=num/10;
}
if (neg)
total+=5;
return total;
}
public static int getMilli(int num){
switch (num)
{
case 0:
return 30;
case 1:
return 10;
case 2:
return 25;
case 3:
return 25;
case 4:
return 20;
case 5:
return 25;
case 6:
return 30;
case 7:
return 15;
case 8:
return 35;
default:
return 30;
}
}
}
ProbBot problem
public class PropBot
{
static final double pi = Math.PI;
static final double[] angle = {0, 7*pi/4, 3*pi/2, 5*pi/4,
pi, 3*pi/4, pi/2, pi/4};
static ArrayList<Move> moves;
static double best;
static double x, y;
static int n;
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int cases = in.nextInt();
for (int i = 0; i < cases; i++)
{
best = Double.POSITIVE_INFINITY;
moves = new ArrayList<Move>();
n = in.nextInt();
x = in.nextDouble();
y = in.nextDouble();
part(n);
findDists();
System.out.printf("%.6f\n", best);
}
}
public static void findDists()
{
for (Move m : moves)
{
tryMoves(m);
}
}
public static void tryMoves(Move m)
{
for (int a=0; a<7; a+=4)
for (int b=1; b<=7; b+=4)
for (int c=2; c<=7; c+=4)
for (int d=3; d<=7; d+=4)
{
int[] move = new int[8];
move[a] = m.a;
move[b] = m.b;
move[c] = m.c;
move[d] = m.d;
if (validMove(move))
eval(move);
}
}
public static boolean validMove(int[] m)
{
int total = 0, turns = -1;
for (int i=0; i<m.length; i++)
{
total += m[i];
if (m[i] > 0)
turns = i;
}
return (turns == -1) || (total + turns <= n);
}
public static void eval(int[] m)
{
double fx = 0, fy = 0;
for (int i=0; i<m.length; i++)
{
fx += m[i] * 10 * Math.cos(angle[i]);
fy += m[i] * 10 * Math.sin(angle[i]);
}
double d = dist(fx,fy);
if (d < best)
best = d;
}
public static double dist(double x1, double y1)
{
return Math.sqrt(Math.pow(x1 - x, 2) + Math.pow(y1 - y, 2));
}
public static void part(int num) //partition
{
for (int a = 0; a<=num; a++)
for (int b = 0; b<=num - a; b++)
for (int c = 0; c<=num - b - a; c++)
for (int d = 0; d<=num - c - b - a; d++)
moves.add(new Move(a,b,c,d));
}
}
class Move
{
public int a, b, c, d;
public Move(int e, int f, int g, int h)
{
a = e;
b = f;
c = g;
d = h;
}
public String toString()
{
return a + " " + b + " " + c + " " + d;
}
}
1