Source code for tryalgo.scalar

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Permute vector to minimize scalar product
jill-jênn vie et christoph dürr - 2014-2019
"""


# snip{
[docs]def min_scalar_prod(x, y): """Permute vector to minimize scalar product :param x: :param y: x, y are vectors of same size :returns: min sum x[i] * y[sigma[i]] over all permutations sigma :complexity: O(n log n) """ x1 = sorted(x) # make copies to preserve the input arguments y1 = sorted(y) return sum(x1[i] * y1[-i - 1] for i in range(len(x1)))
# snip}