-
Notifications
You must be signed in to change notification settings - Fork 0
/
shuffleperm.py
96 lines (83 loc) · 2.51 KB
/
shuffleperm.py
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
from __future__ import print_function
import sys
def height(n):
"""Return the height of an Eytzinger tree of size n"""
h = 0
m = 1
while (m < n):
h += 1
m += 2**h
return h
def eytzinger(i, n):
"""This is the Eytzinger permutation"""
h = height(n)
bottom = n-2**(h-1)
if i % 2 == 0 and i//2 < bottom:
path = i | (1<<h)
else:
path = i | (1<<h-1)
print(path)
def my_outshuffle(i, n):
"""This is the outshuffle permutation we need for Eytzinger layouts"""
if i % 2 == 0:
return n//2+i//2
else:
return i//2
def funny_outshuffle(i, n):
return (my_outshuffle(i, n) + n//2) % n;
def std_inshuffle(i, n):
return (2*(i+1) % (n+1))-1;
def print_cycles(cycles):
print("(" + ")*(".join([",".join([str(x) for x in c])
for c in cycles]) +")")
def print_bin_cycles(cycles):
print("(" + ")*(".join([",".join(["{0:05b}".format(x) for x in c])
for c in cycles]) +")")
def get_cycles(f, n):
"""Get the cycles of the permutation f(0),...,f(n-1)"""
marked = set()
cycles = []
for i in range(n):
if i not in marked:
marked.add(i)
c = [i]
j = f(i, n)
while j != i:
c.append(j)
marked.add(j)
j = f(j, n)
cycles.append(c)
return cycles
def read_cmd_line():
n = -1
if len(sys.argv) == 2:
try:
n = int(sys.argv[1])
except ValueError:
sys.stderr.write("Unable to parse argument '{}'\n".format(sys.argv[1]))
if n <= 0:
sys.stderr.write("Usage: {} <n>\n".format(sys.argv[0]))
sys.exit(-1)
return n
def stats():
for n in range(2, 1000):
cycles = get_cycles(my_outshuffle, n);
if len(cycles) == 1:
print("n={} C={}".format(n, len(get_cycles(my_outshuffle, n))))
if __name__ == "__main__":
#stats()
#exit(0)
n = read_cmd_line()
marked = set()
cycles = get_cycles(std_inshuffle, n)
print_cycles(cycles)
# print_bin_cycles(cycles)
cycles = get_cycles(my_outshuffle, n)
print_cycles(cycles)
cycles = [c for c in get_cycles(funny_outshuffle, n) if len(c)>1]
print("const static int A = {}, B = {};".format(len(cycles), len(cycles[0])))
print("const static int cycles[A][B] = {")
for c in cycles:
print("\t{" + ", ".join([str(x) for x in c]) + "},")
print("};")
# print_bin_cycles(cycles)