CODEWITHSUNDEEP
pythonalgorithmlist
Benjamin Hodgson
Benjamin Hodgson

Reputation: 44634

Building a list from positional relationships between the elements

How can I form a flat, ordered list from a set of items, each possibly with requirements that they appear before and/or after some other item in the list?

Sample input
-----------------------
3: before 5 and after 2
8: before 5
2: before 3
5: no constraint

Sample output
-------------
[2, 3, 8, 5]

Obviously, the general solution to this sort of problem is non-unique (consider the case of lots of elements with no constraints), which is fine - any result which meets the constraints will do.

I also know that there are lots of error cases here (duplicate elements, two elements which both want to be before each other, etc...). Right now I'm interested in the 'happy path' - I'll add error handling later.

Here are a few test cases in Python. They're far from comprehensive, but should be enough to give you the idea:

def test_some_unconstrained_elements():
    l = ListBuilder()
    l.add(1, after=None, before=None)
    l.add(7, after=None, before=None)
    assert set(l.to_list()) == {1, 7}

def test_element_which_should_appear_after_already_added_element():
    l = ListBuilder()
    l.add(5, after=None, before=None)
    l.add(3, after=5, before=None)
    assert l.to_list() == [5, 3]

def test_element_which_should_appear_after_element_added_later():
    l = ListBuilder()
    l.add(3, after=5, before=None)
    l.add(5, after=None, before=None)
    assert l.to_list() == [5, 3]

def test_element_which_should_appear_between_two_already_added_elements():
    l = ListBuilder()
    l.add(4, after=None, before=None)
    l.add(2, after=None, before=None)
    l.add(6, after=2, before=4)
    assert l.to_list() == [2, 6, 4]

def test_two_elements_either_side_of_new_element():
    l = ListBuilder()
    l.add(4, after=6, before=None)
    l.add(2, after=None, before=6)
    l.add(6, after=None, before=None)
    assert l.to_list() == [2, 6, 4]

def test_element_which_should_appear_after_missing_element():
    l = ListBuilder()
    l.add(4, after=6, before=None)
    assert l.to_list() == [4]

def test_two_elements_which_should_appear_after_the_same_element():
    l = ListBuilder()
    l.add(4, after=None, before=None)
    l.add(6, after=4, before=None)
    l.add(8, after=4, before=None)
    assert l[0] == 4
    assert set(l[1:]) == {6, 8}

def test_fully_constrained_short_list():
    l = ListBuilder()
    l.add(3, after=4, before=None)
    l.add(4, after=5, before=3)
    l.add(5, after=None, before=4)
    assert l.to_list() == [5, 4, 3]

NB. This is not homework. It's an actual problem I need to solve in real life (I'm working on a test framework; I'll be happy to elaborate on what I need it for), but I'm not clever enough for it :(

Upvotes: 4

Views: 85

Answers (2)

DSM
DSM

Reputation: 353169

This looks like a topological sort, so grab an implementation from somewhere (e.g. here) and modify your data format to work with it. For example:

def toposort2(data):
    # modified from http://rosettacode.org/wiki/Topological_sort#Python
    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        for x in sorted(ordered):
            yield x
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    if data:
        raise ValueError("a cyclic dependency exists")

def toposort_wrap(data):
    dep_dict = {}
    for d in data:
        for bef in d.get("before", ()):
            dep_dict.setdefault(bef, set()).add(d["value"])
        dep_dict.setdefault(d["value"], set()).update(d.get("after", ()))
    print dep_dict
    result = list(toposort2(dep_dict))
    return result

After which we have

>>> data = [dict(value=3, before=(5,), after=(2,)),
...         dict(value=8, before=(5,)),
...         dict(value=2, before=(3,)),
...         dict(value=5)]
>>> toposort_wrap(data)
{8: set([]), 2: set([]), 3: set([2]), 5: set([8, 3])}
[2, 8, 3, 5]

(Untested, so more proof-of-concept than anything else, but this is how I'd go about it.)

Upvotes: 3

kraskevich
kraskevich

Reputation: 18556

Topological sort seems to be a good solution. The graph can look like that: each element of the list is node. If a goes before b, then there is a directed edge from b to a.

Upvotes: 0

Related Questions