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

Question

Katsimoto @Katsimoto

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

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

Вопрос задан более трёх лет назад
309 просмотров

4 комментария

Подписаться 1 Средний 4 комментария

Сергей Соколов @sergiks Куратор тега JavaScript

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

Написано более трёх лет назад
Katsimoto @Katsimoto Автор вопроса

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

Написано более трёх лет назад
Сергей Соколов @sergiks Куратор тега JavaScript

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

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

Написано более трёх лет назад
Katsimoto @Katsimoto Автор вопроса

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

Написано более трёх лет назад

обязательно из каждого массива по 1 цифре использовать? Или полная свобода: вывалили все цифры в один мешок и тащим оттуда всё что попало.
Сергей Соколов, в данном примере это получается как бы 3 варианта значения, которое это число может принимать, то есть первый массив это число, которое может принимать значение либо 1, либо 2, либо 3, второй это число, которое может принимать значение либо 2, либо 3, либо 4 и т. д., в результате из возможных значений для каждого из 4-х чисел должно получится 4-хзначное число, возможные значения для каждого числа от 1-го до 4-х, а конечное число может быть от 1 до 8 знаков длиной
Вот это в конце не понял:
возможные значения для каждого числа от 1-го до 4-х, а конечное число может быть от 1 до 8 знаков длиной

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

Answer 1 · 2019-08-06 15:48:03

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

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

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

Войдите на сайт