Algorithm that balances the number of elements in

问题:

Lets say you have an array with 4 different types of elements.

1 1 2 3 1 2 2 3 3 4 4 1.

I want to find the longest subinterval that results in an equal number of each elements and the largest total number of elements.

In this case, it would be

1 1 2 3 1 2 2 3 3

because this results in 3 twos, 3 threes, and 3 ones.

I believe this is some sort of modified dynamic programming, or something that requires prefix sums but I am not too sure. Can someone give me insight on how to start?

回答1:

#!/usr/bin/env python

#The demo data
SET = [1,1,2,3,1,2,2,3,3,4,4,1]

#Function to map the counts of the values in the set
def map(x):
        ret = {}
        for v in x:
                if v not in ret.keys():
                        ret.update({v:0})
                ret[v] += 1
        return ret

#Function to check if all counts in the map are the same
def checkMap(x):
        val = None
        for k,v in x.items():
                if val != None and v != val:
                        return False
                else:
                        val=v
        return True

#Determine the initial counts
counts = map(SET)

#Now step back from end index to start
for ix in range(len(SET) - 1, 0, -1):
        val = SET[ix]
        counts[val] += -1
        if counts[val] == 0:
                del counts[val]
        if checkMap(counts):
                print "Condition Reached, Largest Subset is:",SET[0:ix]
                break