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-79,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.
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.
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.
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
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)) ```