是否有按存储桶大小对阵列进行分区的"named"算法

Question

我想采用一个输入数组和一组可能的大小，并将数组划分为子数组，每个子数组的可能最大存储桶大小小于剩余项目数。

所以给定输入数组...

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

还有尺寸...

[10, 5, 3, 2, 1]

它会返回一个数组，例如...

[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12, 13], [14]]

首先分区 10，然后分区 3，然后分区 1。

我可以使用while循环等以非常笨拙的方式做到这一点，但我想知道这种算法是否有某种名称，我可以研究一些更优雅的方法。

Answer 1

多亏了@AnandUndavia，我不是作为一个数组分区练习来解决这个问题，而是一个硬币变化问题。

我能够使用这个函数解决这个问题...(斯威夫特(

func separate(numberOfItems n: Int, bucketSizes sizes: [Int]) -> [Int] {
var output = [Int]()
var remaining = n
for size in sizes {
while remaining >= size {
output.append(size)
remaining -= size
}
}
return output
}

现在，有了我的尺寸阵列，我可以轻松解决我正在处理的其余问题:D

Answer 2

您也可以在单个循环中实现此目的。像这样的东西是JS：

var inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
var sizeArray = [10, 3, 5, 2, 1];
var outputArray = [];
sizeArray.sort(function(a, b) { return b-a}); // Sort array in decreasing order
while(sizeArray.length > 0 && inputArray.length > 0){
var m = sizeArray[0];
sizeArray = sizeArray.slice(1); // Pop the first element from Size Array
if(m <= inputArray.length){
outputArray.push(inputArray.slice(0, m)); // Extract first m elements from inputArray if its size is greater than m
inputArray = inputArray.slice(m);
}
}
console.log(outputArray);