How can i combine the arrays?
[
['1','1','1','2','1'],
['3','3','4','4','4'],
['6','6','7','8','7'],
]
with those arrays there are many combinations, some of the are these:
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
how can we replace the wrong combination? one solution will be:
1,3,6
1,3,7 -> fixed
1,4,6
1,4,8
2,4,7 -> fixed
rules:
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
my attempt is: i would like to generate many combinations, but its not safe the number of appears
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))
}CodePudding user response：
Ignore that the individual strings contain digits. This doesn't matter. At that level, all that matters is that they're strings. (We wouldn't care about that either, just that they're some kind of comparable symbol, but we can take advantage of the fact that they're stings in validation.)
Integers, in general, don't have to have any particular representation. Just because, say, 3 is shaped like that doesn't say anything about the concept of 3. It could be represented in any way so long as it's unique relative to others of its type. For example, we could represent it as [1,1,1].
For each row, we need to iterate through the permutations of that row. Heap's Algorithm allows us to do that in a predictable way without breaking the rules for how many of each kind of item goes in each row.
If we think of that iteration as a kind of counting (the first permutation is 1, the next is 2, etc.), we can count through the permutations of each row as though they were digits in a strange kind of integer. In this way, we can iterate over all combinations of the permutations of the rows.
All that's left is validating each result against duplicate columns. We do this by joining along columns, and adding the results to a set. So long as the set ends up with the same length as the rows, we know there were no duplicates.
solve() only returns the first solution encountered, if any. However, it would be pretty simple to adjust it to return all solutions.
We use .every as a kind of .forEach with the additional ability to end the loop early and to signal whether or not that happened.
function* is known as a generator function. They return a generator object, a thing that wraps the function and lets you return values (via yield) and then later come back and resume the function from that point.
// 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; }CodePudding user response：
Maybe I'm missing something, but it seems like you're looking for the product of the arrays with only unique combinations of elements -
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
By inverting the loops, we can generate the unique products in lexicographical order -
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
Finally we can generate the products lazily by using a generator -
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
If you are looking for permutations, see this related Q&A.