http://en.wikipedia.org/wiki/Sorting_network
The sorting network it found for 12 items is close to what's been proven optimal, it took 43 steps instead of the proven optimal betweeen 37 and 39...
[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [10, 11], [0, 2], [1, 3], [1, 2], [4, 6], [5, 7], [5, 6], [8, 10],[9, 11], [9, 10], [0, 4], [1, 5], [2, 6], [3, 7], [1, 4], [2, 4], [3, 5], [3, 4], [5, 6], [0, 8], [1, 9], [2, 10], [3, 11], [1, 8], [2, 8], [3, 9], [4, 10], [5, 11], [3, 8], [4, 8], [5, 9], [6, 10], [7, 11], [5, 8], [6, 8], [7, 9], [7, 8], [9, 10]]
A slight modification of the code found one with one more step (44) but one less depth, for a depth of 9:
[[10, 11], [8, 9], [6, 7], [4, 5], [2, 3], [0, 1], [9, 11], [8, 10], [9, 10], [5, 7], [4, 6], [5, 6], [1, 3], [0, 2], [1, 2], [7, 11], [6, 10], [5, 9], [4, 8], [7, 10], [7, 9], [6, 8], [7, 8], [5, 6], [3, 11], [2, 10], [1, 9], [0, 8], [3, 10], [3, 9], [2, 8], [1, 7], [0, 6], [3, 8], [3, 7], [2, 6], [1, 5], [0, 4], [3, 6], [3, 5], [2, 4], [3, 4], [1, 2], [10, 11]]
I found that one with 64 comparators and depth of 10 could be found by "seeding" the process with these starting values that I had kind of seen the pattern of in the above results:
Seed Values: [[15, 14], [13, 12], [11, 10], [9, 8], [7, 6], [5, 4], [3, 2], [1, 0], [15, 13], [14, 12], [11, 9], [10, 8], [7, 5], [6, 4], [3, 1], [2, 0]]
And the whole network:
[[15, 14], [13, 12], [11, 10], [9, 8], [7, 6], [5, 4], [3, 2], [1, 0], [15, 13], [14, 12], [11, 9], [10, 8], [7, 5], [6, 4], [3, 1], [2, 0], [13, 14], [9, 10], [5, 6], [1, 2], [11, 15], [9, 13], [10, 14], [8, 12], [10, 15], [8, 13], [13, 14], [9, 10], [8, 15], [3, 7], [1, 5], [2, 6], [0, 4], [2, 7], [0, 5], [5, 6], [1, 2], [0, 7], [7, 15], [5, 13], [6, 14], [4, 12], [0, 8], [2, 10], [1, 9], [3, 11], [7, 11], [5, 9], [6, 10], [4, 8], [10, 15], [8, 13], [4, 9], [6, 11], [0, 5], [2, 7], [13, 14], [9, 10], [8, 15], [5, 6], [4, 11], [1, 2], [0, 7], [14, 15]]
The concept is that you start with a list A of every unique string of a certain length pf 0's and 1's and you provisionally try every possible pairwise swap on that list and find the swap that after that swap is done on every element of A (making a list B of strings of 1's and 0's) has the greatest intersection of A and B, meaning the most strings are the same between the two. The union becomes the new A and iterated. The greatest intersection also means it has the smallest union, so the idea is that this union will generally be smaller than A. I found that there is a non-zero intersection (And smaller union!) all the way until you end up with L lists of length L each one a sorted version of the L possible initial weights (where each 1 in the initial string is adding one to the weight). This means every possible list has been mapped to one of those lists via the swapping and thus all the lists can be sorted with those swaps. By the One-Zero principle it means every list of L sortable items can be sorted just as well with those swaps...
I know this isn't explained well in words but the code is fairly simple and works fairly quickly even written in single threaded python finding the network above only took a couple of minutes...
***Source Code***
import random
def copy(a):
a1 = []
for e in a:
a1.append(e)
return a1
def cullswap(s, sw):
t = []
for n in range(0, len(s)):
a = copy(s[n])
if s[n][sw[0]] > s[n][sw[1]]:
swap(a, sw[0], sw[1])
if finddupe(a, n, s) == False:
t.append(a)
else:
t.append(s[n])
return t
def swap(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def finddupe(a, n, s):
for e in range(0, len(s)):
if s[e] == a and e != n:
return True
return False
def bestswap(s):
best = 0
bestij = []
for i in range(0, len(s[0])-1):
for j in range(i+1, len(s[0])):
count = 0
for n in range(0, len(s)):
if s[n][i] > s[n][j]:
a = copy(s[n])
swap(a, i, j)
if finddupe(a, n, s) == True:
count +=1
if count > best:
best = count
bestij = [i,j]
return bestij, best
def addelement(s,a, listlength):
if len(a) < listlength:
a1 = copy(a)
a1.append(0)
addelement(s, a1, listlength)
a2 = copy(a)
a2.append(1)
addelement(s, a2, listlength)
else:
s.append(a)
def main():
listlength = 12
s = []
addelement(s, [], listlength)
swaps = []
i = 0
while(len(s) > 0):
swap, best = bestswap(s)
i+=1
print(i, swap)
swaps.append(swap)
if best == 0:
break
s = cullswap(s, swap)
print(swaps, len(swaps))
main()
** Slower, but Depth optimizing source code**
import random
def copy(a):
a1 = []
for e in a:
a1.append(e)
return a1
def cullswap(s, sw):
t = []
for n in range(0, len(s)):
a = copy(s[n])
if s[n][sw[0]] > s[n][sw[1]]:
swap(a, sw[0], sw[1])
if finddupe(a, n, s) == False:
t.append(a)
else:
t.append(s[n])
return t
def swap(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def finddupe(a, n, s):
for e in range(0, len(s)):
if s[e] == a and e != n:
return True
return False
def finddepth(swaps, newswap):
for k in range(len(swaps)-1, 0, -1):
if swaps[k][0] == newswap[0] or swaps[k][0] == newswap[1] or swaps[k][1] == newswap[0] or swaps[k][1] == newswap[1]:
return len(swaps)-k
return len(swaps)
def bestswap(s, swaps):
best = 0
bestij = []
for i in range(0, len(s[0])-1):
for j in range(i+1, len(s[0])):
count = 0
d = -1
for n in range(0, len(s)):
if s[n][i] > s[n][j]:
a = copy(s[n])
swap(a, i, j)
if finddupe(a, n, s) == True:
count +=1
if count >= best:
f = finddepth(swaps, [i,j])
if f > d:
d = f
best = count
bestij = [i,j]
return bestij, best
def addelement(s,a, listlength):
if len(a) < listlength:
a1 = copy(a)
a1.append(0)
addelement(s, a1, listlength)
a2 = copy(a)
a2.append(1)
addelement(s, a2, listlength)
else:
s.append(a)
def main():
listlength = 14
s = []
addelement(s, [], listlength)
swaps = []
i = 0
while(len(s) > 0):
swap, best = bestswap(s, swaps)
i+=1
print(i, swap)
swaps.append(swap)
if best == 0:
break
s = cullswap(s, swap)
print(swaps, len(swaps))
main()
**Code for starting with a certain "seeding" network**
import random
def copy(a):
a1 = []
for e in a:
a1.append(e)
return a1
def cullswap(s, sw):
t = []
for n in range(0, len(s)):
a = copy(s[n])
if s[n][sw[0]] > s[n][sw[1]]:
swap(a, sw[0], sw[1])
if finddupe(a, n, s) == False:
t.append(a)
else:
t.append(s[n])
return t
def swap(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def finddupe(a, n, s):
for e in range(0, len(s)):
if s[e] == a and e != n:
return True
return False
def finddepth(swaps, newswap):
for k in range(len(swaps)-1, 0, -1):
if swaps[k][0] == newswap[0] or swaps[k][0] == newswap[1] or swaps[k][1] == newswap[0] or swaps[k][1] == newswap[1]:
return len(swaps)-k
return len(swaps)
def bestswap(s, swaps, starter):
best = 0
bestij = []
if len(swaps) < len(starter):
return starter[len(swaps)], 1
for i in range(0, len(s[0])-1):
for j in range(i+1, len(s[0])):
count = 0
d = -1
for n in range(0, len(s)):
if s[n][i] > s[n][j]:
a = copy(s[n])
swap(a, i, j)
if finddupe(a, n, s) == True:
count +=1
if count >= best:
f = finddepth(swaps, [i,j])
if f > d:
d = f
best = count
bestij = [i,j]
return bestij, best
def addelement(s,a, listlength):
if len(a) < listlength:
a1 = copy(a)
a1.append(0)
addelement(s, a1, listlength)
a2 = copy(a)
a2.append(1)
addelement(s, a2, listlength)
else:
s.append(a)
def main():
listlength = 16
s = []
addelement(s, [], listlength)
starter = [[15,14],[13,12],[11,10],[9,8],[7,6],[5,4],[3,2],[1,0], [15,13],[11,9],[7,5],[3,1],[4,0], [5,1],[6,2],[7,3],[8,12],[9,13],[10,14],[11,15]]
swaps = []
i = 0
while(len(s) > 0):
swap, best = bestswap(s, swaps, starter)
i+=1
print(i, swap)
swaps.append(swap)
if best == 0:
break
s = cullswap(s, swap)
print(swaps, len(swaps))
main()
No comments:
Post a Comment