我很了解这个网站，但是我没有找到包含重复元素的答案。例如，给定以下数组:
[1,2,3,4]
有一个长度为3的函数，应该生成使用每个数字超过一次的这些数字的每个可能组合的列表：
[
[1,1,1],
[1,1,2],
[1,1,3],
...
[4,4,2],
[4,4,3],
[4,4,4]
]
我只是无法理解我应该使用哪个算法。 我不期望得到源代码的答案，但是希望能得到正确方向的指引。
我已经尝试使用reduce函数，像这样：
const arr = [1, 2, 3, 4]
const len = 3
arr.reduce((acc, n) => {
for (let i = 0; i < len; i++) {
acc.push(/* ???? */)
}
return acc
}, [])
但我真的不知道该如何继续。
值得一提的是，理想情况下，我希望尽可能高效地完成这件事。
一种方法是使用数组的长度作为基础。然后，您可以从0开始访问数组的元素，并计数到组合的数量（数组长度**长度）。如果您正在处理小数据集，则性能不应成为问题，但本答案非常注重性能:
const getCombos = (arr, len) => {
const base = arr.length
const counter = Array(len).fill(base === 1 ? arr[0] : 0)
if (base === 1) return [counter]
const combos = []
const increment = i => {
if (counter[i] === base - 1) {
counter[i] = 0
increment(i - 1)
} else {
counter[i]++
}
}
for (let i = base ** len; i--;) {
const combo = []
for (let j = 0; j < counter.length; j++) {
combo.push(arr[counter[j]])
}
combos.push(combo)
increment(counter.length - 1)
}
return combos
}
const combos = getCombos([1, 2, 3, 4], 3)
console.log(combos)您可以使用算法来获取具有所需值的三个数组的笛卡尔积。
var values = [1, 2, 3, 4],
length = 3,
result = Array
.from({ length }, _ => values)
.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
console.log(result.map(a => a.join(' ')));.as-console-wrapper { max-height: 100% !important; top: 0; }
00000 到 99999 的计数方法是，将最右边的轮子旋转到 9，然后它会重置为 0，第二个右边的轮子就会向前进 1，以此类推。function counter(digits, size) {
let wheels = Array(size).fill(0),
len = digits.length,
res = [];
while (1) {
res.push(wheels.map(n => digits[n]));
for (let i = size - 1; i >= 0; i--) {
if (wheels[i] < len - 1) {
wheels[i]++;
wheels.fill(0, i + 1);
break;
}
if (i === 0)
return res;
}
}
}
all = counter('1234', 3)
console.log(...all.map(c => c.join('')))const kobe = (arr, len) => {
const base = arr.length
const counter = Array(len).fill(base === 1 ? arr[0] : 0)
if (base === 1) return [counter]
const combos = []
const increment = i => {
if (counter[i] === base - 1) {
counter[i] = 0
increment(i - 1)
} else {
counter[i]++
}
}
for (let i = base ** len; i--;) {
const combo = []
for (let j = 0; j < counter.length; j++) {
combo.push(arr[counter[j]])
}
combos.push(combo)
increment(counter.length - 1)
}
return combos
}
function nina(values, length) {
return Array
.from({length}, _ => values)
.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
}
function trincot(digits, size) {
if (!size) return [[]]; // base case
let shorter = trincot(digits, size - 1); // get all solutions for smaller size
// ...and prefix each of those with each possible digit
return Array.from(digits, dig => shorter.map(arr => [dig, ...arr])).flat();
}
function georg(digits, size) {
let wheels = Array(size).fill(0),
len = digits.length,
res = [];
while (1) {
res.push(wheels.map(n => digits[n]));
for (let i = size - 1; i >= 0; i--) {
if (wheels[i] < len - 1) {
wheels[i]++;
wheels.fill(0, i + 1);
break;
}
if (i === 0)
return res;
}
}
}
const gilad = (A, k) =>
k ? gilad(A, k - 1).reduce((a, s) => a.concat(A.map(e => s.concat(e))), []) : [[]]
//////////////////////////////////////////////////////////////
fns = [kobe, nina, trincot, georg, gilad];
ary = [0, 1, 2, 3, 4, 5, 6, 7, 8]
size = 5
res = []
for (f of fns) {
console.time(f.name);
res.push(f(ary, size));
console.timeEnd(f.name)
}function product(...arrays) {
let size = arrays.length,
wheels = Array(size).fill(0),
lens = arrays.map(a => a.length),
res = [];
while (1) {
res.push(wheels.map((n, w) => arrays[w][n]));
for (let w = size - 1; w >= 0; w--) {
if (wheels[w] < lens[w] - 1) {
wheels[w]++;
wheels.fill(0, w + 1);
break;
}
if (w === 0)
return res;
}
}
}
// demo
p = product('12', 'abcde', 'XYZ')
console.log(...p.map(q => q.join('')))
// some timings
// https://dev59.com/xWct5IYBdhLWcg3wKqQd#43053803
const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);
arrays = Array(7).fill(0).map(_ => Array(5).fill(0)) // 5**7=78125 combinations
console.time('func')
cartesian(...arrays)
console.timeEnd('func')
console.time('iter')
product(...arrays)
console.timeEnd('iter')function counter(digits, size) {
if (!size) return [[]]; // base case
let shorter = counter(digits, size-1); // get all solutions for smaller size
// ...and prefix each of those with each possible digit
return Array.from(digits, dig => shorter.map(arr => [dig, ...arr])).flat();
}
// demo
let all = counter("1234", 3);
console.log(...all.map(c => c.join("")));function f(ns, n, k){
if (n == 0)
return []
if (k == 0)
return [[]]
return f(ns, n - 1, k).concat(
f(ns, n, k - 1).map(s => s.concat(ns[n-1])))
}
var multiset = [1, 2, 3, 4]
var k = 3
console.log(JSON.stringify(f(multiset, multiset.length, k)))const f = (A, k) =>
k ? f(A, k - 1).reduce((a, s) => a.concat(A.map(e => s.concat(e))), []) : [[]]
var A = [1, 2, 3, 4]
var k = 3
console.log(JSON.stringify(f(A, k)))1,2,1、1,3,1 等。 - georg