Algorithm to get Cartesian product

Question

I have an array like [0,2,3,0,1] as input , and I need to find Cartesian product of {0}x{0,1,2}x{0,1,2,3}x{0}x{0,1}, more precisely I need to have output as following.

---

Input:

[0, 2, 3, 0, 1]

Output:

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 1]
[0, 0, 2, 0, 0]
[0, 0, 2, 0, 1]
[0, 0, 3, 0, 0]
[0, 0, 3, 0, 1]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 1]
[0, 1, 1, 0, 0]
[0, 1, 1, 0, 1]
[0, 1, 2, 0, 0]
[0, 1, 2, 0, 1]
[0, 1, 3, 0, 0]
[0, 1, 3, 0, 1]
[0, 2, 0, 0, 0]
[0, 2, 0, 0, 1]
[0, 2, 1, 0, 0]
[0, 2, 1, 0, 1]
[0, 2, 2, 0, 0]
[0, 2, 2, 0, 1]
[0, 2, 3, 0, 0]
[0, 2, 3, 0, 1]

I need a general algorithm. Any idea ? I would like to write it in c++. Thanks

Answer 1

Recursion seems like the simplest way to approach this problem, given that you may not know the length of the input vector. Something like this:

import java.util.ArrayList;
import java.util.Arrays;

public class Cartesian {

  public static void printCartesian(String head, ArrayList<Integer> array) {
    if (array.size() == 0) {
      System.out.println(head);
      return;
    }
    if (array.size() == 1) {
      for (int i = 0; i <= array.get(0); ++i) {
        System.out.println(head + i + "]");
      }
      return;
    }
    // assert array.size() > 1
    int a0 = array.get(0);
    ArrayList<Integer> array0 = new ArrayList<Integer>(array);
    array0.remove(0);
    for (int i = 0; i <= a0; ++i) {
      printCartesian(head + i + ", ", array0);
    }
  }

  public static void main(String[] args) {
    Integer[] input = { 0, 2, 3, 0, 1 };
    ArrayList<Integer> array = new ArrayList<Integer>(Arrays.asList(input));
    printCartesian("[", array);
  }
}

The initial call would be printCartesian("[", a) where a is an ArrayList containing the elements of your array in order. An extra if clause has to be added for size == 1 because otherwise one too many commas is printed.

Translating this to C++ data structures shouldn't be difficult.

Answer 2

A hard code solution would be:

for (int a1 : {0}) {
  for (int a2 : {0,1,2}) {
    for (int a3 : {0,1,2,3}) {
      for (int a4 : {0}) {
        for (int a5 : {0,1}) {
            do_job(a1, a2, a3, a4, a5);
        }
      }
    }
  }
}

You may use the following for a generic way (putting all as into vector):

bool increase(const std::vector<std::size_t>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] > v[index]) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

void iterate(const std::vector<std::size_t>& v)
{
    std::vector<std::size_t> it(v.size(), 0);

    do {
        do_job(it);
    } while (increase(v, it));
}

Live Demo

Answer 3

From your example, it seem like you want to count with mixed radix, and your input is the maximum digit value for each position.

A simple way is to use arithmetic coding, treating the max digit 0 positions specially. Here's pseudo-code for the case with no 0 max digits:

input radixes
let n_numbers = product_of radixes
for i = 0 to n_numbers-1 inclusive
    let n = i
    for digit_pos = 0 to number-of-radixes-1
        output n mod radix[digit_pos]
        let n = n div radix[digit_pos]
    output newline

I leave the treatment of 0 as max digit in a position, as an exercise. :)

---

I can't recall any particularly relevant support for this in the C++ standard library. I.e. it's mostly a language-independent question that has nothing to do with C++, nothing to do with permutations, and nothing to do with arrays. Provided my interpretation of it is correct: it would have been better it the problem was described also with words, not just an example.