Algorithm for finding if an array is balanced

Question

I'm trying to create a program that will create a 10 element array and then assign random values to each element. I then want the program to tell if the array is balanced. By balanced I mean, is there anywhere in the array values that at a certain element the sum of the values in the elements are equal to the sum of the array values in the elements greater than that current element.

Example

Element (1,2,3,4) Values (2,1,3,0) The program would then display that elements 1-2 are balanced to elemtns 3-4, because they both equal 4.

So far I have

import random

size = 10
mean = 0
lists = [0] * size
for i in range(size):
    var = random.randint(0,4)
    lists[i] = var

for i in lists:
    mean += i

avg = (mean)/(size)

I figured the only way the elements could be balanced is if the values average is equal to 2, so I figured that's how I should start.

I'd appreciate any help in the right direction.

To make a random list of `n` elements: `lists = [randint(0, 4) for _ in range(n)]`. To find the mean/first sample moment of a list of numbers: `avg = sum(lists) / float(len(lists))`. — Joel Cornett, May 08 '13 at 00:29
Your variable names are confusing, like having a single list named `lists`, a total called `mean`, … — abarnert, May 08 '13 at 00:29
Do you mean that the sum of some elements in your list is equal to the sum of some other elements, and that those twe groups may not intersect? — Lennart, May 08 '13 at 00:29
@Lennart yes that's what I mean. It's a confusing problem I know. — user2348621, May 08 '13 at 00:31
I don't see how the sum of elements 1 and 2 equals 4, since 2 + 1 = 3 != 4 — Joel Cornett, May 08 '13 at 00:31
Also, your logic is confusing. The average of the values in your example is 1.5, not 2, and yet it's balanced. So, what makes you think that the elements are balanced iff the average is 2? — abarnert, May 08 '13 at 00:31
@abarnet I now see that that won't work. How should I begin to find if the values balanced then? — user2348621, May 08 '13 at 00:37
@user2348621: By adding the values and comparing the results. — abarnert, May 08 '13 at 00:38
Meanwhile, are you sure you want to say "elements 1-2 are balanced to elemtns 3-4, because they both equal 3" instead of "elements 0-1 are balanced to 2-3", or, maybe even "0-2 … 2-4"? Anyone who understands programming will expect 0-based indexes, and anyone who doesn't understand programming will probably not get that these are indexes at all without more prompting/explanation, so 1-based indexes are usually not very useful (except to Visual Basic programmers, who don't count as anyone). — abarnert, May 08 '13 at 00:44

abarnert · Answer 1 · 2013-05-08T00:38:28.023

If I understand the question, the simplest solution is something like this:

def balanced(numbers):
    for pivot in range(len(numbers)):
        left_total = sum(numbers[:pivot])
        right_total = sum(numbers[pivot:])
        if left_total == right_total:
            return pivot
    return None

For example:

>>> numbers = [2, 1, 3, 0]
>>> balanced(numbers)
2
>>> more_numbers = [2, 1, 3, 4]
>>> balanced(numbers)

(That didn't print anything, because it returned None, meaning there is no pivot to balance the list around.)

While this is the simplest solution, it's obviously not the most efficient, because you keep adding the same numbers up over and over.

If you think about it, it should be pretty easy to figure out how to keep running totals for left_total and right_total, only calling sum once.

def balanced(numbers):
    left_total, right_total = 0, sum(numbers)
    for pivot, value in enumerate(numbers):
        if left_total == right_total:
            return pivot
        left_total += value
        right_total -= value
    return None

Finally, here's how you can build a program around it:

size = 10
numbers = [random.range(4) for _ in range(size)]
pivot = balanced(numbers)
if pivot is None:
    print('{} is not balanced'.format(numbers))
else:
    print('{} is balanced, because elements 1-{} equal {}-{}'.format(
        numbers, pivot+1, pivot+2, size+1))

One suggestion about your final function: If the list is balanced, at some point `left_total` must equal `right_total` and so they must both be equal to half the total of the whole list. So, you can avoid doing some of the work by just calculating `sum(numbers)/2` once and testing `left_total` against it. You don't need to keep updating `right_total` as you go. — Blckknght, May 08 '13 at 06:02

hughdbrown · Answer 2 · 2013-05-08T03:24:59.187

A good data structure to know about for this kind of problem is an array that has the cumulative sum. element[j] - element[i] is the sum from i to j in the original series. If you have the original series [1, 2, 3, 4], the cumulative series is [0, 1, 3, 6, 10]. The sum up to the i position in the original series is element[i] - element[0]. For this problem, we are interested in only a sum starting at 0, so this is a bit of overkill but, again, more fully useful for other problems.

Here is code to make a cumulative sum:

def cumulative_sum(series):
    s = [0]
    for element in series:
        s.append(element + s[-1])
    return s

Given that, we can find the pivot point with this code:

def find_pivot(series):
    cs = cumulative_sum(series)
    total = cs[-1]
    even_total = not (total & 1)
    if even_total:
        target = total // 2
        for i, element in enumerate(cs[1:]):
            if element == target:
                return i + 1
    return -1

Notice that it is not necessary to try dividing the series if we know the series sums to an odd number: there cannot be a pivot point then.

Alternatively, you can write find_pivot like this:

def find_pivot(series):
    cs = cumulative_sum(series)
    total = cs[-1]
    even_total = not (total & 1)
    if even_total:
        target = total // 2
        try:
            return cs.index(target)
        except ValueError:
            return -1
    return -1

It has the advantage that the looping is not done explicitly in python but in C code in the standard library.

Trying the code out:

def test():
    for i in range(1, 30):
        test_values = range(i)
        j = find_pivot(test_values)
        if j >= 0:
            print "{0} == {1}".format(test_values[:j], test_values[j:])

And we get this output:

[0] == []
[0, 1, 2] == [3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] == [15, 16, 17, 18, 19, 20]

Algorithm for finding if an array is balanced

2 Answers2

Linked