Algorithm to sort pairs of numbers

I am stuck with a problem and I need some help from bright minds of SO. I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped with each other. Sometimes there is no solution, so I need to throw an exception then.

Example:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-开发者_如何学Go- swapped
8 3     <-- swapped

^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result. or

in pairs:
1 5
6 9

out:
not possible

One more example that shows how 'sorting pairs' first isn't the solution.

in pairs:
1 4
2 5
out pairs:
1 4
5 2

Thanks

---

O( n log n ) solution

---

Let S(n) equals all the valid sort orderings, where n corresponds to pairs included [0,n].

S(n) = []
for each order in S(n-1)
   for each combination of n-th pair
      if pair can be inserted in order, add the order after insertion to S(n)
      else don't include the order in S(n)

A pair can be inserted into an order in maximum of two ways(normal pair and reversed pair).

Maximum orderings = O(2^n)

I'm not very sure about this amortized orderings, but hear me out.

For an order and pair we have four ways of getting sorted orders after insertions (two orders, one(normal),one(reversed), zero)

No of orderings (Amortized) = (1/4)*2 + (1/4)*1 + (1/4)*1 + (1/4)*0 = 1

 Amortized orderings = O(1)

Similarly time complexity will be O(n^2), Again not sure. Following program finds orderings using a variant of Insertion sort.

debug = False

(LEFT, RIGHT, ERROR) = range(3)
def position(first, second):
    """ Returns the position of first pair when compared to second """
    x,y = first
    a,b = second
    if x <= a and b <= y:
        return LEFT
    if x >= a and b >= y:
        return RIGHT
    else:
        return ERROR

def insert(pair, order):
    """ A pair can be inserted in normal order or reversed order
     For each order of insertion we will get one solution or none"""
    solutions = []
    paircombinations = [pair]
    if pair[0] != pair[1]: # reverse and normal order are distinct
        paircombinations.append(pair[::-1])

    for _pair in paircombinations:
        insertat = 0
        if debug: print "Inserting", _pair, 
        for i,p in enumerate(order):
            pos = position(_pair, p)
            if pos == LEFT:
                break
            elif pos == RIGHT:
                insertat += 1
            else:
                if debug: print "into", order,"is not possible"
                insertat = None
                break
        if insertat != None:
            if debug: print "at",insertat,"in", order
            solutions.append(order[0:insertat] + [_pair] + order[insertat:])
    return solutions


def swapsort(pairs):
    """
    Finds all the solutions of pairs such that ending vector
    of pairs are be sorted non decreasingly by the first number in
    each pair and non increasingly by the second in each pair.
    """
    solutions = [ pairs[0:1] ] # Solution first pair
    for pair in pairs[1:]:
        # Pair that needs to be inserted into solutions
        newsolutions = []
        for solution in solutions:
            sols = insert(pair, solution) # solutions after inserting pair
            if sols:
                newsolutions.extend(sols)
        if newsolutions:
            solutions = newsolutions
        else:
            return None
    return solutions

if __name__ == "__main__":
    groups = [ [(1,5), (7,1), (3,8), (5,6)],
               [(1,5), (2,3), (3,3), (3,4), (2,4)],
               [(3,5), (6,6), (7,4)],
               [(1,4), (2,5)] ]
    for pairs in groups:
        print "Solutions for",pairs,":"
        solutions = swapsort(pairs)
        if solutions:
            for sol in solutions:
                print sol
        else:
            print "not possible"

Output:

Solutions for [(1, 5), (7, 1), (3, 8), (5, 6)] :
[(1, 7), (1, 5), (6, 5), (8, 3)]
Solutions for [(1, 5), (2, 3), (3, 3), (3, 4), (2, 4)] :
[(1, 5), (2, 4), (2, 3), (3, 3), (4, 3)]
[(1, 5), (2, 3), (3, 3), (4, 3), (4, 2)]
[(1, 5), (2, 4), (3, 4), (3, 3), (3, 2)]
[(1, 5), (3, 4), (3, 3), (3, 2), (4, 2)]
Solutions for [(3, 5), (6, 6), (7, 4)] :
not possible
Solutions for [(1, 4), (2, 5)] :
[(1, 4), (5, 2)]

---

This is a fun problem. I came up with Tom's solution independently, here's my Python code:

class UnableToAddPair:
    pass

def rcmp(i,j):
    c = cmp(i[0],j[0])
    if c == 0:
        return -cmp(i[1],j[1])
    return c

def order(pairs):
    pairs = [list(x) for x in pairs]
    for x in pairs:
        x.sort()
    pairs.sort(rcmp)
    top, bottom = [], []
    for p in pairs:
        if len(top) == 0 or p[1] <= top[-1][1]:
            top += [p]
        elif len(bottom) == 0 or p[1] <= bottom[-1][1]:
            bottom += [p]
        else:
            raise UnableToAddPair
    bottom = [[x[1],x[0]] for x in bottom]
    bottom.reverse()
    print top + bottom

One important point not mentioned in Tom's solution is that in the sorting stage, if the lesser values of any two pairs are the same, you have to sort by decreasing value of the greater element.

It took me a long time to figure out why a failure must indicate that there's no solution; my original code had backtracking.

---

Below is a simple recursive depth-first search algorithm in Python:

import sys

def try_sort(seq, minx, maxy, partial):
  if len(seq) == 0: return partial
  for i, (x, y) in enumerate(seq):
    if x >= minx and y <= maxy:
      ret = try_sort(seq[:i] + seq[i+1:], x, y, partial + [(x, y)])
      if ret is not None: return ret
    if y >= minx and x <= maxy:
      ret = try_sort(seq[:i] + seq[i+1:], y, x, partial + [(y, x)])
      if ret is not None: return ret
  return None

def do_sort(seq):
  ret = try_sort(seq, -sys.maxint-1, sys.maxint, [])
  print ret if ret is not None else "not possible"

do_sort([(1,5), (7,1), (3,8), (5,6)])
do_sort([(1,5), (2,9)])
do_sort([(3,5), (6,6), (7,4)])

It maintains a sorted subsequence (partial) and tries to append every remaining pair to it both in the original and in the reversed order, without violating the conditions of the sort.

If desired, the algorithm can be easily changed to find all valid sort orders.

Edit: I suspect that the algorithm can be substantially improved by maintaining two partially-sorted sequences (a prefix and a suffix). I think that this would allow the next element can be chosen deterministically instead of trying all possible elements. Unfortunately, I don't have time right now to think this through.

---

Update: this answer is no longer valid since question was changed

Split vector of pairs into buckets by first number. Do descending sort on each bucket. Merge buckets in ascending order of first numbers and keep track of second number of last pair. If it's greater than current one there is no solution. Otherwise you will get solution after merge is done.

If you have stable sorting algorithm you can do descending sort by second number and then ascending sort by first number. After that check if second numbers are still in descending order.

---

The swapping in your case is just a sort of a 2-element array. so you can tuple[] = (4,6),(1,5),(7,1),(8,6), ...

1. for each tuple -> sort internal list

=> (4,6),(1,5),(1,7),(6,8)

1. sort tuple by 1st asc

=> (1,5),(1,7),(4,6),(6,8)

1. sort tuple by 1nd desc

=> (1,7),(1,5),(4,6),(6,8)

---

The first thing I notice is that there is no solution if both values in one tuple are larger than both values in any other tuple.

The next thing I notice is that tuples with a small difference become sorted towards the middle, and tupples with large differences become sorted towards the ends.

With these two pieces of information you should be able to figure out a reasonable solution.

Phase 1: Sort each tuple moving the smaller value first.

Phase 2: Sort the list of tuples; first in descending order of the difference between the two values of each tuple, then sort each grouping of equal difference in ascending order of the first member of each tuple. (Eg. (1,6),(2,7),(3,8),(4,4),(5,5).)

Phase 3: Check for exceptions. 1: Look for a pair of tuples where both elements of one tuple are larger than both elements of the other tuple. (Eg. (4,4),(5,5).) 2: If there are four or more tuples, then look within each group of tuples with the same difference for three or more variations (Eg. (1,6),(2,7),(3,8).)

Phase 4: Rearrange tuples. Starting at the back end (tuples with smallest difference), the second variation within each grouping of tuples with equal difference must have their elements swapped and the tuples appended to the back of the list. (Eg. (1,6),(2,7),(5,5) => (2,7),(5,5),(6,1).)

I think this should cover it.

---

This is a very interesting question. Here is my solution to it in VB.NET.

Module Module1

    Sub Main()
        Dim input = {Tuple.Create(1, 5),
                     Tuple.Create(2, 3),
                     Tuple.Create(3, 3),
                     Tuple.Create(3, 4),
                     Tuple.Create(2, 4)}.ToList

        Console.WriteLine(Solve(input))
        Console.ReadLine()
    End Sub

    Private Function Solve(ByVal input As List(Of Tuple(Of Integer, Integer))) As String
        Dim splitItems As New List(Of Tuple(Of Integer, Integer))
        Dim removedSplits As New List(Of Tuple(Of Integer, Integer))
        Dim output As New List(Of Tuple(Of Integer, Integer))
        Dim otherPair = Function(indexToFind As Integer, startPos As Integer) splitItems.FindIndex(startPos, Function(x) x.Item2 = indexToFind)
        Dim otherPairBackwards = Function(indexToFind As Integer, endPos As Integer) splitItems.FindLastIndex(endPos, Function(x) x.Item2 = indexToFind)

        'split the input while preserving their indices in the Item2 property
        For i = 0 To input.Count - 1
            splitItems.Add(Tuple.Create(input(i).Item1, i))
            splitItems.Add(Tuple.Create(input(i).Item2, i))
        Next

        'then sort the split input ascending order
        splitItems.Sort(Function(x, y) x.Item1.CompareTo(y.Item1))

        'find the distinct values in the input (which is pre-sorted)
        Dim distincts = splitItems.Select(Function(x) x.Item1).Distinct

        Dim dIndex = 0
        Dim lastX = -1, lastY = -1

        'go through the distinct values one by one
        Do While dIndex < distincts.Count
            Dim d = distincts(dIndex)

            'temporary list to store the output for the current distinct number
            Dim temOutput As New List(Of Tuple(Of Integer, Integer))

            'go through each of the split items and look for the current distinct number
            Dim curIndex = 0, endIndex = splitItems.Count - 1
            Do While curIndex <= endIndex
                If splitItems(curIndex).Item1 = d Then
                    'find the pair of the item
                    Dim pairIndex = otherPair(splitItems(curIndex).Item2, curIndex + 1)
                    If pairIndex = -1 Then pairIndex = otherPairBackwards(splitItems(curIndex).Item2, curIndex - 1)

                    'create a pair and add it to the temporary output list
                    temOutput.Add(Tuple.Create(splitItems(curIndex).Item1, splitItems(pairIndex).Item1))

                    'push the items onto the temporary storage and remove it from the split list
                    removedSplits.Add(splitItems(curIndex))
                    removedSplits.Add(splitItems(pairIndex))
                    If curIndex > pairIndex Then
                        splitItems.RemoveAt(curIndex)
                        splitItems.RemoveAt(pairIndex)
                    Else
                        splitItems.RemoveAt(pairIndex)
                        splitItems.RemoveAt(curIndex)
                    End If
                    endIndex -= 2
                Else
                    'increment the index or exit the iteration as appropriate
                    If splitItems(curIndex).Item1 <= d Then curIndex += 1 Else Exit Do
                End If
            Loop

            'sort temporary output by the second item and add to the main output
            output.AddRange(From r In temOutput Order By r.Item2 Descending)

            'ensure that the entire list is properly ordered
            'start at the first item that was added from the temporary output
            For i = output.Count - temOutput.Count To output.Count - 1
                Dim r = output(i)
                If lastX = -1 Then
                    lastX = r.Item1
                ElseIf lastX > r.Item1 Then
                    '!+ It appears this section of the if statement is unnecessary
                    'sorting on the first column is out of order so remove the temporary list
                    'and send the items in the temporary list back to the split items list
                    output.RemoveRange(output.Count - temOutput.Count, temOutput.Count)
                    splitItems.AddRange(removedSplits)
                    splitItems.Sort(Function(x, y) x.Item1.CompareTo(y.Item1))
                    dIndex += 1
                    Exit For
                End If
                If lastY = -1 Then
                    lastY = r.Item2
                ElseIf lastY < r.Item2 Then
                    'sorting on the second column is out of order so remove the temporary list
                    'and send the items in the temporary list back to the split items list
                    output.RemoveRange(output.Count - temOutput.Count, temOutput.Count)
                    splitItems.AddRange(removedSplits)
                    splitItems.Sort(Function(x, y) x.Item1.CompareTo(y.Item1))
                    dIndex += 1
                    Exit For
                End If
            Next
            removedSplits.Clear()
        Loop

        If splitItems.Count = 0 Then
            Dim result As New Text.StringBuilder()
            For Each r In output
                result.AppendLine(r.Item1 & " " & r.Item2)
            Next

            Return result.ToString

        Else
            Return "Not Possible"
        End If
    End Function

    <DebuggerStepThrough()> _
    Public Class Tuple(Of T1, T2)
        Implements IEqualityComparer(Of Tuple(Of T1, T2))

        Public Property Item1() As T1
            Get
                Return _first
            End Get
            Private Set(ByVal value As T1)
                _first = value
            End Set
        End Property
        Private _first As T1

        Public Property Item2() As T2
            Get
                Return _second
            End Get
            Private Set(ByVal value As T2)
                _second = value
            End Set
        End Property
        Private _second As T2

        Public Sub New(ByVal item1 As T1, ByVal item2 As T2)
            _first = item1
            _second = item2
        End Sub

        Public Overloads Function Equals(ByVal x As Tuple(Of T1, T2), ByVal y As Tuple(Of T1, T2)) As Boolean Implements IEqualityComparer(Of Tuple(Of T1, T2)).Equals
            Return EqualityComparer(Of T1).[Default].Equals(x.Item1, y.Item1) AndAlso EqualityComparer(Of T2).[Default].Equals(x.Item2, y.Item2)
        End Function

        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            Return TypeOf obj Is Tuple(Of T1, T2) AndAlso Equals(Me, DirectCast(obj, Tuple(Of T1, T2)))
        End Function

        Public Overloads Function GetHashCode(ByVal obj As Tuple(Of T1, T2)) As Integer Implements IEqualityComparer(Of Tuple(Of T1, T2)).GetHashCode
            Return EqualityComparer(Of T1).[Default].GetHashCode(Item1) Xor EqualityComparer(Of T2).[Default].GetHashCode(Item2)
        End Function
    End Class

    Public MustInherit Class Tuple
        <DebuggerStepThrough()> _
        Public Shared Function Create(Of T1, T2)(ByVal first As T1, ByVal second As T2) As Tuple(Of T1, T2)
            Return New Tuple(Of T1, T2)(first, second)
        End Function
    End Class

End Module

The input

1 5
2 3
3 3
3 4
2 4

Produces the output

1 5
2 4
2 3
3 4
3 3

And

3 5
6 6
7 4

Outputs

Not Nossible

Comments

I found this problem quite challenging. It took me some 15 minutes to come up with with a solution and an hour or so to write and debug it. The code is littered with comments so that anyone can follow it.