CODEWITHSUNDEEP
algorithmmathdata-structuresgraphgraph-algorithm
Ayush
Ayush

Reputation: 2608

Merge inequalities into one

Suppose that I have been given n inequalities as follows:

Input:

Example : n=4

f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3

Output:

I have to merge these inequalities to make 1 inequality such that the above inequalities stay true. For the example above:

f4 > f2 > f1 > f3

There can be multiple inequalities as answer; I need any one that is correct. It is also sure that there exists a solution for the given inputs; that is, we can assume that the inputs will always be valid.

Any ideas on how to make an algorithm to implement this?

I have been thinking that directed graphs can be used for this, but I am not sure.

Any ideas to implement the above algorithm? The value of n can be very large.

Upvotes: 1

Views: 344

Answers (4)

Paddy3118
Paddy3118

Reputation: 4772

This solution extracts all two-item inequalities and performs a sort that obeys them:

Python 2.7.5 (default, May 15 2013, 22:43:36) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ineq = """f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3"""
>>> print(ineq)
f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3
>>> greater_thans, all_f = set(), set()
>>> for line in ineq.split('\n'):
    tokens = line.strip().split()[::2]
    for n, t1 in enumerate(tokens[:-1]):
        for t2 in tokens[n+1:]:
            greater_thans.add((t1, t2))
            all_f.add(t1)
        all_f.add(t2)


>>> sorted(all_f, cmp=lambda t1, t2: 0 if t1==t2 else (1 if (t1, t2) not in greater_thans else -1))
['f4', 'f2', 'f1', 'f3']
>>>

Kind guys on group comp.lang.python pointed out that if the original set of relations did not include every less-than relation then the sort might fail so I needed to add a function expand_transitive_relations:

from __future__ import print_function
from itertools import permutations


def extract_relations(ineq):
    "Turns lines of lists of relations separated by '>' into set of tuples of (x,y) pairs where x > y"
    greater_thans, all_f = set(), set()
    for line in ineq.split('\n'):
        tokens = line.strip().split()[::2]
        for n, t1 in enumerate(tokens[:-1]):
            for t2 in tokens[n+1:]:
                greater_thans.add((t1, t2))
                all_f.add(t1)
            all_f.add(t2)
    expanded = expand_transitive_ralations(greater_thans, all_f)
    return sorted(all_f, cmp=lambda t1, t2: 0 if t1==t2 else 
                                            (1 if (t1, t2) not in expanded else -1))

def expand_transitive_ralations(greater_thans, all_f):
    "if x > y and y > z then x > z"
    start_len = len(greater_thans)
    while True:
        for x, y, z in permutations(all_f, 3):
            if (x, y) in greater_thans and (y, z) in greater_thans:
                greater_thans.add((x, z))
        new_len = len(greater_thans)
        if start_len == new_len:
            break
        else:
            start_len = new_len
    return greater_thans

if __name__ == '__main__':
    for ineq in (
            """\
            f4 > f2 > f3
            f4 > f1 > f3
            f4 > f2 > f1
            f2 > f1 > f3\
            """,
            """\
            f4 > f2 > f3 
            f4 > f1 > f3 
            f4 > f2 > f1 
            f2 > f1 > f3 
            f3 > f5\
            """,
            """\
            f2 > f3 
            f3 > f1\
            """):
        print(ineq)
        print('  Becomes:', ' > '.join(extract_relations(ineq)), '\n')

Output:

            f4 > f2 > f3
            f4 > f1 > f3
            f4 > f2 > f1
            f2 > f1 > f3            
  Becomes: f4 > f2 > f1 > f3 

            f4 > f2 > f3 
            f4 > f1 > f3 
            f4 > f2 > f1 
            f2 > f1 > f3 
            f3 > f5            
  Becomes: f4 > f2 > f1 > f3 > f5 

            f2 > f3 
            f3 > f1            
  Becomes: f2 > f3 > f1

Upvotes: 2

Albert Wifstrand
Albert Wifstrand

Reputation: 230

An approach that could work is to make a directed graph G in which an edge u to v represents that u > v (naturally, every inequality corresponds to an edge in G), look for a vertex w with no incoming edges and then try to find a non-cyclic path with n vertices, starting at w. This is merely intuition, though; it could be erroneous and to me there's no obvious similarity to Tacet's and user2040251's topological sort proposals.

Edit It looks like my suggestion involves topological sort too, but maybe the specifics differ somewhat between our suggestions?

Upvotes: 0

Tacet
Tacet

Reputation: 1421

You can make a directed graph, in which vertices will be given variables and edges will be between bigger and smaller (connection v1 --> v2 means v1 > v2). For example:

f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3

means edges are from f4 to f2 & f1, from f2 to f3 & f1 and from f1 to f3. f3 has no outgoing edges.

Now you can just sort topologically graph. Pay attention, if you have a cycle there is no solution! f4 -> f2 -> f1 -> f4 means f4 > f2 > f1 > f4.

Upvotes: 1

kraskevich
kraskevich

Reputation: 18556

You can use topological sort on a directed graph that represents these inequalities. It can be done in O(N + M) time using depth-first search(where N is the number of variables and M is the number of inequalities).

Upvotes: 0

Related Questions