Алгоритм сортировки пар чисел

Ответ 1

O (n log n) решение

Ответ 2

Пусть S (n) равно всем действительным порядкам сортировки, где n соответствует парам, включенным [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)

Пара может быть вставлена ​​в порядок максимум двумя способами (нормальная пара и обратная пара).

Maximum orderings = O(2^n)

Я не очень уверен в этом амортизированном порядке, но выслушаю меня.

Для заказа и пары у нас есть четыре способа сортировки заказов после вставки (два порядка, один (нормальный), один (обратный), нуль)

Нет порядков (Амортизировано) = (1/4) * 2 + (1/4) * 1 + (1/4) * 1 + (1/4) * 0 = 1

 Amortized orderings = O(1)

Аналогично, сложность времени будет O (n ^ 2), снова не уверен. Следующая программа находит упорядочения с использованием варианта сортировки Insertion.

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"

Вывод:

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)]

Ответ 3

Это забавная проблема. Я придумал решение Tom самостоятельно, здесь мой код Python:

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

Один важный момент, не упомянутый в решении Tom, заключается в том, что на этапе сортировки, если меньшие значения любых двух пар одинаковы, вы должны отсортировать, уменьшив значение большего элемента.

Мне потребовалось много времени, чтобы понять, почему неудача должна указывать на отсутствие решения; мой исходный код имел откат.

Ответ 4

Обновление: этот вопрос больше недействителен, поскольку вопрос был изменен

Разделить вектор пар в ведра по первому числу. Убирайте сортировку по каждому ковшу. Объедините ведра в порядке возрастания первых чисел и отслеживайте второе число последней пары. Если оно больше текущего, то нет решения. В противном случае вы получите решение после завершения слияния.

Если у вас есть стабильный алгоритм сортировки, вы можете сортировать по убыванию по второму числу, а затем по возрастанию сортировать по первому числу. После этого проверьте, сохраняются ли остальные числа в порядке убывания.

Ответ 5

Ниже представлен простой рекурсивный алгоритм поиска по глубине в 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)])

Он поддерживает отсортированную подпоследовательность (partial) и пытается присоединить каждую оставшуюся пару к ней как в оригинале, так и в обратном порядке, не нарушая условий сортировки.

При желании алгоритм можно легко изменить, чтобы найти все допустимые порядки сортировки.

Изменить: я подозреваю, что алгоритм может быть существенно улучшен за счет сохранения двух частично отсортированных последовательностей (префикс и суффикс). Я думаю, что это позволило бы выбрать следующий элемент детерминированным способом, а не пытаться использовать все возможные элементы. К сожалению, у меня нет времени, чтобы подумать об этом.

Ответ 6

Обмен в вашем случае - это всего лишь двухэлементный массив. так что вы можете tuple [] = (4,6), (1,5), (7,1), (8,6),...

• для каждого кортежа → сортировать внутренний список

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

• сортировать кортеж на 1-й asc

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

• сортировать кортеж на 1nd desc

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

Ответ 7

Первое, что я заметил, это отсутствие решения, если оба значения в одном кортеже больше, чем оба значения в любом другом кортеже.

Следующее, что я замечаю, состоит в том, что кортежи с небольшой разницей сортируются по середине, а разноцветные переполнения сортируются по концам.

С помощью этих двух частей информации вы сможете найти разумное решение.

Фаза 1: Сортируйте каждый кортеж, перемещая сначала меньшее значение.

Этап 2. Сортировка списка кортежей; сначала в порядке убывания разницы между двумя значениями каждого кортежа, затем сортируйте каждую группу одинаковой разницы в порядке возрастания первого члена каждого кортежа. (1,6), (2,7), (3,8), (4,4), (5,5).)

Этап 3: Проверьте исключения. 1: Найдите пару кортежей, где оба элемента одного кортежа больше, чем оба элемента другого кортежа. (Например, (4,4), (5,5).) 2: Если есть четыре или более кортежей, посмотрите в каждую группу кортежей с одинаковой разницей для трех или более вариаций (например, (1,6), (2,7), (3,8)).

Этап 4: Переупорядочить кортежи. Начиная с задней части (кортежи с наименьшей разницей), вторая вариация внутри каждой группировки кортежей с равной разницей должна иметь свои элементы, а их кортежи добавлены в конец списка. (1,6), (2,7), (5,5) = > (2,7), (5,5), (6,1).)

Я думаю, что это должно его покрыть.

Ответ 8

Это очень интересный вопрос. Вот мое решение для него в 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

Вход

1 5
2 3
3 3
3 4
2 4

Производит вывод

1 5
2 4
2 3
3 4
3 3

и

3 5
6 6
7 4

Выходы

Not Nossible

Комментарии

Я нашел эту проблему довольно сложной. Мне потребовалось около 15 минут, чтобы придумать решение и час или около того, чтобы написать и отладить его. Код завален комментариями, чтобы каждый мог следовать за ним.