Перебор всех возможных сочетаний элементов массива
Суть проблемы: дан отсортированный одномерный массив, состоящий из простых чисел, например: [2, 3, 3, 5] На выходе необходимо получить все возможные произведения элементов исходного массива, а именно: [2], [3], [5], [2х3], [2х3х3], [2х3х3х5], [3х3], [3х3х5], [3х5], [2х5], [2х3х5]
Как я пробовал это решить:
function counter (arr) {
return arr.reduce((acc, el) => {
acc[el] = (acc[el] || 0) + 1
return acc
}, {})
}
Здесь получал объект, включающий все элементы массива и их степени, далее пробовал написать алгоритм перебора по принципу поиска делителей числа, то есть, возводить каждый элемент массива в степени от 0 до значения элемента в объекте, например, для [2, 3, 3, 5] объект выглядит так:
{ '2': 1, '3': 2, '5': 1 }
Также смог получить все степени для каждого элемента массива (в данном случае это [0, 1] для 2, [0,1,2] для 3, [0,1] для 5), но вот присвоить эти степени исходным элементам и перемножить у меня не вышло.
Спасибо всем, кто откликнется!
Ответы (3 шт):
Я понял ход ваших мыслей. Не понятно только, в каком месте и почему остановились.
Возьмем массив [2, 3, 3, 5].
Уберём повторения, получим [2, 3, 5], а массив со степенями – [1, 2, 1].
Если прибавить к каждому элементу единицу, то получим [2, 3, 2]. Каждый элемент этого массива есть размер упорядоченного множества степеней для соответствующих элементов исходного массива [2, 3, 5] (включая нулевую степень). А задача сводится к перебору декартова произведения этих множеств.
Иными словами, на массив [2, 3, 2] мы смотрим как на модули разрядов (основания) будущего счетчика-кортежа, значения которого и требуется перебрать: [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 2, 0] и т.д. (разряды в обратном порядке).
Если перемножить элементы и отнять единицу (кортеж [0, 0, 0] исключаем), то получим число комбинаций: 2 * 3 * 2 - 1 = 11.
Чтобы получить искомое произведение, например, для [2, 3, 5] и кортежа [1, 1, 0], нужно вычислить:
21 * 31 * 50.
Перебрать все комбинации можно разными способами. Привожу один из них:
let array = [2, 3, 3, 5];
let object = getBases(array);
let values = Object.keys(object); // массив без повторений
let bases = Object.values(object); // основания
let total = bases.reduce((a, v) => a * v);
let counter = Array(values.length).fill(0);
while (--total) {
counter.some((e, ci) => (counter[ci] = (e + 1) % bases[ci]));
let product = counter.reduce((a, v, i) => a * Math.pow(values[i], v), 1);
console.log('[' + getSet(counter).join(',') + ']', product);
}
//////////
function getBases(arr) {
return arr.reduce((a, v) => {
a[v] = (a[v] || 1) + 1;
return a
}, {});
}
function getSet(counter) {
return counter.reduce((a, v, i) => {
if (v) a.push(...Array(v).fill(values[i]));
return a;
}, []);
}
UPD
Еще один вариант не для слабонервных:
const values = [2, 2, 2, 3, 3, 3];
const masks = getMasks(values);
const max = 1 << values.length;
for (let num = 1; num < max; num++) {
for (let i = 0; i < masks.length; i++) {
let m = masks[i];
let chk = num >> m[1];
let val = (chk & m[0]) - 1;
if (val > 0 && !(chk & 1)) {
num = (num & ~m[1]) | (val & m[0]) << m[1];
}
}
console.log(getProd(num));
}
function getProd(num, i = 0, prd = 1) {
while (num) {
if (num & 1) prd *= values[i];
num >>= 1; i++;
}
return prd;
}
function getMasks(array) {
return Object.values(
array.reduce((a, v, i) => (
a[v] = a[v] ? [a[v][0] + 1, a[v][1]] : [0, i], a), {})).filter(
v => v[0] ? v[0] = (1 << v[0] + 1) - 1 : false
);
}
Рекурсивный метод. В JS я не спец, так что условие if слепил как попало, наверное.
На каждом шаге мы делаем рекурсивные вызовы со следующем индексом (idx + 1) массива, при этом либо пропускаем текущий элемент (omit устанавливаем в 1, prod не изменяем) , либо используем его (передавая дальше prod * arr[idx]).
Однако, если мы пропустили первый элемент из серии одинаковых, то остальные тоже не нужны, чтобы не было одинаковых наборов. Вот условие в if и служит этой цели - если предыдущий элемент был пропущен, и текущий с ним совпадает, то и текущий не включать в набор множителей.
function counter (arr, idx, omit, prod) {
if (idx >= arr.length)
console.log(prod);
else {
counter (arr, idx + 1, 1, prod);
if(!(idx>0 && omit && arr[idx]==arr[idx-1]))
counter (arr, idx + 1, 0, prod * arr[idx]);
}
}
counter([2,3,3,5],0,1,1)
Так как массив простых упорядочен, можно обойтись без словаря. Массив [2, 3, 3, 5] преобразуется в массив пар [основание, степень]: [[2, 1], [3, 2], [5, 1]]. Произведения порождаются рекурсивным генератором iter. Вызов iter(i) перечисляет все произведения начиная с i-той пары.:
const products = factors => {
const pairs = [];
for (const f of factors) {
if (pairs.length === 0 || f !== pairs[pairs.length - 1][0]) {
pairs.push([f, 1]);
} else {
++pairs[pairs.length - 1][1];
}
}
function* iter(i) {
if (i === pairs.length) {
yield 1;
} else {
const [b, e] = pairs[i];
for (let p of iter(i + 1)) {
yield p;
for (let j = 0; j < e; ++j) {
p *= b;
yield p;
}
}
}
};
return iter(0);
};
console.log(...products([2, 2, 2, 2, 2, 2]));
console.log(...products([2, 2, 2, 3, 3, 3]));
console.log(...products([2, 3, 3, 5]));
$ node products.js 1 2 4 8 16 32 64 1 2 4 8 3 6 12 24 9 18 36 72 27 54 108 216 1 2 3 6 9 18 5 10 15 30 45 90
Можно обойтись без создания массива пар:
const products = factors => {
function* iter(i) {
if (i === factors.length) {
yield 1;
} else {
const f = factors[i];
let j = i + 1;
for (; factors[j] === f; ++j) {
}
for (let p of iter(j)) {
yield p;
for (let k = i; k < j; ++k) {
p *= f;
yield p;
}
}
}
}
return iter(0);
};
Самый короткий вариант с генератором. Идея украдена из ответа MBo:
const products = factors => {
function* iter(i, branch) {
if (i === factors.length) {
yield 1;
} else {
yield* iter(i + 1, false);
const f = factors[i];
if (branch || f !== factors[i - 1]) {
for (const p of iter(i + 1, true)) {
yield f * p;
}
}
}
}
return iter(0, true);
};