partitions (version 1.11-1)

nextpart: Next partition

Description

Given a partition, return the “next” one; or determine whether it is the last one.

Usage

nextpart(part, check=TRUE)
islastpart(part)
 firstpart(n)
  nextdiffpart(part, check=TRUE)
islastdiffpart(part)
 firstdiffpart(n)
  nextrestrictedpart(part, check=TRUE)
islastrestrictedpart(part)
 firstrestrictedpart(n, m, include.zero=TRUE)
  nextblockpart(part, f, n=sum(part), include.fewer=FALSE, check=TRUE)
islastblockpart(part, f, n=NULL     , include.fewer=FALSE)
 firstblockpart(      f, n=NULL     , include.fewer=FALSE)
  nextcomposition(comp, restricted, include.zero=TRUE, check=TRUE)
islastcomposition(comp, restricted, include.zero=TRUE)
 firstcomposition(n,    m=NULL    , include.zero=TRUE)

Arguments

part, comp

A partition or composition

check

Boolean, with default TRUE meaning to carry out various safety checks; the next() functions use C calls which might crash the session with some inputs

f, n, include.fewer, m, include.zero

Other arguments as per the vectorized version

restricted

In function nextcomposition() and islastcomposition(), Boolean, with TRUE meaning to consider compositions of fixed length [eg, to iterate through the columns of compositions(6,3)], and FALSE meaning to consider compositions of any length [eg to iterate through the columns of compositions(6)]

Author

Robin K. S. Hankin

Details

These functions are intended to enumerate partitions one at a time, eliminating the need to store a huge matrix. This is useful for optimization over large domains and makes it possible to investigate larger partitions than is possible with the vectorized codes.

The idea is to use a first...() function to generate the first partition, then iterate using a next...() function, stopping when the islast...() function returns TRUE.

An example is given below, in which the “scrabble” problem is solved; note the small size of the sample space. More examples are given in the tests/aab.R file.

See Also

parts

Examples

# Do the optimization in scrabble vignette, one partition at a time:
# (but with a smaller letter bag)
scrabble <- c(a=9 , b=2 , c=2 , d=4 , e=12 , f=2 , g=3)

f <- function(a){prod(choose(scrabble,a)) / choose(sum(scrabble),7)}
bestsofar <- 0
a <- firstblockpart(scrabble, 7)
while(!islastpart(a)){
  jj <- f(a)
  if(jj > bestsofar){
    bestsofar <- jj
    bestpart <- a
  }
  a <- nextblockpart(a, scrabble) 
}