1
$\begingroup$

I have such a product example:

{
  "color": ["red", "blue"],
  "material": ["metal", "textile", "plastic"],
  "options": ["handle", "wire", "bt"],
  "textile": ["silk", "cotton"]
}

I need to know what algorithm can help me to produce all options possible for such product, f.e.:

{
  "color": "red",
  "material": "metal",
  "options": "handle",
  "textile": "cotton"
}

Each option can be single for a product.

Obviously, I don't want to use tons of for loops. It should be possible to easily add new options and new variations, f.e.:

{
  "color": ["red", "blue", "new"],
  "material": ["metal", "textile", "plastic", "new"],
  "options": ["handle", "wire", "bt", "new"],
  "textile": ["silk", "cotton", "new"],
  "newOption": ["new option]
}
$\endgroup$
  • $\begingroup$ Are you asking for code or algorithm in pseudocode? What if algorithm uses more loops? Tags like matrix are irrelevant to your question. $\endgroup$ – Evil Jan 29 '19 at 12:28
  • $\begingroup$ What you are looking for is an algorithm that computes the Cartesian product of your lists (though you could also see them as sets, I suppose). $\endgroup$ – dkaeae Jan 29 '19 at 12:44
  • $\begingroup$ @dkaeae Thanks for relevant answer :) $\endgroup$ – sorryiamnoob Jan 29 '19 at 13:22
1
$\begingroup$

The classical recursive algorithm to calculate the Cartesian product $A_1 \times \cdots \times A_n$ goes as follows:

  • If $n = 0$, return the empty tuple.
  • Otherwise, for every $x_1 \in A_1$ and $(x_2,\ldots,x_n) \in A_2 \times \cdots \times A_n$, output $(x_1,x_2,\ldots,x_n)$.

In the second step, you compute $A_2 \times \cdots \times A_n$ recursively.

You can convert this into an iterative algorithm. Suppose that $|A_i| = m_i$, and that the individual elements are $a_{ij}$. We count from $0$ to $m_1 \cdots m_n - 1$, and interpret each of these numbers as a mixed base number, involving the bases $m_1,\ldots,m_n$. We then convert the number into a tuple.

An alternative presentation of the iterative approach uses $n$ counters $c_1,\ldots,c_n$ counting from $0$ to $m_i-1$; when a counter reaches $m_i$, we reset it and all following counters to zero, and update the tuple accordingly.

Details of all these approaches left to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.