pse*_*rra 5 python combinatorics gray-code
对于通信系统,我需要一种特殊的格雷码.要求是:
这种格雷码的一个例子是,对于5位且mrl = 4:
01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111
本文给出了不同位数的最佳mrl值.然后,通过使用详尽的计算机搜索找到这些值.
我有python代码,适用于少量位,最多6位:
N = 5 # number of bit
mrl = 4 # minimum run length
first_transition = [0]
first_code = [0]
def Recur(previous_transitions, previous_codes):
if len(previous_codes) == (2**N):
for b in xrange(N):
print ''.join([str((code >> (N-b-1)) & 1) for code in previous_codes])
print
return
new_transition_list = range(N)
for new_transition in new_transition_list:
ok = True
for i in xrange(mrl-1): #look back for transitions that are too close
try:
if new_transition == previous_transitions[-1-i]:
ok = False
break
except: break
if ok:
new_code = previous_codes[-1] ^ 2**new_transition #look back for repeated code
if not (new_code in previous_codes):
Recur(previous_transitions+[new_transition], previous_codes+[new_code])
Recur(first_transition, first_code )
raw_input('[end]')
我的问题是我想要一个20位的代码,基本方法的复杂性似乎接近于O(n ^ 3).有关如何改进此代码的任何建议？有更好的方法吗？
这是具有优化游程长度的格雷码中描述的方法 1 的（较差）Python 实现，其中包含来自具有长位游程的二进制格雷码n=10的位的特殊情况
我尝试使用与上述论文中相同的术语和变量名称。\n我相信第一篇论文中的方法 2 可能能够改善一些已发现的差距。
\n如果有用的话请告诉我，我可以将它包装在 python 包中，或者用 rust 进行更快的实现。
\nimport numpy as np\n\ndef transition_to_code( transition_sequence ):\n code_sequence = [0]\n \n n = np.int( np.log2( len(transition_sequence) ) )\n \n code = 0\n \n for pos in transition_sequence:\n code ^= 1 << int(pos)\n code_sequence.append(code)\n \n return code_sequence[:-1]\n\ndef print_code_from_transition( transition_sequence ):\n n = np.int( np.log2( len(transition_sequence) ) )\n \n codes = transition_to_code( transition_sequence )\n \n format_string = "b: {:0"+ str(n) +"b}"\n \n for c in codes:\n print( format_string.format( c ) )\n \ndef gap( transition_sequence ):\n as_array = a = np.array( transition_sequence )\n gap = 1\n \n while gap < len(transition_sequence):\n if np.any( as_array == np.roll(as_array, gap) ):\n return gap\n gap += 1\n \n return 0\n\ndef valid_circuit( transition_sequence ):\n n = np.int( np.log2( len(transition_sequence) ) )\n\n if not len(transition_sequence) == 2**n:\n print(\'Length not valid\')\n return False\n \n if not np.all(np.array(transition_sequence) < n):\n print(\'Transition codes not valid\')\n return False\n \n sorted_codes = np.sort( transition_to_code( transition_sequence ) )\n \n if not np.all( sorted_codes == np.arange(0,2**n) ):\n print(\'Not all Unique\')\n return False\n \n return True\n\ntransitions = {\n 2 : [0, 1, 0, 1],\n 3 : [0, 1, 0, 2, 0, 1, 0, 2],\n 4 : [0, 1, 2, 3, 2, 1, 0, 2, 0, 3, 0, 1, 3, 2, 3, 1],\n 5 : [0, 1, 2, 3, 4, 1, 2, 3, 0, 1, 4, 3, 2, 1, 4, 3, 0, 1, 2, 3, 4, 1, 2, 3, 0, 1, 4, 3, 2, 1, 4, 3],\n 6 : [0, 1, 2, 3, 4, 5, 0, 2, 4, 1, 3, 2, 0, 5, 4, 2, 3, 1, 4, 0, 2, 5, 3, 4, 2, 1, 0, 4, 3, 5, 2, 4, 0, 1, 2, 3, 4, 5, 0, 2, 4, 1, 3, 2, 0, 5, 4, 2, 3, 1, 4, 0, 2, 5, 3, 4, 2, 1, 0, 4, 3, 5, 2, 4]\n}\n\ndef interleave(A, B):\n n = np.int( np.log2( len(A) ) )\n m = np.int( np.log2( len(B) ) )\n \n M = 2**m\n N = 2**n\n \n assert N >= M\n \n gap_A = gap(A)\n gap_B = gap(B)\n \n assert gap_A >= gap_B\n \n st_pairs = [ (i, M-i) for i in range(M) if i % 2 == 1]\n \n sorted_pairs = sorted(st_pairs, key=lambda p: np.abs(p[1]/p[0] - gap_B/gap_A) )\n \n best_pair = sorted_pairs[0]\n \n s, t = best_pair\n \n ratio = t/s\n \n P = "b"\n \n while len(P) < M:\n b_to_a_ratio = P.count(\'b\') / (P.count(\'a\') + 1)\n \n if b_to_a_ratio >= ratio :\n P += \'a\'\n else:\n P += \'b\'\n\n return P * N\n\n\ndef P_to_transition(P, A, B):\n Z = []\n \n pos_a = 0\n pos_b = 0\n \n n = np.int( np.log2( len(A) ) )\n \n delta = n\n \n for p in P:\n if p == \'a\' :\n Z.append( A[pos_a % len(A)] )\n pos_a += 1\n else :\n Z.append( B[pos_b % len(B)] + delta )\n pos_b += 1\n \n return Z\n\n"""\nCode for special case for 10-bits to fabric a gap of 8.\n\nFrom: Binary gray codes with long bit runs\nby: Luis Goddyn\xe2\x88\x97 & Pavol Gvozdjak\n\n"""\n\nT0 = [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]\n\ndef to_4( i, sequence ):\n \n permutations = []\n \n indices = [j for j, x in enumerate(sequence) if x == i]\n \n for pos in indices:\n permutation = sequence.copy()\n permutation[pos] = 4\n permutations.append( permutation )\n \n return permutations\n\ndef T_to_group(T):\n \n state = np.array([0,0,0,0,0])\n \n cycle = []\n \n for pos in T:\n cycle.append( state.copy() )\n state[pos] += 1\n state[pos] %= 4\n \n return np.array( cycle )\n\ndef T_to_transition(T):\n \n ticker = [False, False, False, False, False]\n \n transitions = []\n \n for t in T:\n transistion = 2*t + 1*ticker[t]\n ticker[t] = not ticker[t]\n \n transitions.append( transistion )\n return transitions\n \n\nT1 = to_4( 0, T0)[3] * 4\nT2 = to_4( 1, T1)[0] * 4\nT3 = to_4( 2, T2)[1] * 4\n\ntransitions[10] = T_to_transition(T3)\n\n\nfor bits in range(2,21):\n if bits in transitions:\n print( "gray code for {} bits has gap: {}".format(bits, gap(transitions[bits]) ) )\n else:\n print( "finding code for {} bits...".format(bits) )\n \n all_partitions = [ (i, bits-i) for i in range(bits) if i > 1]\n partitions = [ (n, m) for (n,m) in all_partitions if n >= m and m > 1] \n current_gap = 0\n for n,m in partitions:\n P = interleave( transitions[n], transitions[m])\n Z = P_to_transition(P, transitions[n], transitions[m])\n candidate_gap = gap( Z )\n \n if candidate_gap > current_gap:\n current_gap = candidate_gap\n transitions[bits] = Z\n if valid_circuit(transitions[bits]):\n print( "gray code for {} bits has gap: {}".format(bits, gap(transitions[bits]) ) )\n else:\n print( "found in-valid gray code")\n\n\n上面的循环产生
\ngray code for 2 bits has gap: 2\ngray code for 3 bits has gap: 2\ngray code for 4 bits has gap: 2\ngray code for 5 bits has gap: 4\ngray code for 6 bits has gap: 4\nfinding code for 7 bits...\ngray code for 7 bits has gap: 5\nfinding code for 8 bits...\ngray code for 8 bits has gap: 5\nfinding code for 9 bits...\ngray code for 9 bits has gap: 6\ngray code for 10 bits has gap: 8\nfinding code for 11 bits...\ngray code for 11 bits has gap: 8\nfinding code for 12 bits...\ngray code for 12 bits has gap: 8\nfinding code for 13 bits...\ngray code for 13 bits has gap: 9\nfinding code for 14 bits...\ngray code for 14 bits has gap: 9\nfinding code for 15 bits...\ngray code for 15 bits has gap: 11\nfinding code for 16 bits...\ngray code for 16 bits has gap: 11\nfinding code for 17 bits...\ngray code for 17 bits has gap: 12\nfinding code for 18 bits...\ngray code for 18 bits has gap: 12\nfinding code for 19 bits...\ngray code for 19 bits has gap: 13\nfinding code for 20 bits...\ngray code for 20 bits has gap: 15\n使用transitions[3]或print_code_from_transition( transitions[3] )显示格雷码（本例中为 3 位）