Finding the product of each of the (n-1) subsets of a given array

Question

I'm sorry for deleting the original question, here it is: We have a bag or an array of n integers, we need to find the product of each of the (n-1) subsets. e.g:

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

After discussions, we need to take care of the three cases and they are illustrated in the following:

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];

Thanks.

Answer 1

If the set is very large, it may be convenient to:

• compute the product P of all the elements beforehand, and then
• for each element x, obtain a (n-1) product as P/x

If the set contains zero (i.e. P=0, x=0), you must deal with it as a special case.

EDIT. Here is a solution in Scheme, taking into account andand's answer. I'm a complete beginner - can someone help me improve the following code (make it more efficient, more readable, more lisp-ish)? (Feel free to edit my answer.)

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

Answer 2

You need to explicitly consider the three cases:

1) No zeros: Precompute the product of all of the elements and divide out the desired set element from that product.

2) One zero: Precompute the product of the non-zero elements. The answer is always 0 except when you remove the single zero element, in which case it's the precomputed product.

3) More than one zero: The answer is always 0.

This assumes that you have a data type that can contain the products... that is, you need to be careful that your product doesn't exceed the maximum value of the type you're using to store it.

For the actual implementation, always precompute the product of the non-zero elements and keep track of how many zeros there are. If the "set" is dynamic (its values change) you'll need to update the product and the zero count. When asked for a particular subset product, consider the various cases and act accordingly.

Answer 3

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

If I understand your question, this is the trivial solution. It should be easy to implement in any programming language.

Answer 4

You can solve this in O(N), using O(1) additional space (not counting the O(N) output array), without even using division. Here's the algorithm in 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]"

---

See also

• Interview Q: given an array of numbers, return array of products of all other numbers (no division)

Answer 5

Assuming you can use Python:

You can use the combinations method from the itertools module to lazily generate the various subsets of the set in question. Once you have that, you can use reduce and operator.mul to generate the product of each one.