我如何組合陣列？
[
['1','1','1','2','1'],
['3','3','4','4','4'],
['6','6','7','8','7'],
]
這些陣列有很多組合，其中一些是：
1,3,6
1,3,6 -> this not, because its duplicate
1,4,7
2,4,8
1,4,7 -> this not, because its duplicate
我們如何替換錯誤的組合？一種解決方案是：
1,3,6
1,3,7 -> fixed
1,4,6
1,4,8
2,4,7 -> fixed
規則：
in the first column, 1 should appear 4 times
in the first column, 2 should appear 1 times
in the second column, 3 should appear 2 times
in the second column, 4 should appear 3 times
in the third column, 6 should appear 2 times
in the third column, 7 should appear 2 times
in the third column, 8 should appear 1 times
我的嘗試是：我想生成很多組合，但出現的數量并不安全
function available(array) {
let currentIndex = array.length,
randomIndex;
while (currentIndex != 0) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
[array[currentIndex], array[randomIndex]] = [
array[randomIndex], array[currentIndex]
];
}
return array;
}
const arrays = [
['1', '1', '1', '2', '1'],
['3', '3', '4', '4', '4'],
['6', '6', '7', '8', '7'],
]
for (const current of arrays) {
console.log(available(current))
}uj5u.com熱心網友回復：
忽略單個字串包含數字。這沒關系。在那個級別上，重要的是它們是字串。（我們也不會關心這一點，只是它們是某種可比較的符號，但我們可以利用它們在驗證中被刺痛的事實。）
一般來說，整數不必有任何特定的表示。僅僅因為，比如說，3形狀像那樣，并不能說明3. 它可以以任何方式表示，只要它相對于其他同類產品是獨一無二的。例如，我們可以將其表示為[1,1,1]。
對于每一行，我們需要遍歷該行的排列。堆演算法允許我們以可預測的方式做到這一點，而不會違反每行中每種專案有多少的規則。
如果我們將該迭代視為一種計數（第一個排列是1，下一個排列是2，等等），我們可以通過每一行的排列來計數，就好像它們是一種奇怪的整數中的數字一樣。通過這種方式，我們可以迭代行排列的所有組合。
剩下的就是針對重復的列驗證每個結果。我們通過沿列連接并將結果添加到集合中來做到這一點。只要集合以與行相同的長度結束，我們就知道沒有重復。
solve()僅回傳遇到的第一個解決方案（如果有）。但是，調整它以回傳所有解決方案將非常簡單。
我們將.every其用作一種.forEach具有提前結束回圈并發出信號是否發生的附加功能。
function*被稱為生成器函式。它們回傳一個生成器物件，一個包裝函式并讓您回傳值（通過yield）然后回傳并從該點恢復函式的東西。
// Heap's Algorithm modified to skip swaps of the same value
// Allows us to iterate over permutations of a row
function* iterHeapsAlgo(arr) {
const A = Array.from(arr); // shallow copy
const len = A.length;
const c = new Array(len).fill(0);
let i = 0;
yield A;
while(i < len) {
if(c[i] < i) {
let j = i&1 ? c[i] : 0;
if(A[i] != A[j]) {
[A[j], A[i]] = [A[i], A[j]];
yield A;
}
c[i] ;
i = 0;
} else {
c[i] = 0;
i ;
}
}
};
// Iterate over all combinations of all rows
// Typical counting algorithm with shortcut to take advantage of exposed state
function* iterCount(data) {
const state = data.map(v => iterHeapsAlgo(v));
const current = state.map(v => v.next().value);
yield current;
while(true) {
const isEnd = state.every((v,i) => {
let n = v.next();
if(n.done) {
state[i] = iterHeapsAlgo(data[i]);
current[i] = state[i].next().value;
return true;
}
});
if(isEnd) return;
yield current;
}
}
const validate = data => {
const set = new Set();
return data[0].every((_,i) => {
set.add(data.reduce((s,v) => s v[i]));
return set.size-1 == i;
});
};
const solve = start => {
const state = iterCount(start);
while(true) {
const current = state.next();
if(current.done) break;
if(validate(current.value)) {
return current.value.map(v => Array.from(v)); // depth 2 copy
}
}
return null;
}
console.log(solve([
['1','1','1','2','1'],
['3','3','4','4','4'],
['6','6','7','8','7'],
]) || 'No solution found');.as-console-wrapper { top: 0; max-height: 100% !important; }uj5u.com熱心網友回復：
也許我遺漏了一些東西，但看起來你正在尋找product只有unique元素組合的陣列 -
const unique = a =>
Array.from(new Set(a))
const product = t =>
t.length == 0
? [[]]
: product(t.slice(1)).flatMap(p => unique(t[0]).map(v => [v, ...p]))
const myinput = [
['1','1','1','2','1'],
['3','3','4','4','4'],
['6','6','7','8','7'],
]
for (const combination of product(myinput))
console.log(String(combination))1,3,6
2,3,6
1,4,6
2,4,6
1,3,7
2,3,7
1,4,7
2,4,7
1,3,8
2,3,8
1,4,8
2,4,8
通過反轉回圈，我們可以按字典順序生成唯一的產品 -
const bind = (f, x) => f(x)
const unique = a =>
Array.from(new Set(a))
const product = t =>
t.length == 0
? [[]]
: bind
( r => unique(t[0]).flatMap(v => r.map(p => [v, ...p]))
, product(t.slice(1))
)
const myinput = [
['1','1','1','2','1'],
['3','3','4','4','4'],
['6','6','7','8','7'],
]
for (const combination of product(myinput))
console.log(String(combination))1,3,6
1,3,7
1,3,8
1,4,6
1,4,7
1,4,8
2,3,6
2,3,7
2,3,8
2,4,6
2,4,7
2,4,8
最后，我們可以使用生成器懶惰地生成產品 -
const unique = a =>
Array.from(new Set(a))
function* product(t) {
if (t.length == 0)
yield []
else
for (const p of product(t.slice(1)))
for (const v of unique(t[0]))
yield [v, ...p]
}
const myinput = [
['1','1','1','2','1'],
['3','3','4','4','4'],
['6','6','7','8','7'],
]
for (const combination of product(myinput))
console.log(String(combination))1,3,6
2,3,6
1,4,6
2,4,6
1,3,7
2,3,7
1,4,7
2,4,7
1,3,8
2,3,8
1,4,8
2,4,8
如果您正在尋找permutations，請參閱此相關問答。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422785.html
標籤：
下一篇：超過LeetCode40時間限制