Cartesian product of two or more lists

From Fōrmulæ dictionary
Jump to: navigation, search

This page is the answer to the task Cartesian product of two or more lists in the Rosetta Code.

Description (from Rosetta Code)

Task

Show one or more idiomatic ways of generating the Cartesian product of two arbitrary lists in your language.

Demonstrate that your function/method correctly returns:

{1, 2} × {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4)}

and, in contrast:

{3, 4} × {1, 2} = {(3, 1), (3, 2), (4, 1), (4, 2)}

Also demonstrate, using your function/method, that the product of an empty list with any other list is empty.

{1, 2} × {} = {}

{} × {1, 2} = {}

For extra credit, show or write a function returning the n-ary product of an arbitrary number of lists, each of arbitrary length. Your function might, for example, accept a single argument which is itself a list of lists, and return the n-ary product of those lists.

Use your n-ary Cartesian product function to show the following products:

{1776, 1789} × {7, 12} × {4, 14, 23} × {0, 1}

{1, 2, 3} × {30} × {500, 100}

{1, 2, 3} × {} × {500, 100}

Program

No programs needed. Cartesian product is intrinsically supported in Fōrmulæ.

Case 1. No commutativity

CartesianProductCase1.png

Case 2. With an empty list

CartesianProductCase2.png

Case 3. Extra credit. n-ary cartesian product

CartesianProductCase3.png

CartesianProductCase4.png

CartesianProductCase5.png

Additional case. Cartesian product exponentiation

In a n-ary cartesian product of lists, the lists are the same, then the cartesian product exponentiation can be used:

CartesianProductCase6.png