-4
\$\begingroup\$

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.

\$\endgroup\$

closed as unclear what you're asking by πάντα ῥεῖ, Mast, Peter Taylor, IEatBagels, Pieter Witvoet May 29 at 9:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ What does the output 0 3 1 4 2 6 5 mean in terms of real life? \$\endgroup\$ – Roland Illig May 26 at 5:59
  • 1
    \$\begingroup\$ Assume we have 10 elements. The output 0 3 1 4 2 6 5 means that the list of the first, fourth, second, fifth, third, seventh and six element has the best utility function. \$\endgroup\$ – Daniel Chepenko May 26 at 6:03
  • 1
    \$\begingroup\$ And how does the output relate to the input? I can see that there are as many 1s as there are elements in the output. I could simply return set(range(count(in, lambda x: x == 1))) to get the same result. Why would I need to have more complicated code than this? \$\endgroup\$ – Roland Illig May 26 at 6:08
  • 1
    \$\begingroup\$ Because we have a constrains that the type of the adjusted element in the output should be different. \$\endgroup\$ – Daniel Chepenko May 26 at 6:15
  • 5
    \$\begingroup\$ I think this post could benefit greatly from stating the utility function outside of the code. As it stands, it's somewhat hard to understand why the output elements have the order they have. I'm happy to format it with mathjax if you ping me after editing to include the utility function as plain text. Thanks! \$\endgroup\$ – Vogel612 May 26 at 11:25
2
\$\begingroup\$

Here is what I understood from your question. I'm still unsure since you didn't provide a detailed description about how the input is transformed into the output, and why some elements do not appear in the output.

Given:

  • A list of element types
  • A utility function that calculates a value for an element, given its index and type

Calculate a sublist of the given types, such that:

  • The sum of the utility function's values for the resulting list is maximal
  • In the sublist, adjacent elements must not have the same type
  • The elements in the returned list need not be in the same order as in the given list

Based on these assumptions, the idea is:

  1. Create a list of tuples (type, index, value)
  2. Sort the list so that the largest values come first
  3. Repeatedly take the first element from this sorted list whose type differs from the type at the end of the result
  4. From this filtered list, keep only the index from the tuples

And, after a while of programming, the corresponding code is:

import collections

from typing import List, Callable


def max_sublist(types: List[int], utility: Callable[[int, int], float]) -> List[int]:
    """
    Returns the indices into the types list such that the sum of the
    utility values is maximized and adjacent items from the result
    list don't have the same type.

    :param types: a list of arbitrary integers
    :param utility: a function that returns the value of the item,
    based on its (index, type)
    """

    Elem = collections.namedtuple('Elem', 'type index value')

    elems = [Elem(type, index, utility(type, index))
             for index, type in enumerate(types)]

    sorted_elems = sorted(elems, key=lambda elem: elem.value, reverse=True)

    # Repeatedly take the first element from sorted_elems
    # whose type differs from the type at the end of the result.
    remaining = sorted_elems[:]
    relevant_elems: List[Elem] = []
    done = False
    while not done:
        done = True
        for i, elem in enumerate(remaining):
            if len(relevant_elems) == 0 or elem.type != relevant_elems[-1].type:
                relevant_elems.append(elem)
                remaining.remove(elem)
                done = False
                break

    return [elem.index for elem in relevant_elems]


def test_max_sublist():
    result = max_sublist(
        [1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
        lambda type, index: 2 ** -index)
    print(result)

    assert result == [0, 3, 1, 4, 2, 6, 5]


if __name__ == '__main__':
    test_max_sublist()

In the programming phase, I used the following and a few more Stack Overflow answers:

The input format and the output format are mostly irrelevant to the question. Therefore it is good that you separated the I/O code from the interesting computation.

You don't need classes and objects for everything. As you can see, my code does not need any Object or ObjectList classes, it just needs functions.

Python provides the tools for manipulating lists efficiently. Steps 1, 2 and 4 almost fit into a single line of code, each. Only step 3 was difficult since it didn't fit into the typical processing model that the Python standard library supports.

\$\endgroup\$
  • \$\begingroup\$ Thanks for sharing! \$\endgroup\$ – Daniel Chepenko May 26 at 22:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.