将一组整数分成两个大致相同太阳的子组

Question

我有一组整数，如 R data.frame:

set.seed(1)
df <- data.frame(id = paste0("id",1:100), length = as.integer(runif(100,10000,1000000)), stringsAsFactors = F)

所以每个元素都有一个id和一个length。

我想将 df 分成两个 data.frames，其总和 length.

大致相等

有没有想过 R 函数来实现它？

我认为 Hmisc 的 cut2 可以做到这一点，但我认为这不是它的预期用途：

library(Hmisc) # cut2
ll <- split(df, cut2(df$length, g=2))
> sum(ll[[1]]$length)
[1] 14702139
> sum(ll[[2]]$length)
[1] 37564671

Answer 1

这叫做Bin pack问题。 https://en.wikipedia.org/wiki/Bin_packing_problem 这个 link 可能会有帮助。

使用BBmisc::binPack函数，

df$bins <- binPack(df$length, sum(df$length)/2 + 1)
tapply(df$length, df$bins, sum)

结果类似

       1        2        3 
25019106 24994566    26346

既然你想要两组，

dummy$bins[dummy$bins == 3] <- 2 #because labeled as 2's sum is smaller

结果是

       1        2 
25019106 25020912

Split a group of integers into two subgroups of approximately the same suns