与重复结合 [英] Combination with repetition
本文介绍了与重复结合的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在寻找一种方法来获取所有可能的与数组输入的组合,因此,如果我们有 [1,2,3]
,它将返回
I am looking for a way to get all possible combination with an array intake so if we had [1,2,3]
it would return
[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3].
我在这里查看了其他几篇类似的文章: https://stackoverflow.com/a/9960925/1328107 但它们似乎都无法满足所有组合要求,即
I have looked at several other posts such as this one here: https://stackoverflow.com/a/9960925/1328107 but they all seem to stop short of all combinations, ie
[ 1, 2, 3 ], [ 1, 3, 2 ],[ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ].
任何帮助将不胜感激.
推荐答案
回溯将解决问题:
function combRep(arr, l) {
if(l === void 0) l = arr.length; // Length of the combinations
var data = Array(l), // Used to store state
results = []; // Array of results
(function f(pos, start) { // Recursive function
if(pos === l) { // End reached
results.push(data.slice()); // Add a copy of data to results
return;
}
for(var i=start; i<arr.length; ++i) {
data[pos] = arr[i]; // Update data
f(pos+1, i); // Call f recursively
}
})(0, 0); // Start at index 0
return results; // Return results
}
一些例子:
combRep([1,2,3], 1); /* [
[1], [2], [3]
] */
combRep([1,2,3], 2); /* [
[1,1], [1,2], [1,3],
[2,2], [2,3],
[3,3]
] */
combRep([1,2,3], 3); /* [
[1,1,1], [1,1,2], [1,1,3],
[1,2,2], [1,2,3],
[1,3,3],
[2,2,2], [2,2,3],
[2,3,3],
[3,3,3],
] */
combRep([1,2,3]); /* Same as above */
这篇关于与重复结合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文