Усложненная генерация перестановок (желательно JS, но и псевдокод подойдёт)?

Question

[Katsimoto]

Всем привет. Есть от 1 до 8 массивов, в каждом из которых от 2 до 4 элементов (все элементы цифры). Нужно перебрать все эти цифры таким образом, чтобы получились все возможные варианты числа от 1 до 8 знаков. Например, есть массивы [1, 2, 3], [2, 3, 4], [5, 6], [7, 8, 9]. Нужно как-то сделать так, чтобы получились всевозможные варианты числа, например, 1359, 2258 и т. д.
Подскажите пожалуйста, в какую сторону копать, какой алгоритм использовать. Думал реализовать это через 8 циклов, если допустим массивов будет всего 4, то тогда 5 и далее цикл не запускается, но что-то кажется мне это совсем колхоз и должен быть какой-то изящный вариант. Знания очень слабые, но решить задачу хочется.
Желательно без готовых решений, а просто написать алгоритм, даже словами. Заранее большое спасибо!

Comments

[Сергей Соколов]

обязательно из каждого массива по 1 цифре использовать? Или полная свобода: вывалили все цифры в один мешок и тащим оттуда всё что попало.

[Katsimoto]

Сергей Соколов, в данном примере это получается как бы 3 варианта значения, которое это число может принимать, то есть первый массив это число, которое может принимать значение либо 1, либо 2, либо 3, второй это число, которое может принимать значение либо 2, либо 3, либо 4 и т. д., в результате из возможных значений для каждого из 4-х чисел должно получится 4-хзначное число, возможные значения для каждого числа от 1-го до 4-х, а конечное число может быть от 1 до 8 знаков длиной

[Сергей Соколов]

Вот это в конце не понял:

возможные значения для каждого числа от 1-го до 4-х, а конечное число может быть от 1 до 8 знаков длиной

Так из 4-х массивов должны получаться только 4-х значные числа в итоге? Было бы 5 массивов - все числа были бы 5-значные? Или не так?

[Katsimoto]

Сергей Соколов, нет, смотрите, на входе мы получаем число от 1 до 8 знаков длиной, каждый знак может принимать от 1 до 4 вариантов значения (например, на входе число 4256, 4 может принимать значения [1, 4, 5], 2 может принимать значения [1, 3, 5] и т. д.), какое значение может принимать каждое из чисел известно заранее и записано в массив, теперь нам нужно сделать так, чтобы мы получили все возможные варианты значений для полученного на входе числа и вывели все их в строку через запятую

Answer 1

[Алексей Ярков]

const parts = [
  [0, 1],
  [0, 1, 2, 3],
  [0, 1, 2],
  [0, 1, 2, 3, 4, 5],
  [0, 1, 2],
  [0, 1, 2, 3],
  [0, 1],
  [0, 1, 2]
];
const result = parts.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

console.log(result.map(a => a.join(', ')));

Comments

[Katsimoto]

Большое спасибо за ответ! Я сейчас разберу со справочником что это всё значит, и возможно смогу применить это в решении (не знаю что значит .reduce, .concat, .map). Единственное, количество массивов, которые будут содержаться в parts, заранее неизвестно, но я так понимаю это детали и для меня вся соль в строчке где много непонятных слов :)

[Алексей Ярков]

Katsimoto, ограничений на количество массивов и элементов в них здесь нет. Ну кроме памяти и скорости выполнения ))

что значит .reduce, .concat, .map

Это всего лишь методы массива в JavaScript. Справочник прояснит более детально ))

[Katsimoto]

Алексей Ярков, разобрался, спасибо большое! Очень лаконично и грамотно. Сидел весь день разбирал, читал про методы, дебажил, только сейчас полностью разобрал эту строку :)

[Алексей Ярков]

Katsimoto, рад что смог помочь

Answer 2

[Петр Мухуров]

arr.reduce((acc, numbers, index) => {
  return index === 0 ? numbers : numbers.reduce((numAcc, num) => {
    return [...numAcc, ...acc.map(i => `${i}${num}`)]
  }, []);
}, []);

но жрет сие действо кучу памяти)

Comments

[Katsimoto]

Большое спасибо за ответ! Сейчас разберу что всё это значит, и возможно смогу применить в решении.

[Петр Мухуров]

Katsimoto, можно запустить код в дебаггере, поставив точку останова внутри первого редьюса, и посмотреть на промежуточные результаты, тогда станет понятнее