Нахождение произведения каждого из (n-1) подмножеств данного массива - PullRequest
Новая
       11

Нахождение произведения каждого из (n-1) подмножеств данного массива

7 голосов
/ 19 апреля 2010

Прошу прощения за удаление исходного вопроса, вот он: У нас есть мешок или массив из n целых чисел, нам нужно найти произведение каждого из (n-1) подмножеств. например:

S = {1, 0, 3, 6}
ps [1] = 0 * 3 * 6 = 0;
ps [2] = 1 * 3 * 6 = 18; и т.д.

После обсуждений нам нужно позаботиться о трех случаях, и они проиллюстрированы следующим образом: 

1. S is a set (contains one zero element)
  for i=1 to n
    if s[i]=0
      sp[i] = s[1] * s[2] * ...* s[i-1] * s[i+1] *.....*s[n]
    else
      sp[i] = 0;

2. S is a bag (contains more than one zero element) 
  for i=1 to n
      sp[i] = 0;

3. S is a set (contains no zero elements)
   product = 1
   for i=1 to n
     product *= s[i];
   for i=1 to n
     sp[i] = product / s[i];

Спасибо.

Ответы [ 5 ]

13 голосов
/ 19 апреля 2010

Если набор очень большой, может быть удобно:

  • предварительно вычисляет произведение P всех элементов, а затем
  • для каждого элемента x, получить (n-1) произведение как P / x

Если набор содержит ноль (то есть P = 0, x = 0), вы должны рассматривать его как особый случай.

EDIT . Вот решение в Схеме с учетом andand ответа. Я начинающий - может ли кто-нибудь помочь мне улучшить следующий код (сделать его более эффективным, более читабельным, более понятным)? (Не стесняйтесь редактировать мой ответ.) 

#!/usr/bin/env guile !#
(use-modules (ice-9 pretty-print))

(define (count-zeros l)
    (cond ((null? l) 0)
          ((= 0 (car l)) (+ 1 (count-zeros (cdr l))))
          (else (count-zeros (cdr l)))))

(define (non-zero-product l)
    (define (non-zero-product-loop l product)
        (cond ((null? l) product)
              ((= 0 (car l)) (non-zero-product-loop (cdr l) product))
              (else (non-zero-product-loop (cdr l) (* (car l) product)))))
    (non-zero-product-loop l 1))

(define (n-1-products l)
    (let ((nzeros (count-zeros l)))
         (cond ((> nzeros 1)
                   (map (lambda (x) 0) l))
               ((= 1 nzeros)
                   (map (lambda (x) (if (= 0 x) (non-zero-product l) 0)) l))
               (else 
                   (map (lambda (x) (/ (non-zero-product l) x)) l)))))

(pretty-print (n-1-products '(1 2 3 4 5)))
(pretty-print (n-1-products '(0 1 2 3 4)))
(pretty-print (n-1-products '(0 1 2 3 0)))
11 голосов
/ 19 апреля 2010

Вам необходимо подробно рассмотреть три случая:

1) Без нулей: Предварительно вычислить произведение всех элементов и отделить требуемый элемент набора от этого произведения.

2) Один ноль : Предварительное вычисление произведения ненулевых элементов. Ответ всегда равен 0, за исключением случаев, когда вы удаляете один нулевой элемент, и в этом случае это предварительно вычисленный продукт.

3) Более одного нуля: Ответ всегда равен 0.

Это предполагает, что у вас есть тип данных, который может содержать продукты ... то есть вы должны быть осторожны, чтобы ваш продукт не превышал максимальное значение типа, который вы используете для его хранения.

Для фактической реализации всегда предварительно вычисляйте произведение ненулевых элементов и отслеживайте, сколько существует нулей. Если «набор» является динамическим (его значения меняются), вам нужно обновить продукт и счетчик нулей. Когда вас спросят о конкретном подмножестве продуктов, рассмотрите различные случаи и действуйте соответственно.

2 голосов
/ 22 апреля 2010

Вы можете решить это за O(N), используя O(1) дополнительное пространство (не считая выходной массив O(N)), даже без использования деления. Вот алгоритм на Java. 

static int[] products(int... nums) {
    final int N = nums.length;
    int[] prods = new int[N];
    int pi = 1;
    for (int i = 0; i < N; i++) {
        prods[i] = pi;
        pi *= nums[i];
    }
    int pj = 1;
    for (int j = N-1; j >= 0; j--) {
        prods[j] *= pj;
        pj *= nums[j];
    }
    return prods;
}

//...
System.out.println(
   Arrays.toString(products(1, 2, 3, 4, 5))
); // prints "[120, 60, 40, 30, 24]"

Смотри также

2 голосов
/ 19 апреля 2010 
Set product = 1;
for item in set:
   if item index == argument index
      ignore
   else
      product *= item

Если я понимаю ваш вопрос, это тривиальное решение. Это должно быть легко реализовано на любом языке программирования.

0 голосов
/ 19 апреля 2010

Если вы можете использовать Python:

Вы можете использовать метод combinations из модуля itertools , чтобы лениво генерировать различные подмножества рассматриваемого набора. Получив это, вы можете использовать reduce и operator.mul для создания продукта каждого из них.

...