A (perhaps slightly) original solution to a problem involving multiplying elements of a vector

[Paul]

A standard problem involves transforming a vector of ints by replacing
the ith component by the product of all the entries apart from the ith
component. (I assume the mathematicians' convention that the product
of an empty collection is 1).
Naive attempts can be bugged for the case where the vector has a zero.
Below is my solution with accompanying tests. It seems to work and
I'd be interested to see feedback. It seems to tackle directly
the root of the difficulty by introducing a new type of multiplication
which still retains the necessary information when zero is encountered.

// Task is to transform a vector so that each entry is the multiple of all the other
// entries
#include <iostream>
#include <vector>

// A struct to handle multiplication which doesn't lose the
// information when zero is encountered.
struct intMult{
intMult(int x = 1) : underlying(x){}
int underlying;
int numZeros = underlying == 0; // Number of zeros that have been encountered in the multiplication
intMult operator * (int y)
{
if(y)
underlying *= y;
else ++numZeros;

return *this;

}

intMult& operator *= (int y)
{
*this = *this * y;
return *this;
}
};

void multiplyInVector(std::vector<int>& vec)
{
intMult x;
for(int i = 0; i < vec.size(); ++i)
x *= vec[i];

switch(x.numZeros)
{
case 0:
for(int i = 0; i < vec.size(); ++i)
vec[i] = x.underlying / vec[i];

return;

case 1:
for(int i = 0; i < vec.size(); ++i)
if(!vec[i])
vec[i] = x.underlying;
else
vec[i] = 0;
return;

default:
vec = std::vector<int>(vec.size());

}
}

std::ostream& operator<< (std::ostream& ofs, const std::vector<int>& vec)
{
ofs << "Am printing a vector \n";
for(int i = 0; i < vec.size(); ++i)
ofs << vec[i] << " ";

ofs << "\n";
return ofs;
}

int main()
{
std::vector<int> x;
std::vector<int> y{0};
std::vector<int> z {-1};
std::vector<int> a {-5, -4, 3, 5, 7};
std::vector<int> b {-5, 0, 3, 5, 2};
std::vector<int> c {-5, 0, 3, 1, 0};
std::vector<int> e {-5, 0, 0, 0 , 1, 2};
multiplyInVector(x);
multiplyInVector(y);
multiplyInVector(z);
multiplyInVector(a);
multiplyInVector(b);
multiplyInVector(c);
multiplyInVector(e);
std::cout << x << y << z << a << b << c << e;
}

[Alf P. Steinbach]

On 28.10.2018 14:24, Paul wrote:
> A standard problem involves transforming a vector of ints by replacing
> the ith component by the product of all the entries apart from the ith
> component. (I assume the mathematicians' convention that the product
> of an empty collection is 1).

Those numbers will exceed the number of range of C++ integers pretty quick.

> Naive attempts can be bugged for the case where the vector has a zero.
> Below is my solution with accompanying tests. It seems to work and
> I'd be interested to see feedback. It seems to tackle directly
> the root of the difficulty by introducing a new type of multiplication
> which still retains the necessary information when zero is encountered.

Well it's not exactly a new kind of multiplication. I used the principle
in 1986/87 for Dempster-Schafer evidence combination, together with the
corresponding division operation. Because DS has all these updates of
products of sets and set intersections (it's a combinatorial nightmare).

I was later told that it's well known to at least /some/ in mathematics,
but somewhat esoteric, off the beaten path.

I speculated at some point whether it could be generalized in a way as
complex numbers, because it's pretty similar to multiplication of
complex numbers in polar representation. That was a dead end, a hunch
that did not pan out. The operations do define a new kind of number-like
entities but these entities don't like addition much, then producing yet
new /kinds/ of entities, and so on, ad nauseam... :)

> // Task is to transform a vector so that each entry is the multiple of all the other
> // entries
> #include <iostream>
> #include <vector>
>
> // A struct to handle multiplication which doesn't lose the
> // information when zero is encountered.
> struct intMult{
> intMult(int x = 1) : underlying(x){}
> int underlying;
> int numZeros = underlying == 0; // Number of zeros that have been encountered in the multiplication
> intMult operator * (int y)
> {
> if(y)
> underlying *= y;
> else ++numZeros;
>
> return *this;
>
> }

You don't want to modify one of the operands of a multiplication.

As a member function make that `const` and don't modify.

But better make it a freestanding function, because that better supports
operands that convert implicitly to `intMult`.

> intMult& operator *= (int y)
> {
> *this = *this * y;
> return *this;
> }

Since the infix `*` modifies its left operand the assignment here is
redundant.

But this is where to put the code currently used for infix `*`.

Then express infix `*` in terms of `*=`.

> };



>
> void multiplyInVector(std::vector<int>& vec)
> {
> intMult x;
> for(int i = 0; i < vec.size(); ++i)
> x *= vec[i];
>
> switch(x.numZeros)
> {
> case 0:
> for(int i = 0; i < vec.size(); ++i)
> vec[i] = x.underlying / vec[i];
>
> return;
>
> case 1:
> for(int i = 0; i < vec.size(); ++i)
> if(!vec[i])
> vec[i] = x.underlying;
> else
> vec[i] = 0;
> return;
>
> default:
> vec = std::vector<int>(vec.size());
>
> }
> }

Better factor out the `/` and `/=` operations also.

> std::ostream& operator<< (std::ostream& ofs, const std::vector<int>& vec)
> {
> ofs << "Am printing a vector \n";
> for(int i = 0; i < vec.size(); ++i)
> ofs << vec[i] << " ";
>
> ofs << "\n";
> return ofs;
> }
>
> int main()
> {
> std::vector<int> x;
> std::vector<int> y{0};
> std::vector<int> z {-1};
> std::vector<int> a {-5, -4, 3, 5, 7};
> std::vector<int> b {-5, 0, 3, 5, 2};
> std::vector<int> c {-5, 0, 3, 1, 0};
> std::vector<int> e {-5, 0, 0, 0 , 1, 2};
> multiplyInVector(x);
> multiplyInVector(y);
> multiplyInVector(z);
> multiplyInVector(a);
> multiplyInVector(b);
> multiplyInVector(c);
> multiplyInVector(e);
> std::cout << x << y << z << a << b << c << e;
> }

Well. Maybe express that as a vector of vectors and use a loop?


Cheers!

- Alf

[Chris M. Thomasson]

[...]

I like it. Did something "kind of" similar wrt fractal iteration that
hit a zero, well, I just chose another root to follow. Counting the
zeros that destroy information is nice. I did another thing wrt avoiding
a division my zero. Just avoided it by setting the zero to a small
epsilon, and setting a bit to reflect that this special scenario has
actually occurred. The caller can detect this bit and act accordingly if
needed.

[Öö Tiib]

On Sunday, 28 October 2018 15:24:16 UTC+2, Paul wrote:
>
> for(int i = 0; i < vec.size(); ++i)
> x *= vec[i];

When you iterate over whole container then use range-based for.

for (int e : vec)
x *= e;

It is easier to read that way.
Or if you are after speed then use std::reduce of C++17 instead
of those loops.