getNextSet: Iteration through a list of all combinations of choose(n,k)

In pcalg: Methods for Graphical Models and Causal Inference

Iteration through a list of all combinations of choose(n,k)

Description

Given a combination of k elements out of the elements 1,\dots,n, the next set of size k in a specified sequence is computed.

Usage

getNextSet(n,k,set)

Arguments

n	Number of elements to choose from (integer)
k	Size of chosen set (integer)
set	Previous set in list (numeric vector)

Details

The initial set is 1:k. Last index varies quickest. Using the dynamic creation of sets reduces the memory demands dramatically for large sets. If complete lists of combination sets have to be produced and memory is no problem, the function combn from package combinat is an alternative.

Value

List with two elements:

nextSet	Next set in list (numeric vector)
wasLast	Logical indicating whether the end of the specified sequence is reached.

Author(s)

Markus Kalisch [e-mail] and Martin Maechler

See Also

This function is used in skeleton.

Examples

## start from first set (1,2) and get the next set of size 2 out of 1:5
## notice that res$wasLast is FALSE :
str(r <- getNextSet(5,2,c(1,2)))

## input is the last set; notice that res$wasLast now is TRUE:
str(r2 <- getNextSet(5,2,c(4,5)))

## Show all sets of size k out of 1:n :
## {if you really want this in practice, use something like combn() !}
n <- 5
k <- 3
currentSet <- 1:k
(res <- rbind(currentSet, deparse.level = 0))
repeat {
  newEl <- getNextSet(n,k,currentSet)
  if (newEl$wasLast)
     break
  ## otherwise continue:
  currentSet <- newEl$nextSet
  res <- rbind(res, currentSet, deparse.level = 0)
}
res
stopifnot(choose(n,k) == nrow(res)) ## must be identical

pcalg documentation built on Feb. 6, 2024, 3 p.m.