python – Getting the minimum possible value from list consist of ‘0’ and ‘1’ by multiply no. of [0,1] and add the result after sliced in ‘k’ section


This code write to determine a way to place the N horses into the K stables, so that the total coefficient of unhappiness is minimized.

I use python to write a code and I want to reduce the running time and memory used. Or maybe shorten the code. What should I do?

My memory used is about 67,000- 80,000 KB.

My running time is about 0.25 – 0.28.

Should I try to change the ways I acquire all possible combinations in ‘printAllKLength()’
Or get all the for loops outside of function inside the related function.

Question link: https://acm.timus.ru/submit.aspx?space=1&num=1167

This algorithm do as places the 1st P1 horses in the first stable, the next P2 in the 2nd stable and so on. Moreover, any of the K stables cannot be empty, and no horse must be left outside. There are black or white horses, which don’t really get along too well. If there are i black horses and j white horses in one stable, then the coefficient of unhappiness of that stable is i*j. The total coefficient of unhappiness is the sum of the coefficients of unhappiness of every of the K stables.

Determine a way to place the N horses into the K stables, so that the total coefficient of unhappiness is minimized.

Input:
On the 1st line there are 2 numbers: N (1 ≤ N ≤ 500) and K (1 ≤ K ≤ N). On the next N lines there are N numbers. The i-th of these lines contains the color of the i-th horse in the sequence: 1 means that the horse is black, 0 means that the horse is white.

Output:
You should only output a single number, which is the minimum possible value for the total coefficient of unhappiness.

Sample Input and Output

Input:
6 3
1
1
0
1
0
1
Output: 2
import sys 

inputs =  list(map(int, input().split()))

n = inputs(0)               #n = no. of horse
k = inputs(1)               #k = no. of stable
seq = ()                    #seq = keep input horse sequence
options = ()                #options = keep the options of place no. of horse
combi = ()                  #keep all combinations based on options in list of string element

#maxc = To find the maximum no of horse should be place consider that left no
#       empty stable and at least place one horse in first stable
maxc = n-(k-1)

#To run loop and append the input sequence into ‘seq’ list.
for i in range(n):
    s = int(input())
    seq.append(s)

#find options to place horse = 1,2,3,4 if n = 6
#because all the stable cannot be empty and therefore must at least put horse
#in one stable, so in one stable cannot put horse more than n-(k-1)

#to run loop and append options to place horses based on ‘maxc’ value into ‘options’ list.
for i in range(maxc):
    options.append(str(i+1)) 

#functions to get all combination of no. of horse per stable based on options
#It is mainly a wrapper over recursive function printAllKLengthRec()
def printAllKLength(set, kk):   
    size_of_list = len(set)
    printAllKLengthRec(set, "", size_of_list, kk)

# The main recursive method to print all possible strings of length k     
def printAllKLengthRec(set, prefix, size_of_list, kk):

    # Base case: kk is 0, 
    # print prefix 
    if (kk == 0) :
        combi.append(prefix)
        return

    # One by one add all characters  
    # from set and recursively  
    # call for k equals to k-1
    for i in range(size_of_list):

        # Next character of input added  
        newPrefix = prefix + set(i)

        # k is decreased, because  
        # we have added a new character  
        printAllKLengthRec(set, newPrefix, size_of_list, kk - 1)

printAllKLength(options, k)

#Function to convert teh string element list to int element list and
#check if sums of element in sublist are equal to 'n'
def convert(the_list):

   #change list of str elements to int elements instead
   #Run the for loop to convert from string value to list of int value for one
   #combination and substitute the converted into ‘the_list’ at the same index
   #‘i’ that currently perform conversion on that combination.
   for i in range(len(the_list)):
      digits = (int(x) for x in str(the_list(i)))
      the_list(i) = digits

   b_list = ()

   #check if all sum of each combination from function is actually
   #equal to input no. of horse

   #Create a temporary list ‘b_list’ to compute the sum of each 
   #combination(‘a_list(i)’) and check condition if the sum is equal to ‘n’ value
   #(Total number of horse). If so, then append ‘a_list(i)’ combination and the 
   #‘convert_check()’ function 
   for i in range(len(the_list)):
      sums = sum(the_list(i))
      if sums == n:
         the_list.append(the_list(i))
   return b_list

pos_ways = convert(combi)

#Function to split a seq of horse into stable based on no. of horse per stable
from itertools import islice

def split(the_list, combi_list):
    j = 0
    result_list = ()
    while j < len(combi_list):
        the_list_iter = iter(the_list)
        re2 = (list(islice(the_list_iter, length)) for length in combi_list(j))
        result_list.append(re2)
        j += 1
    return result_list

#find the no of black & white horse in each placed sequence of each combination
#re_seq = ((1),(1),(0,1,0,1))
def find_bw(the_list):
    black = 0
    white = 0
    for i in range(len(the_list)):
        o = the_list(i)
        if the_list(i) == 0:
            white += 1
        elif the_list(i) == 1:
            black += 1
    s = (white, black)
    return s

#find the no of black & white horse in all seq of all combination
#all_re_seq = (((1),(1),(0,1,0,1)),((1,1),(0),(1,0,1)),......)
def find_bw2(the_list2):
    for i in range(len(the_list2)):
        s2 = find_bw(the_list2(i))
        the_list2(i) = s2
    return the_list2

re_seq = split(seq, pos_ways)
no_of_horse = ()

#to get no. of black and white horse in each stable
for i in range(len(re_seq)):
    go = find_bw2(re_seq(i))
    no.append(go)

#to get the coefficient unhappiness in each stable by
#no. of black horse * no. of white horse
def mul_co(the_list):
    for i in range(len(the_list)):
        tu = the_list(i)
        t1 = tu(0)
        t2 = tu(1)
        the_list(i) = t1*t2
    return the_list

#keep all coefficient unhappiness in each stable for all possible ways
coef = (-1)*len(no)

#run function and store all coefficient unhappiness in each stable
#for all possible ways
for i in range(len(no)):
    ko = mul_co(no(i))
    coef(i) = ko

max_value = sys.maxsize

#to find the minimum of coefficient happiness
def coef_un(the_list):
    minimum = max_value
    for j in range(len(the_list)):
        sums = 0
        for i in range(len(the_list(j))):
            sums += the_list(j)(i)
        the_list(j) = sums
        minimum = min(minimum, the_list(j))
    return minimum

print(coef_un(coef))