Two sum: Difference between revisions
→{{header|Python}}: added a concatMap version, generating fewer candidates
m (→version 2: highlighted the negative in the REXX section header.) |
(→{{header|Python}}: added a concatMap version, generating fewer candidates) |
||
Line 1,620:
# GENERIC -------------------------------------------------
# fst :: (a, b) -> a
def fst(tpl):
return tpl[0]
# snd :: (a, b) -> b
def snd(tpl):
return tpl[1]
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>[(1, 3), (2, 5)]
[]</pre>
or, a little more parsimoniously (not generating the entire cartesian product), in terms of '''concatMap''':
<lang python>import itertools
# sumTwo :: Int -> [Int] -> [(Int, Int)]
def sumTwo(n, xs):
ixs = list(enumerate(xs))
return concatMap(
lambda ix: concatMap(
lambda jy: [(fst(ix), fst(jy))] if (
n == snd(ix) + snd(jy)
) else []
)(ixs[fst(ix):]))(
ixs
)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
for n in [21, 25]:
print (
sumTwo(n, [0, 2, 11, 19, 90, 10])
)
# GENERIC -------------------------------------------------
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
return lambda xs: list(
itertools.chain.from_iterable(
map(f, xs)
)
)
| |||