Combinatorics

next permutation

/**
 * Next Permutation of the given input array
 * @param in the array
 * @return whether there is a next permutation or not
 */
public boolean nextPermutation(int[] in){
	for(int i=in.length-2;i>=0;i--)if(in[i]<in[i+1]){
		for(int j=in.length-1;j>i;j--)if(in[j]>in[i]){
			int t=in[i];
			in[i]=in[j];
			in[j]=t;
			break;
		}
		for(int j=i+1;j<in.length-(j-i);j++){
			int t=in[j];
			in[j]=in[in.length-(j-i)];
			in[in.length-(j-i)]=t;
		}
		return true;
	}
	return false;
}

number of permutations

This is an awesome algorithm....first you create a DP array of the number of ways you can insert n "new" things into a list of m "old" things, then you simulate inserting all of the counts of unique symbols, using the values calculated by the DP

/**
 * calculate the number of permutations of a given list
 * @param in the count of each unique element in the list
 * @return number of permutations of the list specified by the input
 */
public long numPermutation(int[] in){
	int total=0;
	for(int i:in)total+=i;
	long[][] dp=new long[total+1][total+1];
	Arrays.fill(dp[0], 1);
	for(int i=1;i<=total;i++)for(int j=0;j<=total;j++)for(int k=0;k<=j;k++)dp[i][j]+=dp[i-1][j-k];
	long ans=1;
	total=0;
	for(int i:in){
		ans*=dp[total][i];
		total+=i;
	}
	return ans;
}

next combination

note...the value of each entry of "in" is the set that item belongs to for this combination..also an arbitrary-base counter

/**
 * Next Combination of the givin input array (left to right), set max to 2 to iterate over all combinations
 * @param in the array
 * @param max the maximum value you are permuting to
 * @return whether there is a next combination or not
 */
public boolean nextCombination(int[] in,int max){
	for(int i=0;i<in.length;i++){
		if(in[i]<max){
			in[i]++;
			return true;
		}
		in[i]=0;
	}
	return false;
}

number of combinations

If you try to do this with factorials, or without DP...you'll probably fail

/**
 * calculates n-choose-r or ans[n][r]
 * @param max maximum value you need for n or r
 * @param mod the mod value, if not needed, use 1
 * @return the values of n choose r for all n,r <max
 */
public long[][]  numCombinations(int max, int mod){
	long[][] ans=new long[max][max];
	for(int i=0;i<max;i++)ans[i][0]=1;
	for(int i=1;i<max;i++)for(int j=1;j<max;j++)ans[i][j]=(ans[i-1][j]+ans[i-1][j-1])%mod;
	return ans;
}

If you only have to calculate a single one

This is cool and works! why? because we divide by 2 on the second loop, by which time we've multiplied by n and n-1....one of which must be a power of two. The same logic applies for 3 and every other value until n/2, which doesn't matter since we took the smaller of r and n-r.

public long nCr(int n, int r, int mod){
    r=Math.min(r,n-r);
    long ans=1;
    for(int i=0;i<r;i++){
        ans*=(n-i);
        ans%=mod;
        ans/=(1+i);
    }
    return ans;
}