Finding the sublist with best utility function among all list’s permutations

I try to find the the better solution in terms of time complexity. Among the list of elements I need to find the sublist with maximum value of given utility function.

Each element has it’s own type. The type of the adjusted element in the sublist should be different

My code works, I find it not optimal. I guess there is a room for improvement in terms time complexity.

import sys #python 3.5  class Object:     def __init__(self, initial_position, object_type):         self.initial_position = initial_position         self.object_type = object_type      @property     def object_relevance(self):         '''         object utility function         '''         return 2 ** (-self.initial_position)   class ObjectList:     def __init__(self, list):         self.object_list = list         self.rel = 0         self.best_list = []       def _list_relevance(self, object_sub_list):         '''         list utility function         '''         relevance = 0         for j in range(len(object_sub_list)):             relevance += (2 ** (-j)) * object_sub_list[j].object_relevance         return relevance       def _check_sub_list_permissibility(self, object_sub_list):         for i in range(len(object_sub_list) - 1):             if object_sub_list[i].object_type == object_sub_list[i + 1].object_type:                 return False             else:                 pass         return True       def _element_not_exist_in_the_list(self, object_sub_list, elem):         for object in object_sub_list:             if elem.initial_position == object.initial_position:                 return False         return True       def _traverse(self, object_list, init_list):         for elem in object_list:             try_list = init_list.copy()             if self._element_not_exist_in_the_list(try_list, elem):                 try_list.append(elem)                 if self._check_sub_list_permissibility(try_list):                     init_list = try_list                     if self._list_relevance(init_list) > self.rel:                         self.best_list = init_list                         self.rel = self._list_relevance(init_list)                     next = [object for object in object_list if object.initial_position != elem.initial_position]                     self._traverse(next, init_list)       def find_relevant_subset(self):         self._traverse(self.object_list, [])         return self.best_list  if __name__ == '__main__':     input = sys.stdin.read()     data = list(map(int, input.split()))     n, m = data[:2]     a_list = [Object(i,object_type) for i, object_type in enumerate(data[2:])]     object_list = ObjectList(a_list)     best_list = object_list.find_relevant_subset()     return_format = ' '.join([str(object.initial_position) for object in best_list])     sys.stdout.write(return_format) 

The input format: The first line contains numbers separated by a space n and m. m – is the number of unique types and n is the number of elements. In the next n lines of the input the type of every element is specified.

10 2 1 1 1 0 0 1 0 1 1 1 

So in the example above we have 10 elements with two different types (0 and 1). The input specifies the type of each element. Each object has it’s own type (in this example – 0 or 1) object_type and the order index initial_position.

The output format: 0 3 1 4 2 6 5

The goal is to find the sublist with maximum value of given utility function (_list_relevance).

This output shows the list of element’s initial_position. Also the object_type of the adjusted elements in this list are different.

  • The element with initial_position == 0 has object_type == 1
  • The element with initial_position == 3 has object_type == 0
  • The element with initial_position == 1 has object_type == 1
  • The element with initial_position == 4 has object_type == 0
  • The element with initial_position == 2 has object_type == 1
  • The element with initial_position == 6 has object_type == 0
  • The element with initial_position == 5 has object_type == 1

My algorithm: I tried to represent all possible combinations of the initial list as a tree and perform the DFS consider the given constrains. My code works, I find it not optimal. I guess there is a room for improvement in terms time complexity.