Найти все комбинации путей
Не знаю, есть ли у этого конкретное имя, но мне нужно сгладить массив одномерных массивов и простых элементов таким образом, чтобы сообщались все комбинации до листового «узла». Вот пример, потому что приведенное выше оставляет много места для воображения:
// My input array contains single elements or 1D arrays:
let input = [1, 2, [3, 4], [5, 6]];
Развертывание происходит таким образом, что каждый раз, когда встречается массив, пути разбиваются на столько элементов, сколько содержит массив:
// current result = [1, 2]
// unconsumed input [[3, 4], [5, 6]]
// ->
// current result = [ [1, 2, 3], [1, 2, 4] ]
// current result = [ [1, 2, 3], [1, 2, 4] ]
// unconsumed input [[5, 6]]
// ->
// final result = [ [1, 2, 3, 5], [1, 2, 4, 5], [1, 2, 3, 6], [1, 2, 4, 6] ]
Я могу что-то напутать с копиями и псевдонимами, но, похоже, не могу заставить это работать правильно и обрабатывать особые случаи, такие как:
let input1 = [1, 2, 3]; // No nested arrays
let input2 = []; // Empty input
Попытался построить результат в обратном порядке, так как здесь удобно использовать .pop, но не могу заставить его работать:
function flatPath(input, result = [[]]) {
while (input.length) {
const last = input.pop();
if (Array.isArray(last)) {
result = flatPath(last, [...result, ...result]);
} else {
for (let ar of result) {
result.push(last);
}
}
}
return result;
}
let result = flatPath([1, 2, [3, 4], [2, 5, 6] ]);
console.info(result);
но не могу даже пройти компиляцию (я использую машинописный текст), так как все, что я получаю, это:
Параметр input неявно имеет тип any.
Аргумент типа «любой» нельзя присвоить параметру типа «никогда».
В чем проблема с моим кодом или есть ли лучший (более идиоматический) способ сделать это.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 4
Я могу скомпилировать ваш код, но он переходит в бесконечный цикл. Я думаю, что проблема в этой части;
for (let ar of result) {
result.push(last);
}
Вы помещаете элементы в массив result, перебирая его. Это вызывает бесконечный цикл.
Чтобы решить эту проблему, вы можете создать отдельный массив для хранения новых элементов, а затем соединить его с массивом result вне цикла.
Следующее работает нормально;
const newElements = [];
for (let ar of result) {
newElements.push(last);
}
result = result.concat(newElements);
Это отличный вариант использования функции-генератора, потому что он позволяет вам yield получать результаты в заметках о выходе (чья кардинальность неизвестна априори), вместо того, чтобы обрабатывать агрегацию по дереву вызовов рекурсии.
const flatPath = function*(array, prefix = []) {
const next = array[0];
if (next === undefined) { // base case
yield prefix;
} else if (next instanceof Array) {
for (let item of next) {
yield * flatPath(array.slice(1), [...prefix, item]);
}
} else {
yield * flatPath(array.slice(1), [...prefix, next]);
}
};
const result = Array.from(flatPath([1, 2, [3, 4], [2, 5, 6]]));
console.info(result);
/* output:
[
[ 1, 2, 3, 2 ],
[ 1, 2, 3, 5 ],
[ 1, 2, 3, 6 ],
[ 1, 2, 4, 2 ],
[ 1, 2, 4, 5 ],
[ 1, 2, 4, 6 ]
]
*/хороший улов! зафиксированный.
Вы можете справиться с этим, не передавая массив контекста, агрегируя результаты снизу вверх здесь, используя map(), чтобы добавить каждый элемент, не являющийся массивом, из предыдущего вызова в возвращенные подмассивы из более глубоких вызовов.
function flatPath([next, ...rest]) {
if (next === undefined) {
return [[]];
}
if (Array.isArray(next)) {
const temp = [];
for (const n of next) {
temp.push(...flatPath([n, ...rest]));
}
return temp;
}
return flatPath(rest).map(t => [next, ...[].concat(t)]);
}
// Test output
for (const test of [
[1, 2, [3, 4], [5, 6]],
[1, 2, 3],
[[1, 2, 3], 4],
[]
]) {
let result = flatPath(test);
console.info(JSON.stringify(result));
}
// [[1,2,3,5],[1,2,3,6],[1,2,4,5],[1,2,4,6]]
// [[1,2,3]]
// [[1,4],[2,4],[3,4]]
// [[]]Вышеприведенное не удастся, если у вас есть элемент undefined в вашем массиве, который фиксируется ниже путем проверки длины ...rest для определения основания (и явной проверки пустых массивов, переданных в качестве входных данных).
function flatPath(input) {
if (input.length === 0) {
return [];
}
const [next, ...rest] = input;
if (Array.isArray(next)) {
const temp = [];
for (const n of next) {
const tail = rest.length
? flatPath([n, ...rest])
: flatPath([].concat(n));
temp.push(...tail);
}
return temp;
}
return rest.length
? flatPath(rest).map(t => [next, ...[].concat(t)])
: [next];
}
// Test output
for (const test of [
[1, 2, [3, 4], [5, 6]],
[1, 2, 3],
[[1, 2, 3], 4],
[]
]) {
let result = flatPath(test);
console.info(JSON.stringify(result));
}
// [[1,2,3,5],[1,2,3,6],[1,2,4,5],[1,2,4,6]]
// [[1,2,3]]
// [[1,4],[2,4],[3,4]]
// [[]]Эта версия, написанная независимо, выражает тот же алгоритм, что и ответ от пилчарда. Но он убирает некоторые вещи и использует чистые выражения, а не операторы, как я всегда предпочитаю:
const process = ([xs, ...xss], rs = xs !== undefined && process(xss)) =>
xs === undefined
? [[]]
: Array.isArray(xs)
? xs.flatMap(x => rs.map(r => [x, ...r]))
: rs.map(r => [xs, ...r]);
const input = [1, 2, [3, 4], [5, 6]]
console .log(JSON.stringify(process (input)))Ответ Пилчарда также выразил беспокойство по поводу возможных значений undefined во входных данных. Если это вызывает беспокойство, простым решением было бы ввести Symbol, например:
const None = Symbol()
const process = ([xs = None, ...xss], rs = xs !== None && process(xss)) =>
xs === None
? [[]]
: Array.isArray(xs)
? xs.flatMap(x => rs.map(r => [x, ...r]))
: rs.map(r => [xs, ...r])
const input = [1, 2, [3, 4], [5, 6]]
Но я бы не стал заморачиваться, если только вы не ожидаете и не хотите обрабатывать undefined значения.
вы можете попробовать typescriptlang.org/play?target=99&jsx=0#code/…