CODEWITHSUNDEEP
algorithmcombinations
user2502761
user2502761

Reputation: 563

Get all the products of an array

How can I calculate all the products of an array and return two products for each combination?

Array: 

[2, 2, 3, 4]

Output:

1, 2*2*3*4
2, 2*3*4
2*2, 3*4
2*2*3, 4
2*2*4, 3
2*3, 2*4

I hope my output contains all of them. Any ideas, pseudocode, code are welcomed.

Upvotes: 0

Views: 110

Answers (1)

user1196549
user1196549

Reputation:

As some of the factors are repeated, you need to take their multiplicities into account to avoid repeating some products.

Sort the array if needed and count the multiplicities (consecutive equal values).

Then, assuming k distinct values with respective multiplicities Mk, you will emulate k nested loops, each from 0 to Mk inclusive. For this emulation, consider an array of counters all initialized to 0. Then increment the first counter, and when it reaches its maximum value, reset it and carry to the next counter. If the next counter reaches its maximum, reset it and carry to the next...

Use these counters as exponents of the factors and compute the product. The second number is the product of all factors divided by the first number.

E.g.

Values:         2, 3, 4
Multiplicities: 2, 1, 1

Counters:
  000
  100
  200
  010
  110
  210
  001
  101
  201
  011
  111
  211

First numbers:
  1
  2
  2²
  3
  2.3
  2²3
  4
  2.4
  2²4
  3.4
  2.3.4
  2²3.4

Second numbers = 2²3.4 / First numbers

The total number of product pairs equals the product of the multiplicities plus one, (M1+1)(M2+1)...(Mk+1).

Upvotes: 2

Related Questions