Algorithme pour trier les paires de nombres

Question

Je suis coincé avec un problème et j'ai besoin de l'aide de brillants esprits de la SORTE. Je N paires de unsigned integerers. J'ai besoin de les trier. La fin vecteur de paires devraient être triés nondecreasingly par le premier nombre de chaque paire et nonincreasingly par le deuxième de chaque paire. Chaque paire peuvent avoir les premier et deuxième éléments échangés les uns avec les autres. Parfois, il n'y a pas de solution, j'ai donc besoin de lever une exception alors.

Exemple:

in pairs:
1 5
7 1
3 8
5 6

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

^^ Sans changer de paires, il est impossible de construire la solution. Nous avons donc permuter deux (7, 1), (3, 8) et (5, 6) et de construire le résultat. ou

in pairs:
1 5
6 9

out:
not possible

Un exemple de plus qui montre comment " le tri des paires d'abord n'est pas la solution.

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

Merci

Answer 1

Solution O (n log n)

Answer 2

Laissez S(n) est égal à tous les valable rangements, où n correspond à des paires est inclus [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)

Une paire peut être inséré dans un ordre maximal de deux façons(normal paire et d'inverser la paire).

Maximum orderings = O(2^n)

Je ne suis pas très sûr de ce amorti des ordonnancements, mais écoutez-moi.

Pour une commande et une paire nous avons quatre façons d'obtenir des ordres de tri après insertions (deux ordonnances, l'une(normal),un(inversé), zéro)

Pas de rangements (Amorti) = (1/4)*2 + (1/4)*1 + (1/4)*1 + (1/4)*0 = 1

 Amortized orderings = O(1)

De même complexité temporelle O(n^2), là Encore pas sûr. Suivant le programme trouve les achats à l'aide d'une variante de tri d'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"

Sortie:

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 3

C'est un problème amusant. J'ai trouvé la solution de Tom indépendamment, voici mon code 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 point important non mentionné dans la solution de Tom est qu'au stade du tri, si les valeurs inférieures de deux paires sont identiques, vous devez trier par valeur décroissante de l'élément supérieur.

Il m'a fallu beaucoup de temps pour comprendre pourquoi un échec doit indiquer qu'il n'y a pas de solution; mon code d'origine avait fait marche arrière.

Answer 4

Mise à jour: cette réponse n'est plus valide puisque la question a été changé

Vecteur de Split de paires dans des compartiments en premier numéro. Faire un tri décroissant sur chaque compartiment. Fusion des seaux dans l'ordre croissant des premiers numéros et de garder trace de la deuxième numéro de la dernière paire. Si il est plus grand que l'actuel, il n'y a pas de solution. Sinon, vous aurez une solution après la fusion est terminée.

Si vous avez stable algorithme de tri que vous pouvez faire un tri décroissant par le deuxième numéro, puis croissant tri par nombre premier. Après cela, vérifiez si la deuxième chiffres sont encore dans l'ordre décroissant.

Answer 5

Ci-dessous est un simple profondeur de récursivité-premier algorithme de recherche 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)])

Il maintient une triés sous-suite (partial) et essaie d'ajouter toutes les paires restantes à la fois dans l'original et dans l'ordre inverse, sans violer les conditions de la sorte.

Si vous le souhaitez, l'algorithme peut être facilement modifié pour trouver toutes les valide les ordres de tri.

Edit: je soupçonne que l'algorithme peut être sensiblement améliorée par le maintien de deux partiellement-séquences triées (un préfixe et d'un suffixe). Je pense que cela permettrait à l'élément suivant peut être choisi de façon déterministe, au lieu d'essayer tous les éléments possibles. Malheureusement, je n'ai pas le temps maintenant de réfléchir à cela.