Divide food to the poor equally! The problem

Through a terrible procastination accident you are reborn as Scrooge McDuck for a day. To make the most out of the situation you decide to give away food to the poor. Since you also are a mathematician you store the food in a vector v(1,2,3). 

You want to give each family approximately the same food. To make things simple each family has n members.  The task is to write a code to split the vector v into rows of length n where each row has the same amount of ''food''. 

Equality is measured by the standard deviation; how different the sum of each row (the food each family receives) is from the mean.

Input

Input should be an integer n and a vector v The length of v does not have to be divisible by n; zero pad it if that is the case.

Example

v = (4, 9, 3, 6, 19, 6, 9, 20, 9, 12, 19, 13, 7, 15)
n = 3


Should return

 4     6    19
 9     9    13
 3    20     7
 6     9    15
19    12     0


The sum of each row is 29,31,30,30,31, so the standard deviation is 0.748331 for n = 2. Note the presence of a 0 that we added.

The output

The code should output the standard deviation. You can also print the matrix but this is not a requirement.

The score

The winner is judged not by the shortest code, but by the sum of the standard deviations, given the test vector and n = 2, 3, and 23. e.g.

Score = your_func(2, foodvec) + your_func(3, foodvec) + your_func(23, foodvec)


Use the following vector to test http://pastebin.com/ybAYGHns and test for n=2,3,23. The final score is the sum of those three tests.
The vector is somewhat big since Scrooge has a lot of food saved up.
Python 3 using PyPy: 6.368014 + 0.701679 + 0.486916 = 7.556608

Optimal for n = 2

There are 1000 numbers, so we want to distribute the food to 500 families. If the food vector is sorted (food[1] &gt;= food[2] &gt;= ... &gt;= food[500]), then the minimal std is reached by giving the first family the food items food[1] and food[500], the second family food[2] and food[499], the third family food[3] and food[498], ...

I thought of a quite easy proof. Basically I expanded the product of the std, removed the terms that appear in each food partition, and proofed that the result is minimal. If someone wants a more detailed explanation, just ask me nice. 

Approximation for n > 2

I don't think, that there's a fast way of finding the optimal solution for n > 2. 

I start with an heuristic solution. I distribute the food items in sorted (descending) order to the family with the lowest food so far (only to such families, which have received less than n food items). 

Afterwards I improve the solution, by swapping 1 food item between a pair of families.
I use the N families with to lowest food and the N families with the most food so far. After all possible swaps, I choose the best swap, and call the local search recursively. 

The bigger the value of N is, the lower will be the std (but also the running time will be longer). I used N = 20 and when I can't find swap, I try again with N = 100. PyPy finishes all 3 test cases in less than 8 minutes. 

Code

def findSmallestStd(food, n):
    food.sort(reverse=True)
    while len(food) % n:
        food.append(0)
    family_count = len(food) // n

    if n == 2: # optimal
        return list(zip(food[:len(food)//2], reversed(food[len(food)//2:])))
    else: # heuristic approach
        partition = [[] for _ in range(family_count)]
        for food_item in sorted(food, reverse=True):
            partition.sort(key=lambda f: sum(f) if len(f) &lt; n else float('inf'))
            partition[0].append(food_item)
        return local_search(partition, calc_std(partition))

def local_search(partition, best_std, N = 20):
    # find indices with smallest and largest sum
    families1 = nsmallest(N, partition, key=sum)
    families2 = nlargest(N, partition, key=sum)
    best_improved_swap = None

    for family1, family2 in product(families1, families2):
        for index1, index2 in product(range(len(family1)), range(len(family2))):
            family1[index1], family2[index2] = family2[index2], family1[index1]
            std = calc_std(partition)
            if std &lt; best_std:
                best_std = std
                best_improved_swap = (family1, family2, index1, index2)
            family1[index1], family2[index2] = family2[index2], family1[index1]

    if best_improved_swap:
        family1, family2, index1, index2 = best_improved_swap
        family1[index1], family2[index2] = family2[index2], family1[index1]
        partition = local_search(partition, best_std)
    elif N &lt; 100:
        return local_search(partition, best_std, 100)
    return partition


The complete code and the output is available on Github: Code, Output 

edit

I was confused about the std-calculation, that N3buchadnezzar proposed in the original question. I updated it to the correct mathematical definition, so we can compare different solutions.

edit 2

In my last submission I varied the family count. E.g. the best solution for n = 2 used 507 families. N3buchadnezzar told me, that there have to be exactly ceil(len(food) / n) families. So I changed my code a little bit. Basically removed the loop over the family counts and improved the local search.