root/de.christofreichardt.scala/de.christofreichardt.scala.combinations/LazyBinomialCombinator

LazyBinomialCombinator

de.christofreichardt.scala.combinations.LazyBinomialCombinator

class LazyBinomialCombinator(val n: Int, val k: Int) extends Tracing

Produces all combinations of k unordered integers which can be chosen from among n integers (k <= n) by applying a lexicographic algorithm. The starting point is given by the lexicographic smallest word comprising k integers, e.g. (0,1,2) for k == 3. First, the algorithm evaluates the rightmost column in order to find new combinations, e.g. (0,1,3), (0,1,4) and (0,1,5) for n == 6. Now the algorithm has run out of options for the rightmost column and switches to (0,2,3) but not (0,2,1) since the latter would be identical to (0,1,2). In due course more to the left columns have to be considered, e.g. at (0,4,5). The algorithm finishes if the options have run out for all columns. For k == 3 and n == 6 that would be (3,4,5). The total number of solutions is given by the binomial coefficient "n choose k". For the given example that would be 20. To compute actual solution sizes , see WolframAlpha.

Value parameters

k: the number of integers which are to be chosen from the basic set
n: defines the basic set of integers

Attributes

Constructor: Creates a problem instance "n choose k".
Graph
Supertypes: trait Tracing

class Object

trait Matchable

class Any

Members list

Value members

Concrete methods

Given a solution the lexicographic next solution will be produced, if any. Most of the time only the value of the last (lowest-order or rightmost) column changes from one solution to the next solution. Sometimes more values are flipping. Depending on the position of the leftmost (discriminator) column with a changing value there are three cases to consider:

(1) the value at the position of the dicriminator column will be incremented by one related to the value of the previous solution at this position

(2) values to the left of the discriminator column will be copied from the previous solution

(3) values to the right of the discriminator column will be incremeted one by one based on the new value at the discriminator column

Value parameters

solution: the current solution

Attributes

Returns: some solution or none

Checks if there is a next solution for a given word.

Value parameters

solution: the current solution

Attributes

Returns: true if there is another solution

Produces a LazyList of all solutions. Solutions are computed only when they are needed. This is great if the solution space is very big.

Attributes

Returns: a LazyList comprising the solutions

Produces a LazyList of solutions given a particular solution.

Value parameters

solution: the starting point

Attributes

Returns: a LazyList comprising the solutions

Gives a textual representation of the problem instance.

Attributes

Returns: the textual presentation
Definition Classes: Any

Inherited methods

Returns the present tracer for this object.

Attributes

Returns: the current tracer, by default the NullTracer
Inherited from:: Tracing

Custom control structure for tracing of embraced code blocks.

Type parameters

T: the actual type of the embraced code block

Value parameters

block: the embraced code block
callee: the call site
method: denotes the method signature
resultType: denotes the return type

Attributes

Returns: returns whatever block returns
Inherited from:: Tracing

Concrete fields

The lexicographic smallest solution

Attributes

indicates the highest possible values for every column and therefore the terminating condition as well

Attributes

we need to look backwards into a solution when checking for the next solution

Attributes

In this article

Generated with