|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Generalized Gray codes with prescribed ends | | Tomáš Dvořák
; Petr Gregor
; Václav Koubek
; | | Date: |
29 Mar 2016 | | Abstract: | An $n$-bit Gray code is a sequence of all $n$-bit strings such that
consecutive strings differ in a single bit. It is well-known that given
$alpha,etain{0,1}^n$, an $n$-bit Gray code between $alpha$ and $eta$
exists iff the Hamming distance $d(alpha,eta)$ of $alpha$ and $eta$ is
odd. We generalize this classical result to $k$ pairwise disjoint pairs
$alpha_i, eta_iin{0,1}^n$: if $d(alpha_i,eta_i)$ is odd for all $i$
and $k<n$, then the set of all $n$-bit strings can be partitioned into $k$
sequences such that the $i$-th sequence leads from $alpha_i$ to $eta_i$ and
consecutive strings differ in a single bit. This holds for every $n>1$ with one
exception in the case when $n = k + 1 = 4$. Our result is optimal in the sense
that for every $n>2$ there are $n$ pairwise disjoint pairs
$alpha_i,eta_iin{0,1}^n$ with $d(alpha_i,eta_i)$ odd for which such
sequences do not exist. | | Source: | arXiv, 1603.8827 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER