Here's a compact brute-force solution, so it has to perform `columns**rows`

tests, which is not good. I suspect that there's a backtracking algorithm that's generally more efficient, but in the worst case all possibilities may need to be checked.

```
from itertools import product
lst = [
[ 1, 2, 3],
[18, 20, 22],
[ 3, 14, 16],
[ 1, 3, 5],
[18, 2, 16],
]
nrows = len(lst)
m = min((t for t in product(*lst) if len(set(t)) == nrows), key=sum)
print(m)
```

**output**

```
(1, 18, 3, 5, 2)
```

Here's a faster version that uses a recursive generator instead of `itertools.product`

.

```
def select(data, seq):
if data:
for seq in select(data[:-1], seq):
for u in data[-1]:
if u not in seq:
yield seq + [u]
else:
yield seq
def solve(data):
return min(select(data, []), key=sum)
```

Here's a modified version of the recursive generator that sorts as it goes, but of course that's slower, and it consumes more RAM. If the input data is sorted it usually finds the minimum solution quite rapidly, but I can't figure out a foolproof way of getting it to stop when it's found the minimum selection.

```
def select(data, selected):
if data:
for selected in sorted(select(data[:-1], selected), key=sum):
for u in data[-1]:
if u not in selected:
yield selected + [u]
else:
yield selected
```

Here's some timing code that compares the speed of Maurice's and my solutions. It runs on Python 2 and Python 3. I get similar time results on Python 2.6 & Python 3.6 on my old 2GHz 32 bit machine running an oldish Debian derivative of Linux.

```
from __future__ import print_function, division
from timeit import Timer
from itertools import product
from random import seed, sample, randrange
n = randrange(0, 1 << 32)
print('seed', n)
seed(n)
def show(data):
indent = ' ' * 4
s = '\n'.join(['{0}{1},'.format(indent, row) for row in data])
print('[\n{0}\n]\n'.format(s))
def make_data(rows, cols):
maxn = rows * cols
nums = range(1, maxn)
return [sample(nums, cols) for _ in range(rows)]
def sort_data(data):
newdata = [sorted(row) for row in data]
newdata.sort(reverse=True, key=sum)
return newdata
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
def solve_Maurice(data):
result = None
for item in product(*data):
if len(item) > len(set(item)):
# Try the next combination if there are duplicates
continue
if result is None or sum(result) > sum(item):
result = item
return result
def solve_prodgen(data):
rows = len(data)
return min((t for t in product(*data) if len(set(t)) == rows), key=sum)
def select(data, seq):
if data:
for seq in select(data[:-1], seq):
for u in data[-1]:
if u not in seq:
yield seq + [u]
else:
yield seq
def solve_recgen(data):
return min(select(data, []), key=sum)
funcs = (
solve_Maurice,
solve_prodgen,
solve_recgen,
)
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
def verify():
for func in funcs:
fname = func.__name__
seq = func(data)
print('{0:14} {1}'.format(fname, seq))
print()
def time_test(loops, reps):
''' Print timing stats for all the functions '''
timings = []
for func in funcs:
fname = func.__name__
setup = 'from __main__ import data, ' + fname
cmd = fname + '(data)'
t = Timer(cmd, setup)
result = t.repeat(reps, loops)
result.sort()
timings.append((result, fname))
timings.sort()
for result, fname in timings:
print('{0:14} {1}'.format(fname, result))
rows, cols = 6, 4
print('Number of selections:', cols ** rows)
data = make_data(rows, cols)
data = sort_data(data)
show(data)
verify()
loops, reps = 100, 3
time_test(loops, reps)
```

**typical output**

```
seed 22290
Number of selections: 4096
[
[6, 11, 22, 23],
[9, 14, 17, 19],
[5, 9, 16, 22],
[5, 6, 9, 13],
[1, 3, 6, 22],
[4, 5, 6, 13],
]
solve_Maurice (11, 9, 5, 6, 1, 4)
solve_prodgen (11, 9, 5, 6, 1, 4)
solve_recgen [11, 9, 5, 6, 1, 4]
solve_recgen [0.5476037560001714, 0.549133045002236, 0.5647858490046929]
solve_prodgen [1.2500368960027117, 1.296529343999282, 1.3022710209988873]
solve_Maurice [1.485518219997175, 1.489505891004228, 1.784105566002836]
```

`min()`

.`SyntaxError: invalid token`

for integer literals with leading zeros.