Skip to content

Tuples

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

Tuples[list,n]
    generates a list of all possible n-tuples of elements from list.
Tuples[{list1,list2,...}]
    generates a list of all possible tuples whose ith element is from listi.
Tuples[list,{n1,n2,...}]
    generates a list of all possible n1 x n2 x ... arrays of elements in list.

Examples

All examples below are verified against the current Mathilda build.

In[1]:= Tuples[{0, 1}, 3]
Out[1]= {{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}}

In[2]:= Tuples[{{a, b}, {1, 2, 3, 4}, {x}}]
Out[2]= {{a, 1, x}, {a, 2, x}, {a, 3, x}, {a, 4, x}, {b, 1, x}, {b, 2, x}, {b, 3, x}, {b, 4, x}}

In[3]:= Tuples[{a, b}, {2, 2}]
Out[3]= {{{a, a}, {a, a}}, {{a, a}, {a, b}}, {{a, a}, {b, a}}, {{a, a}, {b, b}}, {{a, b}, {a, a}}, {{a, b}, {a, b}}, {{a, b}, {b, a}}, {{a, b}, {b, b}}, {{b, a}, {a, a}}, {{b, a}, {a, b}}, {{b, a}, {b, a}}, {{b, a}, {b, b}}, {{b, b}, {a, a}}, {{b, b}, {a, b}}, {{b, b}, {b, a}}, {{b, b}, {b, b}}}

In[4]:= Tuples[f[x, y, z], 2]
Out[4]= {f[x, x], f[x, y], f[x, z], f[y, x], f[y, y], f[y, z], f[z, x], f[z, y], f[z, z]}

Implementation notes

Algorithm. builtin_tuples (in src/funcprog.c) enumerates the Cartesian product. Tuples[{l1, ..., lk}] takes one tuple from each list; Tuples[list, n] is the n-ary product of one list with itself; Tuples[list, {n1, ..., nd}] produces n1·…·nd-element tuples reshaped into a d-dimensional array. All three normalize to an array of source-list pointers and call the recursive tuples_rec.

tuples_rec is a straightforward odometer: it iterates the current list's elements in order, recursing one position deeper for each, and emits a completed tuple when all positions are filled. This yields lexicographic order with the last list varying fastest (the standard Cartesian-product order). The tuple head is taken from the input expression's head (so Tuples over non-List heads is structure-preserving). For the {n1,...,nd} form, each flat tuple is then folded into nested sublists by reshape_rec. Results grow in a geometrically resized Expr** buffer; an empty source list short-circuits to no output.

  • Protected.
  • The elements of list are treated as distinct.
  • The object list need not have head List. The head at each level in the arrays generated by Tuples will be the same as the head of list.

Attributes: Protected.

Implementation status

Stable — documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

References

Notes & additional examples

Worked examples

In[1]:= Tuples[{a, b}, 2]
Out[1]= {{a, a}, {a, b}, {b, a}, {b, b}}

The flat-product form Tuples[{list1, list2, ...}] takes one element from each list — here every pairing of a coin with a die face:

In[1]:= Tuples[{{1, 2}, {a, b, c}}]
Out[1]= {{1, a}, {1, b}, {1, c}, {2, a}, {2, b}, {2, c}}

Tuples enumerates the full sample space, so it composes with Select for combinatorial searches. The ways two dice sum to 7:

In[1]:= Select[Tuples[Range[6], 2], #[[1]] + #[[2]] == 7 &]
Out[1]= {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}}

The count of n-tuples from a k-element set is exactly k^n:

In[1]:= Length[Tuples[{a, b, c}, 4]]
Out[1]= 81

Notes

Tuples[list, n] builds the n-fold Cartesian power of list; Tuples[{l1, l2, ...}] builds the heterogeneous Cartesian product, one factor per list. Results are generated in odometer (lexicographic) order, with the last index varying fastest.