Пусть 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), опять же не уверен.Следующая программа находит заказы, используя вариант сортировки вставок.
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)]