FLSSS (version 7.5)

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,
  useFloat = FALSE
  )

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().

useFloat

See useFloat in FLSSS().

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]].

Examples

# NOT RUN {
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)
# }