algorithm - purposes - Algoritmo para ordenar pares de números

max hashtags instagram 2018

Question

Tengo un problema y necesito ayuda de las mentes brillantes de SO. Tengo N pares de integradores sin firmar. Necesito ordenarlos. El vector final de los pares debe ordenarse cada vez más por el primer número en cada par y no por el segundo en cada par. Cada par puede tener el primero y el segundo elemento intercambiados entre sí. A veces no hay solución, entonces tengo que lanzar una excepción.

Ejemplo:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-- swapped
8 3     <-- swapped

^^ Sin intercambiar pares, es imposible construir la solución. Así que intercambiamos pares (7, 1), (3, 8) y (5, 6) y construimos el resultado. o

in pairs:
1 5
6 9

out:
not possible

Un ejemplo más que muestra cómo ''ordenar pares'' primero no es la solución.

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

Gracias

Answer 1

A continuación se muestra un algoritmo de búsqueda de profundidad recursiva simple simple en 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)])

Mantiene una subsecuencia ordenada ( partial ) e intenta agregar todos los pares restantes tanto en el original como en el orden inverso, sin violar las condiciones del género.

Si lo desea, el algoritmo puede cambiarse fácilmente para encontrar todos los órdenes de clasificación válidos.

Editar: sospecho que el algoritmo puede mejorarse sustancialmente manteniendo dos secuencias parcialmente ordenadas (un prefijo y un sufijo). Creo que esto permitiría que el siguiente elemento se pueda elegir de manera determinista en lugar de intentar todos los elementos posibles. Lamentablemente, no tengo tiempo ahora para pensar en esto.

Answer 2

El intercambio en su caso es solo una especie de matriz de 2 elementos. para que pueda tuplar [] = (4,6), (1,5), (7,1), (8,6), ...

1. para cada tupla -> ordena la lista interna

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

1. ordenar tupla por 1st asc

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

1. ordenar tupla por 1ª desc

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

Answer 3

Esta es una pregunta muy interesante. Aquí está mi solución en 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

La entrada

1 5 2 3 3 3 3 4 2 4

Produce la salida

1 5 2 4 2 3 3 4 3 3

Y

3 5 6 6 7 4

Salidas

Not Nossible

Comentarios

Encontré este problema bastante desafiante. Me llevó unos 15 minutos encontrar una solución y una hora más o menos para escribirla y depurarla. El código está lleno de comentarios para que cualquiera pueda seguirlo.

Answer 4

Este es un problema divertido. Se me ocurrió la solución de Tom de forma independiente, aquí está mi código de 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

Un punto importante que no se menciona en la solución de Tom es que en la etapa de clasificación, si los valores menores de dos pares son iguales, debe ordenar por el valor decreciente del elemento mayor.

Me tomó mucho tiempo descubrir por qué una falla debe indicar que no hay solución; mi código original había retrocedido.

Answer 5

Lo primero que noto es que no hay solución si ambos valores en una tupla son más grandes que ambos valores en cualquier otra tupla.

Lo siguiente que noto es que las tuplas con una pequeña diferencia se ordenan hacia la mitad, y las tupples con grandes diferencias se ordenan hacia los extremos.

Con estas dos piezas de información, debería poder encontrar una solución razonable.

Fase 1: Clasifica cada tupla moviendo primero el valor más pequeño.

Fase 2: ordena la lista de tuplas; primero en orden descendente de la diferencia entre los dos valores de cada tupla, luego ordena cada grupo de igual diferencia en orden ascendente del primer miembro de cada tupla. (Ej. (1,6), (2,7), (3,8), (4,4), (5,5).)

Fase 3: verificar excepciones. 1: Busque un par de tuplas donde ambos elementos de una tupla sean más grandes que los dos elementos de la otra tupla. (Ej. (4,4), (5,5).) 2: Si hay cuatro o más tuplas, busque dentro de cada grupo de tuplas la misma diferencia para tres o más variaciones (Ej. (1,6) , (2,7), (3,8).)

Fase 4: Reorganizar las tuplas. Comenzando en el extremo posterior (tuplas con la diferencia más pequeña), la segunda variación dentro de cada agrupación de tuplas con la misma diferencia debe tener sus elementos intercambiados y las tuplas agregadas al final de la lista. (Ej. (1,6), (2,7), (5,5) => (2,7), (5,5), (6,1).)

Creo que esto debería cubrirlo.

Answer 6

Sea S (n) igual a todos los ordenamientos válidos, donde n corresponde a los pares incluidos [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)

Un par se puede insertar en una orden en un máximo de dos formas (par normal y par invertido).

Maximum orderings = O(2^n)

No estoy muy seguro de este orden amortizado, pero escúchame.

Para un pedido y un par, tenemos cuatro formas de obtener pedidos ordenados después de las inserciones (dos pedidos, uno (normal), uno (invertido), cero)

No de pedidos (Amortizado) = (1/4) * 2 + (1/4) * 1 + (1/4) * 1 + (1/4) * 0 = 1

 Amortized orderings = O(1)

De manera similar, la complejidad del tiempo será O (n ^ 2), nuevamente no estoy seguro. El siguiente programa encuentra ordenamientos usando una variante de ordenación por inserción.

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"

Salida:

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

Answer 7

Solución O (n log n)

Answer 8

Actualización: esta respuesta ya no es válida desde que se cambió la pregunta

Dividir el vector de pares en cubos por el primer número. Haz una ordenación descendente en cada cubo. Fusiona los segmentos en orden ascendente de los primeros números y realiza un seguimiento del segundo número del último par. Si es mayor que el actual, no hay solución. De lo contrario, obtendrás una solución después de que se complete la fusión.

Si tiene un algoritmo de clasificación estable, puede hacer una ordenación descendente por segundo número y luego ordenar ascendentemente por el primer número. Después de eso, comprueba si los segundos números siguen en orden descendente.