FLSSSmultiset: Multi-Subset Sum given error threshold

In FLSSS: Mining Rigs for Problems in the Subset Sum Family

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
  )

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.

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

# # 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)

FLSSS documentation built on May 17, 2022, 5:09 p.m.