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 """ def GDC_TBS(perm): """ Returns the cost to sort perm using TBS as the binary sorting sequence. (GenericDivideConquer_TripartiteBinarySort) """ 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): """Routes the given permutation using reversals. Returns the reversals""" j = max(L) return permutationsort_divideconquer_tbs(L, 0, j) def permutationsort_divideconquer_tbs(L, i=None, j=None): """ 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. """ # Set default params if i == None: i = min(L) if j == None: j = max(L) 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")