Cartesian Product of Several Vectors

Cartesian product of several vectors

Not much of an algorithm...

for(vector<int>::const_iterator i1 = v1.begin(); i1 != v1.end(); ++i1)
    for(vector<int>::const_iterator i2 = v2.begin(); i2 != v2.end(); ++i2)
        for(vector<int>::const_iterator i3 = v3.begin(); i3 != v3.end(); ++i3)
            for(vector<int>::const_iterator i4 = v4.begin(); i4 != v4.end(); ++i4)
                cout << "[" << *i1 << "," << *i2 << "," << *i3 << "," << *i4 << "]" << endl;

Cartesian product of multiple arrays in JavaScript

Here is a functional solution to the problem (without any mutable variable!) using reduce and flatten, provided by underscore.js:

function cartesianProductOf() {    return _.reduce(arguments, function(a, b) {        return _.flatten(_.map(a, function(x) {            return _.map(b, function(y) {                return x.concat([y]);            });        }), true);    }, [ [] ]);}
// [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]]console.log(cartesianProductOf([1, 2], [3, 4], ['a']));  

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore.js"></script>

Octave : Vectorized implementation of the cartesian product of two vectors

Broadcasting can also be applied to multiply multidimensional arrays:

 result  = a .* reshape (b, m, 1, n2);

How can I create cartesian product of vector of vectors?

First, I'll show you a recursive version.

// Cartesion product of vector of vectors

#include <vector>
#include <iostream>
#include <iterator>

// Types to hold vector-of-ints (Vi) and vector-of-vector-of-ints (Vvi)
typedef std::vector<int> Vi;
typedef std::vector<Vi> Vvi;

// Just for the sample -- populate the intput data set
Vvi build_input() {
   Vvi vvi;

   for(int i = 0; i < 3; i++) {
      Vi vi;
      for(int j = 0; j < 3; j++) {
         vi.push_back(i*10+j);
      }
      vvi.push_back(vi);
   }
   return vvi;
}

// just for the sample -- print the data sets
std::ostream&
operator<<(std::ostream& os, const Vi& vi)
{
  os << "(";
  std::copy(vi.begin(), vi.end(), std::ostream_iterator<int>(os, ", "));
  os << ")";
  return os;
}
std::ostream&
operator<<(std::ostream& os, const Vvi& vvi)
{
  os << "(\n";
  for(Vvi::const_iterator it = vvi.begin();
      it != vvi.end();
      it++) {
      os << "  " << *it << "\n";
  }
  os << ")";
  return os;
}

// recursive algorithm to to produce cart. prod.
// At any given moment, "me" points to some Vi in the middle of the
// input data set. 
//   for int i in *me:
//      add i to current result
//      recurse on next "me"
// 
void cart_product(
    Vvi& rvvi,  // final result
    Vi&  rvi,   // current result 
    Vvi::const_iterator me, // current input
    Vvi::const_iterator end) // final input
{
    if(me == end) {
        // terminal condition of the recursion. We no longer have
        // any input vectors to manipulate. Add the current result (rvi)
        // to the total set of results (rvvvi).
        rvvi.push_back(rvi);
        return;
    }

    // need an easy name for my vector-of-ints
    const Vi& mevi = *me;
    for(Vi::const_iterator it = mevi.begin();
        it != mevi.end();
        it++) {
        // final rvi will look like "a, b, c, ME, d, e, f"
        // At the moment, rvi already has "a, b, c"
        rvi.push_back(*it);  // add ME
        cart_product(rvvi, rvi, me+1, end); add "d, e, f"
        rvi.pop_back(); // clean ME off for next round
    }
}

// sample only, to drive the cart_product routine.
int main() {
  Vvi input(build_input());
  std::cout << input << "\n";

  Vvi output;
  Vi outputTemp;
  cart_product(output, outputTemp, input.begin(), input.end());
  std::cout << output << "\n";
}

Now, I'll show you the recursive iterative version that I shamelessly stole from @John :

The rest of the program is pretty much the same, only showing the cart_product function.

// Seems like you'd want a vector of iterators
// which iterate over your individual vector<int>s.
struct Digits {
    Vi::const_iterator begin;
    Vi::const_iterator end;
    Vi::const_iterator me;
};
typedef std::vector<Digits> Vd;
void cart_product(
    Vvi& out,  // final result
    Vvi& in)  // final result

{
    Vd vd;

    // Start all of the iterators at the beginning.
    for(Vvi::const_iterator it = in.begin();
        it != in.end();
        ++it) {
        Digits d = {(*it).begin(), (*it).end(), (*it).begin()};
        vd.push_back(d);
    }

    while(1) {

        // Construct your first product vector by pulling 
        // out the element of each vector via the iterator.
        Vi result;
        for(Vd::const_iterator it = vd.begin();
            it != vd.end();
            it++) {
            result.push_back(*(it->me));
        }
        out.push_back(result);

        // Increment the rightmost one, and repeat.

        // When you reach the end, reset that one to the beginning and
        // increment the next-to-last one. You can get the "next-to-last"
        // iterator by pulling it out of the neighboring element in your
        // vector of iterators.
        for(Vd::iterator it = vd.begin(); ; ) {
            // okay, I started at the left instead. sue me
            ++(it->me);
            if(it->me == it->end) {
                if(it+1 == vd.end()) {
                    // I'm the last digit, and I'm about to roll
                    return;
                } else {
                    // cascade
                    it->me = it->begin;
                    ++it;
                }
            } else {
                // normal
                break;
            }
        }
    }
}

How to get a cartesian-product of all pair from two vectors in numpy?

From a simpler understanding point of view, an assignment based would make sense. Hence -

dt = np.result_type(A.dtype,B.dtype)
s = A.shape
C = np.empty((s[0],)+(2,)+s[1:],dtype=dt)
C[:,0] = A
C[:,1] = B

This could be simplified with a stacking operation for a one-liner -

C = np.stack((A,B),axis=1)

Bit of explanation on how these two methods solve it :

The one-liner is basically stacking A after B. In the first approach, the resultant is a 2 element ndarray along the second axis - s[0],)+(2,)+s[1:]. Thus, each element off A and off B are interleaved along that axis. This stacking operation has a NumPy builtin np.stack, which is the second method. Hence, these two are equivalent and solve our case.

And some verification :

Question is asking for - a new matrix C, in which every element (C[i]) is a matrix of shape (2, 3, 4, 5). Hence, C would be of shape (n,2,3,4,5). The stacking is along the second axis. Furthermore, from what I have understood, the question is asking for C[k][0] == A[k] for k=0..n and C[k][1] == B[k] for k=0..n. Let's prove that -

In [323]: n = 1000
     ...: A = np.random.rand(n, 3, 4, 5)
     ...: B = np.random.rand(n, 3, 4, 5)

In [324]: C = np.stack((A,B),axis=1)

In [325]: np.all([np.allclose(C[i][0],A[i]) for i in range(1000)])
Out[325]: True

In [326]: np.all([np.allclose(C[i][1],B[i]) for i in range(1000)])
Out[326]: True

Creating the Cartesian Product of a set of Vectors in Python?

For the specific case of a space of natural numbers, you want np.indices:

>>> np.indices((4, 4)).reshape(2,-1).T
array([[0, 0],
       [0, 1],
       [0, 2],
       [0, 3],
       [1, 0],
       [1, 1],
       [1, 2],
       [1, 3],
       [2, 0],
       [2, 1],
       [2, 2],
       [2, 3],
       [3, 0],
       [3, 1],
       [3, 2],
       [3, 3]])

(numpy actually outputs these in a grid, but you wanted a 1-D list of points, hence the .reshape)

Otherwise, what you're describing is not a powerset but a cartesian product

itertools.product(range(4), repeat=3)

Cartesian product of two vectors in Julia

Julia is usually very fast in nested loops, so if the they are working correctly for you, you should proabably check the performance maybe just stick with it.

Other option would be using repmat (this one is a little faster than using repeat):

[repmat(x,1,length(y))'[:] repmat(y,length(x),1)[:]]

Did some quick testing of both methods:

x=rand(1000)
y=rand(1000)

function withrepeat(x,y)
    [repeat(x, inner=[size(y,1)]) repeat(y, outer=[size(x,1)])]
end

function withrepmat(x,y)
    [repmat(x,1,length(y))'[:] repmat(y,length(x),1)[:]]
end

withrepeat(x,y)
elapsed time: 0.21556302 seconds (95986112 bytes allocated)

with repmat(x,y)
elapsed time: 0.075604488 seconds (56000560 bytes allocated)

Not sure why so much difference and I think there is room for improvement still.
Haven't tried the product function inside the Iterators.jl package.

Also a little bit more information here: https://groups.google.com/forum/#!topic/julia-users/dtl--SyFgwY

Hope this helps.

Tried a couple of nested loops and indeed is faster:

function withloops (x,y)
    leny=length(y)
    lenx=length(x)
    m=leny*lenx
    OUT = zeros(Float64, m,2)
    c=1
    for i = 1:lenx
        for j = 1:leny
            OUT[c,1] = x[i]
            OUT[c,2] = y[j]
            c+=1
        end
    end 
    return OUT
end

And, for the same rand(1000) for x and y.

withloops(x,y)
elapsed time: 0.011350679 seconds (16000128 bytes allocated)

Iterate over cartesian product of vectors

You can use the apply function to apply a function to each row of your data frame. Just replace "your function" with your actual function.

# example data
xs <- rnorm(10)
ys <- rnorm(10)    

apply(expand.grid(xs, ys), 1, FUN = function(x) {"your function"})

This is a very basic example. Here, the sum of both values in a row is calculated:

apply(expand.grid(xs, ys), 1, FUN = function(x) {x[1] + x[2]})

---

Here is a variant that uses named arguments (xs, ys) instead of indices (x[1], x[2]):

myfun <- function(xs, ys) xs + ys
arguments <- expand.grid(xs = rnorm(10), ys = rnorm(10))
apply(arguments, 1, function(x)do.call(myfun, as.list(x)))

---

Related Topics