Cartesian product of two or more lists: Difference between revisions
Content added Content deleted
(→{{header|Python}}: Added a compact native approach (no imports), in a more mathematical idiom, demonstrating use of Python for functional programming) |
|||
Line 2,045:
=={{header|Python}}==
===Using itertools
<lang python>import itertools
Line 2,103:
(3, 30, 100)]
((1, 2, 3), (), (500, 100)) =>
[]</pre>
===Using the 'Applicative' abstraction===
This task calls for alternative approaches to defining cartesian products, and one particularly compact alternative route to a native cartesian product (in a more mathematically reasoned idiom of programming) is through the Applicative abstraction [[wp:Applicative_functor|Applicative Functor]], which is slightly more general than the possibly better known '''monad''' structure. Applicative functions are provided off-the-shelf by languages like Agda, Idris, Haskell and Scala, and can usefully be implemented in any language, including Python, which supports higher-order functions.
If we write ourselves a re-usable Python '''ap''' function for the case of lists (applicative functions for other 'data containers' can also be written – this one applies a list of functions to a list of values):
<lang python># ap (<*>) :: [(a -> b)] -> [a] -> [b]
def ap(fs):
return lambda xs: foldl(
lambda a: lambda f: a + foldl(
lambda a: lambda x: a + [f(x)])([])(xs)
)([])(fs)</lang>
then one simple use of it will be to define the cartesian product of two lists (of possibly different type) as:
<lang python>ap(map(Tuple, xs))</lang>
where Tuple is a constructor, and xs is bound to the first of two lists. The returned value is a function which can be applied to a second list.
For an nAry product, we can then use a '''fold''' (catamorphism) to lift the basic function over two lists ''cartesianProduct :: [a] -> [b] -> [(a, b)]'' to a function over a list of lists:
<lang python># nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)]
def nAryCartProd(xxs):
return foldl1(cartesianProduct)(
xxs
)</lang>
For example:
<lang python># Two lists -> list of tuples
# cartesianProduct :: [a] -> [b] -> [(a, b)]
def cartesianProduct(xs):
return ap(map(Tuple, xs))
# List of lists -> list of tuples
# nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)]
def nAryCartProd(xxs):
return foldl1(cartesianProduct)(
xxs
)
# main :: IO ()
def main():
# Product of lists of different types
print (
'Product of two lists of different types:'
)
print(
cartesianProduct(['a', 'b', 'c'])(
[1, 2]
)
)
# TESTS OF PRODUCTS OF TWO LISTS
print(
'\nSpecified tests of products of two lists:'
)
print(
cartesianProduct([1, 2])([3, 4]),
' <--> ',
cartesianProduct([3, 4])([1, 2])
)
print (
cartesianProduct([1, 2])([]),
' <--> ',
cartesianProduct([])([1, 2])
)
# TESTS OF N-ARY CARTESIAN PRODUCTS
print('\nSpecified tests of nAry products:')
for xs in nAryCartProd([[1776, 1789], [7, 12], [4, 14, 23], [0, 1]]):
print(xs)
for xs in (
map_(nAryCartProd)(
[
[[1, 2, 3], [30], [500, 100]],
[[1, 2, 3], [], [500, 100]]
]
)
):
print(
xs
)
# GENERIC -------------------------------------------------
# Applicative function for lists
# ap (<*>) :: [(a -> b)] -> [a] -> [b]
def ap(fs):
return lambda xs: foldl(
lambda a: lambda f: a + foldl(
lambda a: lambda x: a + [f(x)])([])(xs)
)([])(fs)
# foldl :: (a -> b -> a) -> a -> [b] -> a
def foldl(f):
def go(v, xs):
a = v
for x in xs:
a = f(a)(x)
return a
return lambda acc: lambda xs: go(acc, xs)
# foldl1 :: (a -> a -> a) -> [a] -> a
def foldl1(f):
return lambda xs: foldl(f)(xs[0])(
xs[1:]
) if xs else None
# map :: (a -> b) -> [a] -> [b]
def map_(f):
return lambda xs: list(map(f, xs))
# Tuple :: a -> b -> (a, b)
def Tuple(x):
return lambda y: (
x + (y,)
) if tuple is type(x) else (x, y)
# TEST ----------------------------------------------------
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>Product of two lists of different types:
[('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2)]
Specified tests of products of two lists:
[(1, 3), (1, 4), (2, 3), (2, 4)] <--> [(3, 1), (3, 2), (4, 1), (4, 2)]
[] <--> []
Specified tests of nAry products:
(1776, 7, 4, 0)
(1776, 7, 4, 1)
(1776, 7, 14, 0)
(1776, 7, 14, 1)
(1776, 7, 23, 0)
(1776, 7, 23, 1)
(1776, 12, 4, 0)
(1776, 12, 4, 1)
(1776, 12, 14, 0)
(1776, 12, 14, 1)
(1776, 12, 23, 0)
(1776, 12, 23, 1)
(1789, 7, 4, 0)
(1789, 7, 4, 1)
(1789, 7, 14, 0)
(1789, 7, 14, 1)
(1789, 7, 23, 0)
(1789, 7, 23, 1)
(1789, 12, 4, 0)
(1789, 12, 4, 1)
(1789, 12, 14, 0)
(1789, 12, 14, 1)
(1789, 12, 23, 0)
(1789, 12, 23, 1)
[(1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)]
[]</pre>
=={{header|R}}==
| |||