Count the ways to partition an array into two equal sets

Question

I need to count the number of ways to partition an array into two contiguous arrays such that those arrays contain exactly same set of items.

Suppose A = [4, 1, 1, 2, 4, 2, 4, 1]. If you pass this array to the function, it needs to return 2. (Those subarrays are [4, 1, 1, 2] & [4, 2, 4, 1] and [4, 1, 1, 2, 4] & [2, 4, 1].)

Suppose A = [1, 5, 1]. If you pass this array to the function, it needs to return 0.

My code given below. Is there any better way to do this?

def solve(A):    
    count = 0
    for i in range(1, len(A)-1/2):

        left = A[:i]
        right = A[i:]

        left[:i].sort()
        right[i:].sort()

        if set(left) == set(right):
            count += 1
    return count

Answer 1

Your current approach is going to be very slow because you're slicing the each time and then that is followed by an unnecessary sort calls and ultimately you call set() on both of the lists.

Slicing a list is very slow, because it requires creating an array of new references(pointers) to the items of the original array. To fix that we can use collections.deque here, ie. start with two deques first. First one is going be a deque(say full_deque) of the list passed to the array and second one will be empty(say current_deque). And now during the loop we simply pop the leftmost item from the full_deque and append it to the current_deque, these are O(1) operations for a deque so we will save a lot of time. And then simply call set() on both deques and compare those sets:

from collections import deque

def solve_deque(seq):
    count = 0
    full_deque = deque(seq)
    current_deque = deque()
    for _ in xrange(len(seq)):
        current_deque.append(full_deque.popleft())
        if set(current_deque) == set(full_deque):
            count += 1
    return count

The above operation is around 7 times faster than your version:

>>> A = [random.randint(0, 100) for _ in xrange(1000)]
>>> %timeit solve(A)
10 loops, best of 3: 74.4 ms per loop
>>> %timeit solve_deque(A)
100 loops, best of 3: 11.3 ms per loop

But for bigger list it is still not good enough as the set() calls in each loop are expensive.

>>> A = [random.randint(0, 100) for _ in xrange(10**5)]
>>> %timeit solve_deque(A)
1 loops, best of 3: 1min 26s per loop

To improve this even further we need to approach this differently, and one such approach is to use a Counter. Similar to deque we maintain two Counters here: 1. full_counter: Contains count of the initial list items 2. current_counter: Contains counts of items seen so far. Apart from these we are also going to maintain two sets here: 1. full_keys: Initial unique items from the list 2. current_keys: Unique items seen so far.

Here during the loop we are going to increment the count of current item in current_counter and decrease its count from the full_counter. But we can't compare these counters, so that's where the 2 sets come in. Firstly add current item to the current_keys set and then check if the count of current item is equal to 0 in full_counter and if it is then we can remove this item from the full_keys set and then simply compare these two sets:

from collections import Counter

def solve_counter(seq):
    count = 0
    full_counter = Counter(seq)
    current_counter = Counter()
    full_keys = set(seq)
    current_keys = set()

    for item in seq:
        current_counter[item] += 1
        full_counter[item] -= 1
        current_keys.add(item)
        if full_counter[item] == 0:
            full_keys.remove(item)
        count += full_keys == current_keys
    return count

Timings:

>>> A = [random.randint(0, 100) for _ in xrange(1000)]
>>> %timeit solve_counter(A)
1000 loops, best of 3: 764 µs per loop
>>> A = [random.randint(0, 100) for _ in xrange(10**5)]
>>> %timeit solve_counter(A)
10 loops, best of 3: 109 ms per loop

---

Few other points:

• The recommended way to get both item and the index is to use enumerate() rather than using range() with indexing. Also in Python 2 range() returns a list, so unless you actually need a list always use xrange().

• Use upper case variable names(A) only for module level constants, that applies to the function arguments as well, we can use num_list or seq instead of A here.

• left[:i].sort() and right[i:].sort() are useless, slice on Python lists returns a new shallow copy. So, here you created two new lists first, sorted them and then threw them away. To sort left and right, simply do left.sort() and rigth.sort().

Answer 2

Your algorithm's complexity is \$\mathcal{O}(n^2 \log(n))\$, (extra \$\log(n)\$ is from sets), but this problem can be easily solved within the complexity of \$\mathcal{O}(n \log(n))\$.

The key thing to observe is that if we go on to add the elements in a set, at some point the size of set doesn't increase....

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# pylint: disable=C0111


def solve(arr):
    fhalf = set()
    prefl, i = 0, 0

    for x in xrange(len(arr)):
        fhalf.add(arr[x])
        if len(fhalf) != prefl:
            prefl = len(fhalf)
            i = x
    w = i
    shalf = set()
    for x in xrange(len(arr) - 1, i, -1):
        shalf.add(arr[x])
        if len(shalf) == prefl:
            w = x
            break
    return max(w - i, 0)


def main():
    print solve([1, 5, 1, 5, 1])
    print solve([4, 1, 1, 2, 4, 2, 4, 1])


main()

Times

In [12]: arr = [randint(0, 100) for _ in xrange(10**3)]

In [13]: %timeit solve(arr)
1 loops, best of 3: 303 ms per loop

In [14]: %timeit solve_nlogn(arr)
1000 loops, best of 3: 502 µs per loop

In [19]: arr = [randint(0, 100) for _ in xrange(10**4)]

In [20]: %timeit solve_nlogn(arr)
100 loops, best of 3: 3.64 ms per loop

In [21]: arr = [randint(0, 100) for _ in xrange(10**5)]

In [22]: %timeit solve_nlogn(arr)
10 loops, best of 3: 34.4 ms per loop

In [23]: 

My Pentium went dead even for the \$10^4\$ data so I don't have benchmarks of your algorithm. for >= \$10^4\$

Answer 3

First, your range definition is a little strange, the -1/2 is unnecessary. It should be len(A) instead of len(A)-1/2. In python range excludes the second element, so range(1,3) is [1,2].

Sorting the two array is an unnecessary overhead since you are creating sets of them anyways.

This is my suggestion:

def solve(A):    
    count = 0
    for i in range(1, len(A)):
        if set(A[:i]) == set(A[i:]):
            count += 1
    return count

Answer 4

I have read the other suggestions with interest, and, as a person who is somewhat new to Python, I was wondering whether I was understanding them all correctly. The suggestions I see are clearly significantly better than your current code, but are missing an alternative algorithm that would make the performance significantly faster.

The solution is attainable in \$O(n)\$ time.

Alternative

Conceptually, the problem is simple:

1. get a collection of all the actual values in the set. This requires a single scan of the entire input array.
2. find the size of the left-most portion of the array that contains the entire set.
3. find the size of the right-most portion that also contains the entire set.
4. if the left and right spans do not overlap, then there is at least one solution. The actual number of solutions is the number of members between the left and right spans (plus 1).

By using a dict to contain the collection of distinct values used in the input array, you get O(1) performance (on average, slightly worse in the event that the dictionary key values become congested - which in this input example is very unlikely.

By combining the identification of the left-portion with the full scan, you can reduce the number of iterations (though it is still \$O(n)\$).

Here's the resulting code:

def countParts(num):
    distinctVal = {}
    size = 0
    left = 0
    for idx, val in enumerate(num):
        distinctVal[val] = 1
        if len(distinctVal) > size:
            left = idx
            size = len(distinctVal)

    for right in xrange(len(num) - 1, left, -1):
        distinctVal.pop(num[right], None)
        if len(distinctVal) == 0:
            return right - left
    return 0

Note that, in the above code, the key features are that it uses the enumerate mechanism to get both the index and value from the input array. This allows us to identify the left-most index of the data that contains the complete set. That set is found by resetting the left pointer each time there's a new distinct value.

Once it has fully scanned the input, it then starts from the right side, and removes each distinct value it finds from the distinctVal. When the dict is empty, it means we have covered the entire distinct set of values.

The difference between the end of the left set, and the start of the right set, is the number of solutions that are possible.

Performance

I compared the performance of my algorithm with that of Ashwini's. The solution I propose is about 40 times faster, for larger inputs, and about 10 times faster for smaller ones. This makes me believe that the time-complexity of my solution has a reduced dimension somewhere, compared to the other. I am not exactly sure why it is so much faster, or what that dimension is.... Here's how I tested them all.... note that your solution effectively does not complete the larger test cases... it's simply not scalable enough.

First, though, the results:

AP We have 1 splits from source 10
RL We have 1 splits from source 10
AP We have 6 splits from source 15
RL We have 6 splits from source 15
AP We have 8922 splits from source 10000
RL We have 8922 splits from source 10000
AP We have 98848 splits from source 100000
RL We have 98848 splits from source 100000
AP We have 987404 splits from source 1000000
RL We have 987404 splits from source 1000000
AP We have 0 splits from source 100000
RL We have 0 splits from source 100000
[27.986757040023804, 27.898667097091675, 27.68735098838806]
[0.6999490261077881, 0.7145471572875977, 0.701956033706665]

AP is Ashwini's post/solution, and RL is my solution.

The actual code that produced the output is:

import random
import timeit

from collections import Counter

def solve_counter(seq):
    count = 0
    full_counter = Counter(seq)
    current_counter = Counter()
    full_keys = set(seq)
    current_keys = set()

    for item in seq:
        current_counter[item] += 1
        full_counter[item] -= 1
        current_keys.add(item)
        if full_counter[item] == 0:
            full_keys.remove(item)
        count += full_keys == current_keys
    return count

def countParts(num):
    distinctVal = {}
    size = 0
    left = 0
    for idx, val in enumerate(num):
        distinctVal[val] = 1
        if len(distinctVal) > size:
            left = idx
            size = len(distinctVal)

    for right in xrange(len(num) - 1, left, -1):
        distinctVal.pop(num[right], None)
        if len(distinctVal) == 0:
            return right - left
    return 0

cases = [
        [1,2,3,4,5,5,4,3,2,1],
        [1,2,3,4,5,1,2,3,4,5,5,4,3,2,1],
        [random.randint(0, 100) for _ in xrange(10**4)],
        [random.randint(0, 100) for _ in xrange(10**5)],
        [random.randint(0, 1000) for _ in xrange(10**6)],
        [random.randint(0, 10000) for _ in xrange(10**5)]
    ]

for todo in cases:
    # print "OP We have {} splits from source {}".format(solve(todo), len(todo))
    print "AP We have {} splits from source {}".format(solve_counter(todo), len(todo))
    print "RL We have {} splits from source {}".format(countParts(todo), len(todo))

print timeit.repeat("for todo in cases: solve_counter(todo)", "from __main__ import cases,solve_counter", number=3)
print timeit.repeat("for todo in cases: countParts(todo)", "from __main__ import cases,countParts", number=3)

Review