logo标签列表

将向量分割成平衡的列表（平衡列表元素的总和）

ralgorithmvectorsplit
7

我很难找到一个高效的解决方案来解决以下问题。由于我不确定是否让这个问题变得更加复杂，所以问题描述非常详细。

给定一个命名向量

t <- c(2, 0, 0, 30, 0, 0, 10, 2000, 0, 20, 0, 40, 60, 10)
names(t) <- c(1, 0, 0, 2, 0, 0, 3, 4, 0, 5, 0, 6, 7, 8)

我希望将t拆分成4个元素的列表，基于结果列表元素的总和进行平衡，同时保持元素的顺序，并仅在非零元素上进行拆分。期望的结果如下：
L[1] <- c(2, 0, 0, 30, 0, 0, 10) # sum = 42
L[2] <- c(2000, 0)               # sum = 2000
L[3] <- c(20, 0, 40)             # sum = 60
L[4] <- c(60, 10)                # sum = 70

我使用的错误函数是最小化sd(rowSums(L))或sd(sapply(L, sum))。
尝试使用以下类似方法来拆分向量并不完全有效。
split(t, cut(cumsum(t), 4))

# $`(-0.17,544]`
 # 1  0  0  2  0  0  3 
 # 2  0  0 30  0  0 10 

# $`(544,1.09e+03]`
# named numeric(0)

# $`(1.09e+03,1.63e+03]`
# named numeric(0)

# $`(1.63e+03,2.17e+03]`
   # 4    0    5    0    6    7    8 
# 2000    0   20    0   40   60   10

我编写了一个函数来按照我想要的方式拆分列表（参见上面的错误函数）。
break_at <- function(val, nchunks) {
    nchunks <- nchunks - 1
    nonzero <- val[val != 0]
    all_groupings <- as.matrix(gtools::permutations(n = 2, r = length(nonzero), v = c(1, 0), repeats.allowed = TRUE))
    all_groupings <- all_groupings[rowSums(all_groupings) == nchunks, ]
    which_grouping <- which.min(
    sapply(
        1:nrow(all_groupings), 
        function(i) { 
            sd(
                sapply(
                    split(
                        nonzero, 
                        cumsum(all_groupings[i,])
                    ), 
                    sum
                )
            )
        }
    )
    )
    mark_breaks <- rep(0, length(val))
    mark_breaks[names(val) %in% which(all_groupings[which_grouping,]==1)] <- 1
    return(mark_breaks)
}

您可以看到，结果要好得多。
break_at(t, 4)
# 0 0 0 0 0 0 0 1 0 1 0 0 1 0

split(t, cumsum(break_at(t, 4)))

# $`0`
 # 1  0  0  2  0  0  3 
 # 2  0  0 30  0  0 10 

# $`1`
   # 4    0 
# 2000    0 

# $`2`
 # 5  0  6 
# 20  0 40 

# $`3`
 # 7  8 
# 60 10

它的工作原理是使用gtools::permutations(n = 2, r = length(nonzero), v = c(1, 0), repeats.allowed = TRUE)来查看所有可能的分割。看看上面的例子如何处理r = 3

     # [,1] [,2] [,3]
# [1,]    0    0    0
# [2,]    0    0    1
# [3,]    0    1    0
# [4,]    0    1    1
# [5,]    1    0    0
# [6,]    1    0    1
# [7,]    1    1    0
# [8,]    1    1    1

我需要对all_groupings[rowSums(all_groupings) == nchunks, ]进行筛选。这仅考虑能够生成nchunks的分割可能性。

我的问题是，由于涉及到大量的排列组合，这在我的实际数据中表现非常糟糕。

hard <- structure(c(2, 0, 1, 2, 0, 1, 1, 1, 5, 0, 0, 0, 0, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 0, 0, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1,
1, 1, 2, 0, 2, 0, 1, 4, 0, 0, 0, 1, 3, 0, 0, 4, 0, 0, 0, 2, 0,
1, 1, 1, 3, 0, 0, 1, 1, 1, 1, 2, 0, 1, 2, 0, 1, 1, 2, 0, 1, 6,
0, 0, 0, 0, 0, 1, 1, 1, 3, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0,
1, 1, 2, 0, 1, 2, 0, 1, 1, 4, 0, 0, 0, 1, 1, 3, 0, 0, 1, 2, 0,
1, 1, 2, 0, 1, 3, 0, 0, 1, 3, 0, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 0, 3,
0, 0, 1, 1, 2, 0, 1, 2, 0, 1, 1, 1, 2, 0, 2, 0, 1, 3, 0, 0, 1,
1, 1, 1, 1, 2, 0, 1, 1, 1, 2, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1, 2,
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
0, 1, 1, 1, 1, 1, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
1, 2, 0, 1, 1, 1, 2, 0, 1, 1, 1, 2, 0, 8, 0, 0, 0, 0, 0, 0, 0,
1, 2, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 2, 0, 1, 1, 1,
3, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1,
1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 3, 0,
0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 1,
1, 1, 1, 2, 0, 1, 1, 1, 1, 5, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 2, 0, 1, 1, 1, 1, 2, 0, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 2, 0, 1, 1, 2, 0, 1, 2, 0, 1, 8, 0, 0, 0, 0, 0, 0, 0, 2,
0, 1, 9, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 0, 0, 0, 1, 1, 1,
1, 6, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 1, 3, 0, 0, 1, 1, 1, 3,
0, 0, 7, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1), .Names = c("1", "0",
"2", "3", "0", "4", "5", "6", "7", "0", "0", "0", "0", "8", "9",
"10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20",
"21", "22", "23", "24", "0", "0", "25", "26", "27", "28", "29",
"30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "0",
"40", "41", "42", "43", "0", "44", "45", "46", "47", "48", "49",
"50", "51", "52", "0", "53", "0", "54", "55", "0", "0", "0",
"56", "57", "0", "0", "58", "0", "0", "0", "59", "0", "60", "61",
"62", "63", "0", "0", "64", "65", "66", "67", "68", "0", "69",
"70", "0", "71", "72", "73", "0", "74", "75", "0", "0", "0",
"0", "0", "76", "77", "78", "79", "0", "0", "80", "81", "82",
"83", "84", "85", "86", "87", "88", "0", "89", "90", "91", "0",
"92", "93", "0", "94", "95", "96", "0", "0", "0", "97", "98",
"99", "0", "0", "100", "101", "0", "102", "103", "104", "0",
"105", "106", "0", "0", "107", "108", "0", "0", "109", "110",
"111", "112", "0", "113", "114", "115", "116", "117", "118",
"119", "120", "121", "122", "123", "124", "125", "126", "127",
"128", "129", "130", "131", "0", "132", "133", "134", "0", "135",
"0", "0", "136", "137", "138", "0", "139", "140", "0", "141",
"142", "143", "144", "0", "145", "0", "146", "147", "0", "0",
"148", "149", "150", "151", "152", "153", "0", "154", "155",
"156", "157", "0", "158", "159", "0", "160", "161", "162", "163",
"164", "165", "166", "0", "167", "168", "169", "170", "171",
"172", "173", "174", "175", "176", "177", "178", "179", "180",
"181", "182", "183", "184", "185", "186", "0", "187", "188",
"189", "190", "191", "192", "0", "0", "0", "0", "0", "0", "0",
"0", "0", "0", "193", "194", "195", "196", "197", "0", "198",
"199", "200", "201", "0", "202", "203", "204", "205", "0", "206",
"0", "0", "0", "0", "0", "0", "0", "207", "208", "0", "209",
"210", "211", "212", "213", "214", "215", "0", "216", "217",
"218", "219", "220", "221", "0", "222", "223", "224", "225",
"0", "0", "226", "227", "228", "229", "230", "231", "232", "233",
"234", "235", "236", "237", "238", "239", "240", "0", "241",
"242", "243", "244", "245", "246", "247", "248", "0", "249",
"250", "251", "252", "253", "254", "0", "255", "256", "257",
"258", "259", "260", "0", "0", "261", "262", "263", "264", "0",
"265", "266", "267", "268", "269", "270", "271", "272", "273",
"274", "0", "275", "276", "277", "278", "279", "280", "281",
"282", "0", "283", "284", "285", "286", "287", "0", "0", "0",
"0", "288", "0", "0", "0", "0", "0", "289", "290", "291", "292",
"293", "294", "295", "296", "297", "298", "299", "300", "301",
"302", "303", "304", "305", "306", "307", "308", "309", "310",
"311", "312", "313", "314", "315", "316", "317", "318", "319",
"320", "321", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0",
"0", "0", "322", "323", "324", "325", "326", "327", "328", "329",
"330", "331", "332", "333", "334", "335", "336", "337", "338",
"339", "340", "341", "0", "342", "343", "344", "345", "346",
"0", "347", "0", "348", "349", "350", "351", "352", "353", "354",
"355", "356", "357", "358", "359", "360", "0", "361", "362",
"363", "0", "364", "365", "0", "366", "367", "0", "0", "0", "0",
"0", "0", "0", "368", "0", "369", "370", "0", "0", "0", "0",
"0", "0", "0", "0", "371", "0", "0", "372", "0", "0", "0", "373",
"374", "375", "376", "377", "0", "0", "0", "0", "0", "378", "0",
"0", "0", "0", "0", "379", "380", "0", "0", "381", "382", "383",
"384", "0", "0", "385", "0", "0", "0", "0", "0", "0", "386",
"387", "388", "0", "389", "390", "391", "392", "393", "394",
"395", "396", "397", "398", "399", "400", "401", "402", "0",
"403", "404", "405", "406", "407", "408", "409"))
我会在可能的时候提供赏金... - CPak
我已经尝试了一半，类似spleq <- function(x, n) { sc <- sum(x)/n; split(x, (cumsum(x) + floor(sc) ) %/% (sum(x) / n)) }的代码似乎可以正常工作，但仍然存在一些问题。 - thelatemail
@thelatemail，非常接近了...我会试着玩一下你的想法。 - CPak
2
“平衡”一词的含义并没有严格定义。您可能应该定义一个要最小化的错误函数。 - algrid
建议避免将向量命名为t，因为在R中它已经是一个函数（转置）。 - Sotos
显示剩余2条评论
3个回答
5

我不知道是否有一些解析解。但如果你将其视为整数规划问题，则可以使用optim中实现的"SANN"启发式算法。例如，考虑使用一些（次优的）随机分割点来切割向量t。

> startpar <- sort(sample(length(t)-1, 3))
> startpar
[1] 5 6 9
> # result in a sub-optimal split
> split(t, cut(1:length(t), c(0, startpar, length(t)), labels = 1:4))
$`1`
 1  0  0  2  0 
 2  0  0 30  0 

$`2`
0 
0 

$`3`
   3    4    0 
  10 2000    0 

$`4`
 5  0  6  7  8 
20  0 40 60 10

错误函数可以写成：
> # from manual: A function to be minimized (or maximized)
> fn <- function(par, vec){
+   ind_vec <- cut(1:length(vec), c(0, par, length(vec)), labels = 1:4)
+   sd(unlist(lapply(split(vec, ind_vec), sum)))
+ }
> # evaluated at the starting parameters
> fn(startpar, t)
[1] 979.5625

"SANN" 启发式算法（模拟退火）需要一种生成新候选解的方法。可以有更复杂的方式选择函数或起始值，但目前的选择仍然能够得到接近最优解（也许在可接受的时间内）。请注意保留 HTML 标签。
> # from manual: For the "SANN" method it specifies a function to generate a new candidate point
> gr <- function(par, vec){
+   ind <- sample(length(par), 1)
+   par[ind] <- par[ind] + sample(-1:1, 1)
+   par[ind] <- max(c(par[ind], ifelse(ind == 1, 1, par[ind - 1] + 1)))
+   par[ind] <- min(c(par[ind], ifelse(ind == 3, length(vec) - 1, par[ind + 1] - 1)))
+   par
+ }

应用于玩具数据

> optimpar <- optim(startpar, fn, gr, method = "SANN", vec = t)$par
> split(t, cut(1:length(t), c(0, optimpar, length(t)), labels = 1:4))
$`1`
 1  0  0  2 
 2  0  0 30 

$`2`
 0  0  3 
 0  0 10 

$`3`
   4 
2000 

$`4`
 0  5  0  6  7  8 
 0 20  0 40 60 10 

> fn(optimpar, t)
[1] 972.7329
>

应用于真实数据

> # use for "hard"
> startpar <- sort(sample(length(hard)-1, 3))
> optimpar <- optim(startpar, fn, gr, method = "SANN", vec = hard)
> optimpar
$par
[1] 146 293 426

$value
[1] 4.573474
...[output shortened]
[编辑]由于我的初始结果不太理想。

我相信你已经找到了一个足够的替代方案，但为了完整起见：关于现有玩具和真实数据示例，更好的 gr 选择（我将其称为 gr2 以便日后参考）应该具有不同的采样长度（例如，依赖于数据的长度），以生成新的候选，这将比现任者（当前解决方案）更少地依赖。例如

> gr2 <- function(par, vec){
+   ind <- sample(length(par), 1)
+   l <- round(log(length(vec), 2))
+   par[ind] <- par[ind] + sample(-l:l, 1)
+   par[ind] <- max(c(par[ind], ifelse(ind == 1, 1, par[ind - 1] + 1)))
+   par[ind] <- min(c(par[ind], ifelse(ind == 3, length(vec) - 1, par[ind + 1] - 1)))
+   par
+ }

对于产生实际数据的

> set.seed(1337)
> 
> startpar <- sort(sample(length(hard)-1, 3))
> opt <- optim(startpar, fn, gr2, method = "SANN", vec = hard)
> opt$value
[1] 4.5
> lapply(split(hard, cut(1:length(hard), c(0, opt$par, length(hard)), labels = 1:4)), sum)
$`1`
[1] 140

$`2`
[1] 141

$`3`
[1] 144

$`4`
[1] 150

对于产生的玩具数据

> startpar <- sort(sample(length(t)-1, 3))
> opt <- optim(startpar, fn, gr2, method = "SANN", vec = t)
> opt$value
[1] 971.4024
> split(t, cut(1:length(t), c(0, opt$par, length(t)), labels = 1:4))
$`1`
 1  0  0  2  0  0  3 
 2  0  0 30  0  0 10 

$`2`
   4 
2000 

$`3`
 0  5  0  6 
 0 20  0 40 

$`4`
 7  8 
60 10

关于实际数据的最优性（使用gr2），我进行了一次短暂的模拟，共进行了100次不同起始参数的优化运行：每个运行在值4.5处终止。

谢谢Tom - 我在想一个模拟退火的方法，这给了我一个开始的地方。它产生的分割并不完全理想，但我会尝试调整一下，看看能否得到我想要的输出结果。 - CPak
没问题。啊，对了；我没有彻底检查结果。你可以稍微改变gr函数来生成一个更复杂的新候选人，例如通过将采样间隔扩大到[-3,3]（par[ind] <- par[ind] + sample(-3:3, 1)）或者更好的方法：依赖于vec的长度或其他一些统计数据。我会编辑我的答案。 - Tom
这太棒了。我会在可能的时候（大约14小时）提供赏金。同时，让我玩几天。起初我并没有真正理解你的梯度函数，但是你的更新帮助澄清了一些事情。我还有一个问题；在模拟退火中，通常有一个影响“重新采样”的温度计划，这在这里适用吗？如果适用，它如何影响梯度函数？ - CPak
这将是很好的。您可以通过控制选项(temp、tmax和maxit；请参阅optim手册了解详情)来控制温度和冷却方案。在当前的gr方法中，temp和t都不会进入新候选人的生成过程。我实际上从未尝试过在gr或fn中访问optim调用中的对象(例如控制参数)(甚至不知道是否可能)。当前温度至少会影响选择更差的新候选人作为新的代表者而不是更好的当前解决方案的概率(以避免局部最优解)。 - Tom
2
通过使用动态规划，您可以在O(N^2)时间内获得真正的最优解。诀窍是要看到最小化标准偏差与最小化行总和平方和相同。由于每个子向量的误差贡献是独立的，因此我们可以通过忽略次优子向量的扩展来减少可能分割的搜索空间。
例如，如果对于V[1:7]，“(3,5)”是比“(2,4)”更好的拆分，则从“(3,5,8,...)”开始的V的每个拆分都比从“(2,4,8,...)”开始的拆分更好。因此，如果对于每个“1
下面的“balanced.split”函数接受一个值向量和拆分数量，并返回一个子向量列表。这将在困难集上产生行总和为“140,141,144,150”的解。
balanced.split <- function(all.values, n.splits) {
    nonzero.idxs <- which(all.values!=0)
    values <- all.values[nonzero.idxs]
    cumsums = c(0, cumsum(values))
    error.table <- outer(cumsums, cumsums, FUN='-')**2
    # error.table[i, j] = error contribution of segment
    # values[i:(j-1)]

    # Iteratively find best i splits
    index.matrix <- array(dim=c(n.splits-1, ncol(error.table)))
    cur.best.splits <- error.table[1, ]
    for (i in 1:(n.splits-1)){
        error.sums <- cur.best.splits + error.table
        index.matrix[i, ] <- apply(error.sums, 2, which.min)
        # index.matrix[i, k] = last split of optimal (i+1)-group
        # split of values[1:k]
        cur.best.splits <- apply(error.sums, 2, min)
        # cur.best.splits[k] = minimal error function
        # of (i+1)-group split of values[1:k]
    }
    # Trace best splits
    cur.idx <- ncol(index.matrix)
    splits <- vector("numeric", n.splits-1)
    for (i in (n.splits-1):1) {
        cur.idx = index.matrix[i, cur.idx]
        splits[i] <- cur.idx
    }
    # Split values vector
    splits <- c(1, nonzero.idxs[splits], length(all.values)+1)
    chunks <- list()
    for (i in 1:n.splits)
        chunks[[i]] <- all.values[splits[i]:(splits[i+1]-1)]
    return(chunks)
}

以下是相同算法的更详细代码。
# Matrix containing the error contribution of 
# subsegments [i:j]
.makeErrorTable <- function(values) {
    cumsums = c(0, cumsum(values))
    return(outer(cumsums, cumsums, FUN='-')**2)
}

# Backtrace the optimal split points from an index matrix
.findPath <- function(index.matrix){
    nrows <- nrow(index.matrix)
    cur.idx <- ncol(index.matrix) 
    path <- vector("numeric", nrows)
    for (i in nrows:1) {
        cur.idx = index.matrix[i, cur.idx]
        path[i] <- cur.idx
    }
    return(path)
}

.findSplits <- function(error.table, n.splits) {
    n.diffs <- nrow(error.table)
    max.val <- error.table[1, n.diffs]

    # Table used to backtrace the optimal path
    idx.table <- array(dim=c(n.splits-1, n.diffs))
    cur.best.splits <- error.table[1, ]
    for (i in 1:(n.splits-1)){
        error.sums <- cur.best.splits + error.table
        idx.table[i, ] <- apply(error.sums, 2, which.min)
        cur.best.splits <- apply(error.sums, 2, min)
    }
    return(.findPath(idx.table))
}

# Split values at given split points
.splitChunks <- function(values, splits) {
    splits <- c(1, splits, length(values)+1)
    chunks <- list()
    for (i in 1:(length(splits)-1))
        chunks[[i]] <- values[splits[i]:(splits[i+1]-1)]
    return(chunks)
}

#' Main function that splits all.values into n.splits
#' chunks, minimizing sd(sum(chunk))    
balanced.split <- function(all.values, n.splits) {
    nonzero.idxs <- which(all.values!=0)
    values <- all.values[nonzero.idxs]
    error.table <- .makeErrorTable(values)
    splits <- .findSplits(error.table, n.splits)
    full.splits <- nonzero.idxs[splits]
    return(.splitChunks(all.values, full.splits))
}
这看起来很理想。它考虑了所有的分割组合（据我所知），生成了我需要的分割，并且使用大多数向量化操作而不会太贪婪地占用内存。我喜欢它，但我需要理解你所做的事情，并将其性能与SA方法进行比较。 - CPak
我现在添加了更多的解释和注释。它考虑了所有的分割组合，但这可能是一个弱点，因为它的搜索空间仍然很大。 - kuppern87
嘿@kuppern87：据Meta Stack所说，似乎没有办法向同一问题授予多个赏金。在我看来，这是一种很好的模拟退火答案。然而，因为它使用向量化，所以比模拟退火更消耗内存。因此，当内存有限时，应该选择模拟退火。如果内存不是限制因素，那么这就是正确的选择。希望stackoverflow将来可以允许多个正确答案。（我会给你的一些先前回答点赞，“奖励”你一些赏金，你也值得获得）。 - CPak
1
以下解决方案是“将t分割成一个由4个元素组成的列表，该列表基于结果列表元素的总和而平衡，同时保持元素的顺序，并仅在非零元素上进行拆分。”
尽管它没有产生您确切的预期输出，但据我理解，您的优化规则不是要求，而只是您尝试获得这些平衡列表的东西。而且它应该是有效的 :)。
t <- c(2, 0, 0, 30, 0, 0, 10, 2000, 0, 20, 0, 40, 60, 10)
groups <- cut(cumsum(t),
              breaks=quantile(cumsum(t),
                              probs=seq(0, 1, 0.25)),
              include.lowest =TRUE)

lapply(unique(groups),function(x) t[groups==x])

# [[1]]
# [1]  2  0  0 30  0  0
# 
# [[2]]
# [1] 10
# 
# [[3]]
# [1] 2000    0   20    0
# 
# [[4]]
# [1] 40 60 10

在您的硬性数据上，结果相当“平衡”：

t2 <- as.numeric(hard)
groups <- cut(cumsum(t2),
              breaks=quantile(cumsum(t2),
                              probs=seq(0, 1, 0.25)),
              include.lowest =TRUE)    

L2 <- lapply(unique(groups),function(x) t2[groups==x])
sapply(L2,sum)
# [1] 144 145 149 137

使用当前选择的解决方案来与 138 143 144 150 进行比较。

感谢@Moody；这显然非常高效，但它并没有产生我要找的精确分割（并且与thelatemail在评论中的答案并没有太大区别）。由于有些答案可以产生我要找的精确分割，所以我需要考虑性能/结果的权衡。 - CPak
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接