FLSSS (version 9.2.0)

FLSSSmultiset: Multi-Subset Sum given error threshold

Description

Find a subet of a given size for each of multiple supersets such that all the subsets sum in a given range.

Usage

FLSSSmultiset(
  len,
  buckets,
  target,
  ME,
  solutionNeed = 1L,
  tlimit = 60,
  useBiSrchInFB = FALSE,
  NfractionDigits = Inf
  )

Value

A list of solutions. Each solution is a list of index vectors. Assume X is a solution. X[[i]] indexes the subset of superset buckets[[i]].

Arguments

len

A positive integer vector as the subset sizes for the supersets.

buckets

A list of the supersets. buckets[[i]] is an unsorted numeric vector of size len[i].

target

See target in FLSSS().

ME

See ME in FLSSS().

solutionNeed

See solutionNeed in FLSSS().

tlimit

See tlimit in FLSSS().

useBiSrchInFB

See useBiSrchInFB in FLSSS().

NfractionDigits

An integer, the maximum number of fractional digits of all elements in v. Internally, v, target and ME are multiplied by 10 ^ NfractionDigits, and then converted as integer values before mining. The default Inf prevents such conversion.

Examples

# # rm(list = ls()); gc()
Nsupersets = 30L
supersetSizes = sample(5L : 20L, Nsupersets, replace = TRUE)
subsetSizes = sapply(supersetSizes, function(x) sample(1L : x, 1))


# Create supersets at random:
supersets = lapply(supersetSizes, function(n)
{
  1000 * (rnorm(n) ^ 3 + 2 * runif(n) ^ 2 + 3 * rgamma(n, 5, 1) + 4)
})
str(supersets) # see the structure


# Give a subset sum
solution = mapply(function(n, l) sample(1L : n, l), supersetSizes, subsetSizes)
str(solution) # See structure
subsetsSum = sum(mapply(function(x, s) sum(x[s]), supersets, solution, SIMPLIFY = TRUE))
subsetsSumError = abs(subsetsSum) * 1e-7 # relative error within 0.00001%
rm(solution)


# Mine subsets:
rst = FLSSS::FLSSSmultiset(len = subsetSizes, buckets = supersets, target = subsetsSum,
                           ME = subsetsSumError, solutionNeed = 3, tlimit = 4)
cat("Number of solutions =", length(rst), "\n")


# Verify:
ver = all(unlist(lapply(rst, function(sol)
{
  S = sum(unlist(mapply(function(x, y) sum(x[y]), supersets, sol)))
  abs(S - subsetsSum) <= subsetsSumError
})))
cat("All subsets are qualified:", ver)