Partial Products Of An Array

October 20, 2017

Our algorithm is to create two arrays, left and right, each containing the product of all the elements to the left (or right) of the current element, respectively. For instance, if the input array is (1 2 3 4 5), left is (1 1 2 6 24) and right is (120 60 20 5 1). Then the desired output is the pair-wise product of the left and right arrays:

(define (f xs)
  (let* ((len (length xs))
         (left (take len (scanl * 1 xs)))
         (right (reverse (take len (scanl * 1 (reverse xs))))))
    (map * left right)))

We make use of the convenient scanl function from Haskell, which applies an operator successively to the elements of a list, accumulating partial results as it goes:

(define (scanl op base xs)
  (let loop ((xs xs) (base base) (zs (list base)))
    (if (null? xs) (reverse zs)
      (let ((z (op (car xs) base)))
        (loop (cdr xs) z (cons z zs))))))

For instance, (scanl * 1 '(1 2 3 4 5)) returns the list (1 1 2 6 24 120). Here are some examples:

> (f '(1 2 3 4 5))
(120 60 40 30 24)
> (f '(5 3 4 2 6 8))
(1152 1920 1440 2880 960 720)

You can run the program at https://ideone.com/fdr3oo.

Advertisements

Pages: 1 2

13 Responses to “Partial Products Of An Array”

  1. chaw said

    The algorithm is essentially the same as in the sample solution,
    but this implementation exercises a few SRFI 133 procedures on
    vectors.

    (import (scheme base)
            (scheme write)
            (org eip10 srfi 133)) ; local copy of SRFI 133 sample implementation
    
    (define input-101 '#(5 3 4 2 6 8))
    (define output-101 '#(1152 1920 1440 2880 960 720))
    
    ;; Theta(n) time and space.
    (define (other-products vec)
      (let ((evec (vector-append '#(1) vec '#(1)))) ; extend vec with 1 at each end
        (let ((lr-chain (vector-cumulate * 1 evec))
              (rl-chain (vector-reverse-copy
                         (vector-cumulate * 1 (vector-reverse-copy evec)))))
          (vector-unfold (lambda (idx)
                           (* (vector-ref lr-chain idx)
                              (vector-ref rl-chain (+ idx 2))))
                         (vector-length vec)))))
    
    (display (equal? output-101 (other-products input-101)))
    (newline)
    
  2. Haskell also has scanr. Here’s my golfed version:

    module Main where
    
    ppa :: Num a => [a] -> [a]
    ppa = zipWith (*) <$> init . scanl (*) 1 <*> tail . scanr (*) 1
    
    main :: IO ()
    main = print . ppa $ [1 .. 5 :: Int]
    
  3. isaac said

    a c solution by a noob:

    #include <stdio.h>
    
    int main() {
    
        int input_array[] = {5,3,4,2,6,8};
        int last_index = (sizeof(input_array) / sizeof(int)) - 1;
        int output_array[last_index + 1];
        int products_array[last_index + 2];
        products_array[last_index + 1] = 1;
        int i;
        int products = 1;
        for(i = last_index; i > 0; i--) {
            products = products * input_array[i];
            products_array[i] = products;
        }
        output_array[0] = products_array[1];
        products = 1;
        for(i = 1; i <= last_index; i++) {
            products = products * input_array[i - 1];
            output_array[i] = products * products_array[i + 1];
        }
        output_array[last_index] = products;
        for(i = 0; i <= last_index; i++) {
            printf("%d\t", output_array[i]);
        }
     
    return 0;
    output_array[last_index] = products;
        for(i = 0; i <= last_index; i++) {
            printf("%d\t", output_array[i]);
        }
     
    return 0;
    }
    
  4. Globules said

    Another Haskell solution that (it turns out) is almost identical to Graham Enos’ version. A minor difference is that I don’t use the init function, since tail will ensure that the second list is one element shorter than the first, so zipwith will never look at the last element of the first list.

    partProd :: Num a => [a] -> [a]
    partProd xs = zipWith (*) (scanl (*) 1 xs) (tail $ scanr (*) 1 xs)
    
    main :: IO ()
    main = do
      print $ partProd []
      print $ partProd [5]
      print $ partProd [5, 3]
      print $ partProd [5, 3, 4, 2, 6, 8]
    
    $ ./partprod 
    []
    [1]
    [3,5]
    [1152,1920,1440,2880,960,720]
    
  5. Daniel said

    Here’s a solution in x86 assembly.

    /* partial_products.s */
    
    .section .text
    
    .globl partial_products
    .type partial_products,@function
    
    # void partial_products(int* input, int* output, int n);
    partial_products:
      pushl %ebp
      movl %esp, %ebp
    
      # %ebp offsets
      .equ input, 8
      .equ output, 12
      .equ n, 16
    
      # Save non-volatile registers
      pushl %ebx
      pushl %edi
      pushl %esi
    
      # create stack space for local variables
      movl $4, %eax # 4 bytes per int
      imull n(%ebp), %eax # n elements per array
      imull $2, %eax # 2 local arrays
      subl %eax, %esp
      # Save the amount of stack space
      pushl %eax
      
      movl input(%ebp), %eax # start of input array
    
      # Calculate cumulative products, while iterating forward
      movl %esp, %ebx # start of forward array
      addl $4, %ebx # (one element into the stack)
      movl $0, %ecx # array index
      movl $1, %edx # cumulative product
    loop1:
      cmpl %ecx, n(%ebp)
      je loop1_end
      movl (%eax, %ecx, 4), %edi # array value
      imull %edi, %edx
      movl %edx, (%ebx, %ecx, 4)
      incl %ecx
      jmp loop1
    loop1_end:
    
      # Calculate cumulative products, while iterating backward
      # Shift %ebx pointer to start of backward array
      # (past the end of the forward array)
      movl $4, %ecx # 4 bytes per int
      imull n(%ebp), %ecx # n elements per array
      addl %ecx, %ebx # start of backward array
    
      movl n(%ebp), %ecx # array index
      movl $1, %edx # cumulative product
    loop2:
      decl %ecx
      cmpl $-1, %ecx 
      je loop2_end
      movl (%eax, %ecx, 4), %edi # array value
      imull %edi, %edx
      movl %edx, (%ebx, %ecx, 4)
      jmp loop2
    loop2_end:
    
      # Calculate output by multiplying leftmost forward
      # array value by the rightmost backward array value.
      movl %esp, %eax # start of forward array
      addl $4, %eax # (one element into the stack)
      movl $4, %ebx # 4 bytes per int
      imull n(%ebp), %ebx # n elements per array
      addl %eax, %ebx # start of backward array
      movl $0, %ecx # array index
    loop3:
      cmpl %ecx, n(%ebp)
      je loop3_end
      movl (%ebx, %ecx, 4), %edx
     
      movl $1, %esi
      cmpl $0, %ecx
      je left_end
      imull -4(%eax, %ecx, 4), %esi
    left_end:
      movl n(%ebp), %edi
      decl %edi
      cmpl %edi, %ecx
      je right_end
      imull 4(%ebx, %ecx, 4), %esi 
    right_end:
      movl output(%ebp), %edi # start of output array
      movl %esi, (%edi, %ecx, 4) 
      incl %ecx
      jmp loop3
    loop3_end:
    
      # Ignore local variables
      popl %eax
      addl %eax, %esp
    
      # Restore non-volatile registers
      popl %esi
      popl %edi
      popl %ebx
    
      movl %ebp, %esp
      popl %ebp
      ret
    

    Here’s a C program that calls the function.

    /* main.c */
    
    #include <stdio.h>
    
    void partial_products(int*, int*, int);
    
    void print_array(int* array, int n) {
      printf("[");
      for (int i = 0; i < n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", array[i]);
      }
      printf("]");
    }
    
    int main(int argc, char* argv[]) {
      int array[] = {5, 3, 4, 2, 6, 8};
      int n = sizeof(array) / sizeof(int);
    
      printf("array:\n  ");
      print_array(array, n);
      printf("\n");
    
      int output[n];
      partial_products(array, output, n);
      printf("partial_products(array):\n  ");
      print_array(output, n);
      printf("\n");
    }
    

    Here’s example usage and output.

    $ as --32 -o partial_products.o partial_products.s
    $ gcc -m32 -o main partial_products.o main.c
    $ ./main
    

    <

    pre>
    array:
    [5, 3, 4, 2, 6, 8]
    partial_products(array):
    [1152, 1920, 1440, 2880, 960, 720]

    <

    pre>

  6. Daniel said

    Here’s the output again, hopefully formatted properly this time:

    array:
    [5, 3, 4, 2, 6, 8]
    partial_products(array):
    [1152, 1920, 1440, 2880, 960, 720]
    
  7. V said

    In Ruby.

      def partial_product(array)
        array.each_with_index.map do |_, i|
          array.rotate(i).drop(1).reduce(&:*)
        end
      end
    
  8. kernelbob said

    Python 3, in the REPL.

    ~$ python3
    Python 3.5.3 (default, May 31 2017, 00:43:27) 
    [GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
    Type "help", "copyright", "credits" or "license" for more information.
    >>> from functools import reduce
    >>> a = [5, 3, 4, 2, 6, 8]
    >>> run_prod = lambda a: reduce(lambda a, b: a + [b * a[-1]], a, [1])[:-1]
    >>> run_prod(a)
    [1, 5, 15, 60, 120, 720]
    >>> [a * b for (a, b) in zip(run_prod(a), run_prod(a[::-1])[::-1])]
    [1152, 1920, 1440, 2880, 960, 720]
    >>> 
    
  9. mj said

    a simple java solution below ..

    //package com.mayank.randompractice;
    import java.util.*;

    public class CodeDay1_IDZ {

    public static void main(String[] args) {
    
        int a[] = new int [] {5,3,4,2,6,8};
        int b[] = new int [a.length];
        int x=1;
    
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length;j++){
                if(i!=j){
                    x = a[j]*x;
                }
    
            }
            b[i]=x;
            x=1;
        }
    
        System.out.println(Arrays.toString(b));
    }
    

    }

  10. bavier said

    Simple recursive solution in Guile Scheme:

    (use-modules (ice-9 match))
    
    (define (partial-products lst)
      (match lst
        (() (list))
        ((head tail ...)
         (cons (apply * tail)
               (map (lambda (e) (* head e))
                    (partial-products tail))))))
    
  11. programmingpraxis said

    @Bavier: Very nice!

  12. David Liu said

    My solution:

    array1 = [5, 3, 4, 2, 6, 8]
    array2 = []

    length = len(array1)

    for i in range(length):

    val = 0
    
    for j in range(length):
        if i != j:
            if val == 0:
                val = array1[j]
            else:
                val = val*array1[j]
    
    array2.append(val)
    

    print(array2)

  13. Jim Li Chong said


    import java.util.*;
    class partial_array_product {
    public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    System.out.println("Please enter the size of your array : ");
    int k = in.nextInt(), arr[] = new int[k], product = 1;

        System.out.println("Please enter elements of the array : ");
        for(int i  = 0; i < arr.length; i++) arr[i] = in.nextInt();
    
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++)
                if (arr[j] != arr[i]) product *= arr[j];
            System.out.println("The product excluding " + arr[i]
                + " is " + product);
            product = 1;
        }
    
    }
    

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: