-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathproblem-3
141 lines (93 loc) · 3.61 KB
/
problem-3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 15 09:25:56 2014
@author: rm
"""
import itertools
b = [3, 4, 6, 5, 8, 7, 1, 2]
def findBreakpoints(l):
'''
input: the list
output: #breakpoints
'''
newlist = [0]
for i in l:
newlist.append(i)
newlist.append(len(l)+1)
# print newlist
count= 0
indexList = []
increasingStripPresent = False
for i in newlist[:-1]:
if newlist[count+1] != i+1 and newlist[count+1] != i-1:
indexList.append(count)
else:
if newlist[count+1] == i+1:
increasingStripPresent = True
count += 1
count = 0
decreasingStripIndex = []
for i in newlist[:-1]:
if newlist[count+1] == i-1 and newlist[count-1] != i-1: #beginning of a decreasing strip
decreasingStripIndex.append(count-1)
if newlist[count+1] != i-1 and newlist[count-1] == i+1:
decreasingStripIndex.append(count-1)
break
count += 1
try:
return len(indexList), increasingStripPresent, [decreasingStripIndex[0], decreasingStripIndex[-1]]
except:
return len(indexList), increasingStripPresent, decreasingStripIndex
def reverseSubset(wholeList, reverseSubset):
'''
reverseSubset is a list, 2 elements long
returns list with reversed segment specified in index list
'''
newlist = []
newlist.extend(reversed(wholeList[reverseSubset[0]:reverseSubset[1]+1]))
outputlist = []
r = range(reverseSubset[0], reverseSubset[1]+1)
count = 0
newlistcount = 0
for i in wholeList:
if count in r:
outputlist.append(newlist[newlistcount])
newlistcount += 1
else:
outputlist.append(i)
count += 1
return outputlist
#
def findOptimalReversalSubmet(wholeList, originalNumberOfBreaks):
'''
input, list to find optimal reversal
returns list with reversed segment specified in index list
'''
r = itertools.combinations(range(0, len(wholeList)), 2)
resultslist = []
for i in r:
q = reverseSubset(wholeList, [i[0], i[1]])
numberOfBreaks, increasingStripPresent, reverseStrip = findBreakpoints(q)
# print numberOfBreaks
resultslist.append((originalNumberOfBreaks - numberOfBreaks))
if (originalNumberOfBreaks - numberOfBreaks) == 2:
return q, numberOfBreaks
r = itertools.combinations(range(0, len(wholeList)), 2)
resultslist = []
for i in r:
q = reverseSubset(wholeList, [i[0], i[1]])
numberOfBreaks, increasingStripPresent, reverseStrip = findBreakpoints(q)
resultslist.append((originalNumberOfBreaks - numberOfBreaks))
if (originalNumberOfBreaks - numberOfBreaks) == 1:
return q, numberOfBreaks
numberOfBreaks, increasingStripPresent, reverseStrip = findBreakpoints(b)
#print numberOfBreaks
while numberOfBreaks > 0:
print b
if increasingStripPresent:
b, numberOfBreaks = findOptimalReversalSubmet(b, numberOfBreaks)
numberOfBreaks, increasingStripPresent, reverseStrip = findBreakpoints(b)
else:
b = reverseSubset(b, reverseStrip)
print b
## ################################### ################################### ################################ mayb#e not optimal since ifax num of BPs not 2 at a iven step,have to chg ose one wih only on oBP removal; this ay not be ,est one