寻找给定数组的每个(n-1)子集的乘积

Question

抱歉删除了原问题，以下是内容： 我们有一个包或者 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];

感谢您的选择。

- guirgis

---

存在不使用除法的O(N)解决方案：https://dev59.com/_3E85IYBdhLWcg3wpFEa - polygenelubricants

相关问题：https://dev59.com/JkXRa4cB1Zd3GeqPpBxQ - jfs

你好，是否可以将其扩展到数组的任何子集的情况？http://stackoverflow.com/questions/28804120/find-product-of-any-combination-of-elements-from-a-list/28804230?noredirect=1#comment45882003_28804230 - meta_warrior

Answer 1

如果集合非常大，可能更方便的做法是：

• 先计算所有元素的乘积P
• 对于每个元素x，通过P / x 得到一个(n-1)次乘积

如果集合中包含零（即P=0或x=0），必须将其作为特殊情况进行处理。 编辑：这里提供了Scheme语言的解决方案，考虑了andand的答案。我是一个完全的初学者，请有人帮我改进以下代码（使其更加高效、易读，并符合Lisp的风格）。（欢迎编辑我的回答。）

#!/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)))

- Federico A. Ramponi

---

我了解你的想法，我的问题是特殊情况（零元素），那么我该怎么办？我需要考虑不同的问题吗？但是如果集合包含许多零元素会发生什么？我认为我们需要一个适用于所有值的通用解决方案。 - guirgis

@guirgis - 集合是一组不同元素的集合。它只能有任何特定元素的一个实例。如果它可以包含多个特定元素的实例，则为多重集（或袋）。如果您有一个带有多个零的袋子，则结果是微不足道的-请考虑一下。 - tvanfosson

我认为@Federico的解决方案是通用的，并适用于您问题中涵盖的所有值。请记住，如果您有一组整数，则0只能是该集合的成员一次；一个集合不能包含多个0元素。 - High Performance Mark

@guirgis - 处理带有零的集合最明显的方法是在遇到一个零时将所有其他结果标记为零，并继续构建产品而不考虑该元素 - 即，退化到仅计算省略单个零值的子集的一个子集乘积的特殊情况。 - tvanfosson

首先，我很抱歉误用了“Set”这个词，我应该使用“bag”或“array”。 其次，感谢您的想法，我正在努力理解它。 - guirgis

哦，如果袋子里包含多个零，则所有子集的乘积都将是“零”。 如果它包含一个零，则除了零元素之一的子集将全部为零，而零元素的子集将是其余元素的乘积。 感谢tvanfosson和所有人的提示，尽管这让我感到有点愚蠢。 - guirgis

Answer 2

需要明确考虑以下三种情况：

1) 没有零: 预先计算所有元素的乘积，并从该乘积中除去所需的集合元素。

2) 一个零: 预先计算非零元素的乘积。除了删除单个零元素时，答案始终为0，否则为预先计算的乘积。

3) 多个零: 答案总是0。

这假设您拥有一个可以容纳产品的数据类型...也就是说，您需要小心，以确保您的产品不会超过用于存储它的类型的最大值。

对于实际实现，请始终预先计算非零元素的乘积，并跟踪其中有多少个零。如果“集”是动态的（其值发生变化），则需要更新乘积和零数。在要求特定子集积时，请考虑各种情况并采取相应措施。

- andand

---

比代码版本更易读，非常详细。 - Matthieu M.

Answer 3

Set product = 1;
for item in set:
   if item index == argument index
      ignore
   else
      product *= item

如果我理解您的问题，这是一个微不足道的解决方案。在任何编程语言中都应该很容易实现。

- Stefan Kendall

---

你理解我的意思了，你的算法完全正确，但问题在于要计算所有子集的复杂度将为O(n^2)，我们正在寻找最优解决方案。 - guirgis

啊。你没有要求最优解 :) - Stefan Kendall

Answer 4

你可以使用 O(1) 的额外空间（不包括 O(N) 的输出数组），甚至不使用除法，在 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]"

参见

• 面试题：给定一个数字数组，返回所有其他数字的乘积数组（不使用除法）

- polygenelubricants

Answer 5

假设您可以使用Python：

您可以使用{{link1：itertools模块中的combinations方法}}来惰性生成所需集合的各种子集。一旦您拥有了它，就可以使用{{link2：reduce}}和{{link3：operator.mul}}来生成每个子集的乘积。

- Hank Gay

---

谢谢Hank，很漂亮的实现，但我觉得我有点需要算法而不是实现。 - guirgis