0

Суть проблемы: дан отсортированный одномерный массив, состоящий из простых чисел, например: [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), но вот присвоить эти степени исходным элементам и перемножить у меня не вышло.

Спасибо всем, кто откликнется!

1
  • Уточните, пожалуйста, нужно получить именно все возможные произведения? Ведь, в таком случае, [2x3] встречается дважды, как и [2x3x5]. 23 мая 2022 в 21:28

3 ответа 3

2

Рекурсивный метод. В 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)

5
  • Спасибо за ответ! Можете пояснить, почему idx и omit у вас 0, 1 и что это вообще за значения?
    – Mahev
    24 мая 2022 в 3:47
  • Да, добавил пояснение
    – MBo
    24 мая 2022 в 4:58
  • Какое лаконичное решение! 24 мая 2022 в 21:00
  • Очень впечатляет. Не могу только врубиться, как вывести получившиеся комбинации? 25 мая 2022 в 9:26
  • @Laukhin Andrey Если нужны сами комбинации, а не произведение, то можно собирать использованные элементы arr[idx] в ещё один аргумент - строку или массив
    – MBo
    25 мая 2022 в 9:47
0

Так как массив простых упорядочен, можно обойтись без словаря. Массив [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);
};
0

Я понял ход ваших мыслей. Не понятно только, в каком месте и почему остановились.

Возьмем массив [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
  );
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.