Partial order sorting?

Question

Say, we have some items, and each defines some partial sorting rules, like this:

I'm A and I want to be before B

I'm C and I want to be after A but before D

So we have items A,B,C,D with these rules:

• A>B
• C<A, C>D
• nothing else! So, B and D have no 'preferences' in ordering and are considered equal.

As you see, transitive relation rules are not working here. However, if A>B it still means that B<A. So, there can be multiple possible results of sorting:

1. A B C D
2. A C D B
3. A C B D
4. A B C D

How can I implement a sorting algorithm that handles such a situation?

---

The reason: there're multiple loadable modules, and some of them 'depend' on others in a way. Each module can declare simple rules, relative to other modules:

Load me before module A

Load me after module B

Load me before module A but after module B

now I need to implement this ordering somehow.. :)

---

Answer: code by Paddy McCarthy (MIT)

## {{{ http://code.activestate.com/recipes/577413/ (r1)
try:
    from functools import reduce
except:
    pass

data = {
    'des_system_lib':   set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()),
    'dw01':             set('ieee dw01 dware gtech'.split()),
    'dw02':             set('ieee dw02 dware'.split()),
    'dw03':             set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()),
    'dw04':             set('dw04 ieee dw01 dware gtech'.split()),
    'dw05':             set('dw05 ieee dware'.split()),
    'dw06':             set('dw06 ieee dware'.split()),
    'dw07':             set('ieee dware'.split()),
    'dware':            set('ieee dware'.split()),
    'gtech':            set('ieee gtech'.split()),
    'ramlib':           set('std ieee'.split()),
    'std_cell_lib':     set('ieee std_cell_lib'.split()),
    'synopsys':         set(),
    }

def toposort2(data):
    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
        yield ' '.join(sorted(ordered))
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

print ('\n'.join( toposort2(data) ))
## end of http://code.activestate.com/recipes/577413/ }}}

Elater

Answer 1

You'll want to construct a dependency graph (which is just a flavor of directed graph), and then follow a topologically sorted ordering. It's been a while since I took a combinatorics class, so the Wikipedia article will probably be more helpful than I am for a topological sort algorithm. I'm hoping giving you the proper terminology is helpful. :)

As far as constructing the graph, you'll basically just need to have each module with a list of that module's dependencies.

You'll just need to rephrase your rules a bit... "I'm C and I want to be after A but before D" would be expressed as "C depends on A" as well as "D depends on C", such that everything is flowing in a standard direction.

Photophilous

+1 Spot-on with the terminology. There are plenty Python implementations (e.g. this one) if OP needs. – Flann

Helped a lot, thank you! However, this has little to do with graphs in its implementation. The logic is: 0. create an empty list sorted. 1. walk through the list, pick the smallest item min(compared to all others). There can be multiple smallest ones, pick any. 2. Add min to sorted 3. If there are more items — loop back to 1 – Elater

@o_O Tync The only difference is that your version is O(n^2), where 'proper' topological sorting works in O(E) (where E is the number of edges-dependencies). As for relation with graphs, your whole structure is a graph, whether you like it or not :) – Decompound

NetworkX implements this sort too. – Men

Found a simple implementation: logarithmic.net/pfh-files/blog/01208083168/sort.py – Elater

@o_O Tync: Wooh! very nice code, I think you should post it as an answer so that it does not disappear if the site goes dead (with proper attribution of course). – Astigmatism

Answer 2

Following will return a dictionary with number as values to the variabes:

list them in the descending order to get the required output

def sorter(var_str: str, the_list: list):
    '''
    1st Argument must be a STRING
        variables, seperated by commas(','),
        WITHOUT ANY SPACES
    Eg: if a, b, c, d are the variables:
            sorter('a,b,c,d', [...])    --> Allowed
            sorter('a, b, c, d', [...]) --> Not Allowed
            sorter('a b c d', [...])    --> Not Allowed

    2nd Argument must be LIST of STRINGS
        having the conditions which can only include
            variables mentioned in the 1st Argument
            seperated with > or = or <,
        WITHOUT ANY SPACES
    Eg: if the conditions are (a > b = c > e), (c > d):
            sorter('...', ['a>b=c>e', 'c>d']        --> Allowed
            sorter('...', ['a > b = c > e', 'c > d']--> Not Allowed
            sorter('...', ['a > b=c > e', 'c > d']  --> Not Allowed
    '''

    level, main_cond_list= {var: 0 for var in var_str.split(',')}, []

    for condition in the_list:
        # Separating conditions & vars
        cond_var = condition.replace('>', ' ').replace('=', ' ').replace('<', ' ').split()
        cond_oper, counter = [], 0
        for i in cond_var[:-1]:
            counter += len(i)
            cond_oper.append(condition[counter])
            counter += + 1

        # SPLITTING THE CORE-CONDITIONS INTO SMALLER ONES
        for id in range(len(cond_oper)):

            # for > operator
            if cond_oper[id] == '>':
                for sub in range(id, -1, -1):
                    if cond_oper[sub] in ['=', '>']:
                        main_cond_list.append(f"{cond_var[sub]} > {cond_var[id + 1]}")
                        continue
                    break

            # for < operator
            if cond_oper[id] == '<':
                for sub in range(id, -1, -1):
                    if cond_oper[sub] in ['=', '<']:
                        main_cond_list.append(f"{cond_var[id + 1]} > {cond_var[sub]}")
                        continue
                    break

            # for = operator
            if cond_oper[id] == '=':
                for sub in range(id, -1, -1):
                    if cond_oper[sub] in ['=']:
                        main_cond_list.append(f"{cond_var[sub]} = {cond_var[id + 1]}")
                        continue
                    break

#             ABOVE 24 lines can be written as below _ commented lines too
#             for signs, strng in [['>', '{cond_var[sub]} > {cond_var[id + 1]}'],
#                                  ['<', '{cond_var[id + 1]} > {cond_var[sub]}'],
#                                  ['=', '{cond_var[sub]} = {cond_var[id + 1]}']]:
#                 exec(f'''
# if cond_oper[id] == '{signs}':
#     for sub in range(id, -1, -1):
#         if cond_oper[sub] in ['=', '{signs}']:
#             main_cond_list.append(f"{strng}")
#             continue
#         break''')

    for i in set(main_cond_list):
        print(i)

    for main_condition in set(main_cond_list):
        var1, cond, var2 = main_condition.split()
        if cond == '>' and var1 < var2:
            level[var1] = level[var2]+1
        if cond == '=':
            level[var1] = level[var2]
        # ABOVE 5 lines can be written as below commented lines also
        # for i in ['', '+1']:
        #     exec(f'''level[{main_cond_list[0]}] {main_cond_list[1]} level[{main_cond_list[0]}[2]{i}''')

    return level

Oud

This is a forum for asking and answering questions. I don't see a question in your post. The post also looks like it could be homework for a programming class. If so, you may still receive hints from users here - but you'll need to ask a question. – Solnit