TripartiteBinarySort.py 4.14 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
import SBR
import math
import itertools
import random
from itertools import permutations

"""
TripartiteBinarySort.py -- Implementation of the TBS algorithm for sorting bitstrings and permutations,
along with a couple testing/analysis functions
"""

Hrishee Shastri's avatar
Hrishee Shastri committed
12
def GDC_TBS(perm):
13
    """
Hrishee Shastri's avatar
Hrishee Shastri committed
14
15
    Returns the cost to sort perm using TBS as the binary sorting sequence.
    (GenericDivideConquer_TripartiteBinarySort)
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
142
143
144
145
146
147
148
149
    """
    revlist = permutationsort_divideconquer_tbs(perm, 0, len(perm) - 1)
    cost = SBR.compress_reversals(revlist, len(perm)) / 3
    return cost


def tripartite_binary_sort(T, i, j):
    """
    Performs TBS (binary version) on T[i,j] inclusive, returns list of reversals
    """
    if all(T[ind] <= T[ind + 1] for ind in range(i, j)):
        return []
    part1, part2 = (2 * i + j) // 3, (i + 2 * j) // 3
    revlist = []
    revlist += tripartite_binary_sort(T, i, part1)
    flipbits(T, part1 + 1, part2)
    revlist += tripartite_binary_sort(T, part1 + 1, part2)
    flipbits(T, part1 + 1, part2)
    revlist += tripartite_binary_sort(T, part2 + 1, j)
    oneind, zerind = zero_one_indices(T, i, j)
    if oneind < zerind:
        rev = SBR.Reversal(oneind, zerind)
        SBR.reverse(T, rev)
        revlist.append(rev)
    return revlist

def flipbits(T, i, j):
    for index in range(i,j+1):
        T[index] = int(not T[index])


def zero_one_indices(T, i, j):
    """
    returns indices of leftmost 1 and rightmost 0 to reverse the segment across
    the median
    """
    oneind = -1
    zerind = -1
    # Find leftmost 1
    for ind in range(i, j+1):
        if T[ind] == 1:
            oneind = ind
            break
    # Find rightmost 0
    for ind in range(j, i-1, -1):
        if T[ind] == 0:
            zerind = ind
            break
    return oneind, zerind

def perm_to_01(L, i, j):
    """
    TUrns a permutation L[i:j] into a permutation of 0s and 1s, where L[i] is 0 if it is
    less than the median and L[i] is 1 if it is greater than the median
    """
    subseq = L[i:j + 1]
    sorted_subseq = sorted(subseq)
    median = (j - i) // 2
    return L[:i] + [int(sorted_subseq.index(k) > median) for k in subseq] + L[j + 1:]

def permutationsort_divideconquer_tbs(L, i, j):
    """
    Sorts the given permutations L from index i to j (inclusive) using a divide and conquer approach. Returns a list of
    reversals used to perform the sort.
    """
    if i == j:
        return []
    T = perm_to_01(L, i, j)
    revs = tripartite_binary_sort(T, i, j)
    m = (i + j) // 2
    SBR.apply_revs(revs, L)
    return revs + permutationsort_divideconquer_tbs(L, i, m) + permutationsort_divideconquer_tbs(L, m + 1, j)



def all_binary_lists_equal(n):
    """
    generates list of lists, where each list is a binary sequence of length n,
    with equal number of 0s and 1s
    """
    def blep(n, b, ct0s, ct1s, lis):
        if len(b) == n:
            if ct1s == n // 2:
                lis.append(b)
            return
        if ct0s == math.ceil(n / 2):
            lis.append(b + [1] * (n - len(b)))
            return
        if ct1s == n // 2:
            lis.append(b + [0] * (n - len(b)))
            return
        blep(n, b + [0], ct0s + 1, ct1s, lis)
        blep(n, b + [1], ct0s, ct1s + 1, lis)
        return

    lis = []
    blep(n, [], 0, 0, lis)
    return lis

def test_binary_sort():
    """
    Testing correctness of sorting bitstrings with TBS.
    """
    wrong = 0
    for i in range(1000):
      l  = [0]*random.randint(100,200) + [1]*random.randint(100,200)
      random.shuffle(l)
      before = l.copy()
      #print(before)
      tripartite_binary_sort(l, 0 , len(l)-1)
      #print(l, '\n')
      if l != sorted(before):
          print("failed")
    print("passed")

def test_perm_sort():
    """
    Testing correctness of sorting permutations with TBS as
    bitstring sorting subroutine. 
    Returns number
    """
    wrong = 0
    n = 1000
    for ct in range(n):
        L = list(range(1,random.randint(5, 200)))
        random.shuffle(L)
        before = L.copy()
        permutationsort_divideconquer_tbs(L,0,len(L)-1)
        #print(before, '\n', L, '\n')
        if L != sorted(before):
            print("failed")
            return 
    print("passed")