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.
Programming Praxis 
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)Haskell also has
scanr. Here’s my golfed version: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; }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.
Here’s a solution in x86 assembly.
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.
<
pre>
array:
[5, 3, 4, 2, 6, 8]
partial_products(array):
[1152, 1920, 1440, 2880, 960, 720]
<
pre>
Here’s the output again, hopefully formatted properly this time:
In Ruby.
def partial_product(array) array.each_with_index.map do |_, i| array.rotate(i).drop(1).reduce(&:*) end endPython 3, in the REPL.
a simple java solution below ..
//package com.mayank.randompractice;
import java.util.*;
public class CodeDay1_IDZ {
}
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))))))@Bavier: Very nice!
My solution:
array1 = [5, 3, 4, 2, 6, 8]
array2 = []
length = len(array1)
for i in range(length):
print(array2)
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;
}