Content deleted Content added
{{Short description|Permutation that reverses binary numbers}} |
→Example: wikitable |
||
Line 11:
Thus, the letter ''a'' in position 000 is mapped to the same position (000), the letter ''b'' in position 001 is mapped to the fifth position (the one numbered 100), etc., giving the new sequence ''{{not a typo|aecgbfdh}}''. Repeating the same permutation on this new sequence returns to the starting sequence.
Writing the index numbers in decimal (but, as above, starting with position 0 rather than the more conventional start of 1 for a permutation), the bit-reversal permutations on <math>n=2^k</math> items, for <math>k=0,1,2, 3, \dots</math>, are:<ref>{{cite OEIS|A030109|mode=cs2}}</ref>
{| class="wikitable" style="text-align: center;"
|-
* k = 1: 0 1▼
! <math>k</math> !! <math>n=2^k</math> !! permutation
* k = 2: 0 2 1 3▼
|-
* k = 3: 0 4 2 6 1 5 3 7▼
| 0 || 1 || 0
* k = 4: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15▼
|-
Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, doubled, and the same sequence with each value increased by one.▼
|-
|-
|-
|}
▲Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, with its values doubled, and the same sequence with each value increased by one.
Thus, for example doubling the length-4 permutation {{nowrap|0 2 1 3}} gives {{nowrap|0 4 2 6}}, adding one gives {{nowrap|1 5 3 7}}, and concatenating these two sequences gives the length-8 permutation {{nowrap|0 4 2 6 1 5 3 7}}.
| |||