Discover strict ordering rules and reorder a sequence according to those rules.

discover_order.py

from typing import List
import itertools as it
from collections import Counter
import random


class Orderer:
    def __init__(self, strict=False):
        self.strict = strict
        self.ord = Counter()
    
    
    def unique_elems(self, seqs: List[List[str]]):
        elems = set()
        for seq in seqs:
            elems.update(set)
        return list(elems)

    def add(self, seq:List):
        for idx, elem in enumerate(seq):
            after = seq[idx+1]
            ord_pairs = [(elem, a) for a in after]
            self.ord.update(ord_pairs)

    def update(self, seqs: List[List[str]]):
        for seq in seqs:
            self.add(seq)

    def get_counts(self, a, b):
        return self.ord[(a,b)], self.ord[(b,a)]

    def order(self, a, b, strict=None):
        strict = self.strict if strict is None else strict
        result = 0
        ab, ba = self.get_counts(a,b)
        if ab > ba and (ba==0 or not strict):
            result = 1
        elif ba > ab and (ab==0 or not strict):
            result = -1
        return result

    def fractional_order(self, a, b):
        ab, ba = self.get_counts(a,b)
        numer = ab - ba
        denom = max(1, ab + ba)
        return numer / denom

def partition(array, low, high):
    pivot = array[high]
 
    # pointer for greater element
    i = low - 1
 
    # traverse through all elements
    # compare each element with pivot
    for j in range(low, high):
        if array[j] <= pivot:
 
            # If element smaller than pivot is found
            # swap it with the greater element pointed by i
            i = i + 1
 
            # Swapping element at i with element at j
            (array[i], array[j]) = (array[j], array[i])
 
    # Swap the pivot element with the greater element specified by i
    (array[i + 1], array[high]) = (array[high], array[i + 1])
 
    # Return the position from where partition is done
    return i + 1

def quicksort(array, low, high):
    if low < high:
 
        # Find pivot element such that
        # element smaller than pivot are on the left
        # element greater than pivot are on the right
        pi = partition(array, low, high)
 
        # Recursive call on the left of pivot
        quicksort(array, low, pi - 1)
 
        # Recursive call on the right of pivot
        quicksort(array, pi + 1, high)

def learned_partition(array, low, high, order_func):
    pivot = array[high]
 
    # pointer for greater element
    i = low - 1
 
    for j in range(low, high):
        if order_func(array[j], pivot) >= 0:
            # If element smaller than pivot is found
            # swap it with the greater element pointed by i
            i = i + 1
 
            # Swapping element at i with element at j
            (array[i], array[j]) = (array[j], array[i])
 
    # Swap the pivot element with the greater element specified by i
    (array[i + 1], array[high]) = (array[high], array[i + 1])
 
    # Return the position from where partition is done
    return i + 1

def learned_quicksort(array, low, high, order_func):
    if low < high:
 
        # Find pivot element such that
        # element smaller than pivot are on the left
        # element greater than pivot are on the right
        pi = learned_partition(array, low, high, order_func)
 
        # Recursive call on the left of pivot
        learned_quicksort(array, low, pi - 1, order_func)
 
        # Recursive call on the right of pivot
        learned_quicksort(array, pi + 1, high, order_func)


seqs = [
    'a b c d'.split(), 
    'c e f'.split(),
    'a c d'.split(),
]
ord = Orderer(strict=True)
ord.update(seqs)

print(ord.order('a','b'), 1)

test_array = 'f e d c b a'.split()
print(learned_quicksort(test_array,0,5,ord.order))
print(learned_quicksort(test_array,0,5,ord.fractional_order))