Class Combinations

java.lang.Object

topics.dynamic.Combinations

public class Combinations
extends Object

DYNAMIC PROGRAMMING PROBLEM: MATHEMATICAL COMBINATIONS n x k The recursive algorithm that calculates Combinations has exponential complexity and repeats calculations already performed. However, it is possible to design an algorithm with an quadratic execution time of O(n*k) based on the idea of the Pascal Triangle. This requires the creation of a two-dimensional table wherein storing the intermediate values we are obtaining

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
Combinations()

Method Summary

Modifier and Type	Method	Description
long	combinations(long[][] table, int n, int k)	Calculates the combinations of n elements taken k by k
long	combinationsDivideAndConquer(int n, int k)	Divide and conquer recursive version.
void	writeSolution(long[][] table, int n, int k)	Shows the result combinations of n elements taken k by k

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Combinations

public Combinations()

Method Details

combinations

public long combinations(long[][] table,
 int n,
 int k)

Calculates the combinations of n elements taken k by k

Parameters:

table - Table to calculate the combinations

n - n elements

k - Taken k by k

Returns:

Number of combinations

writeSolution

public void writeSolution(long[][] table,
 int n,
 int k)

Shows the result combinations of n elements taken k by k

Parameters:

table - Table to calculate the combinations

n - n elements

k - taken k by k

combinationsDivideAndConquer

public long combinationsDivideAndConquer(int n,
 int k)

Divide and conquer recursive version. It solves repeatedly the same subproblems. It has no polynomial complexity (so it is untreatable), and the worst case occurs with calls of the type combiDyV(n, n/2)

Parameters:

n - n elements

k - Taken k by k

Returns:

Number of combinations