GrayCodes

The binary words of length $n$ in binary-reflected Gray-code order.

WikipediaGray codeMathWorldGrayCodeWikidataQ332772OEISA003188SageMathsage.combinat.gray_codes

GrayCodes(n)the binary words of length

n

in binary-reflected Gray-code order

Typed signatures

Type	Package	Applies
`(integer<0..>) -> indexed_collection<binary_word>`	`combinatorics`	always

Domain: Collections

Details

Count is $2^n$ ; consecutive words differ in exactly one bit.
$g(r) = r \oplus \lfloor r/2 \rfloor$ (A003188).

Definition

Epsil, as the implementation runs it.

count(_n)

2 ^ _n

unrank(_n, _r)

Map(Function(
              ((_r - _r % 2 ^ (_n - j)) / 2 ^ (_n - j) % 2 + (_r - _r % 2 ^ (_n -
                                                                             j +
                                                                             1)) /
                                                             2 ^ (_n - j + 1) % 2) % 2,
              j,
            ), Range(1, _n, 1))

rank(_n, _x)

Fold(Function(acc + 2 ^ (_n - j) * (Fold(
                                          Function(c + _x[t], c, t),
                                          0,
                                          Range(1, j, 1),
                                        ) % 2), acc, j), 0, Range(1, _n, 1))

valid(_n, _x)

Length(_x) == _n && Fold(
                          Function(ok_j && 0 <= _x[j] && _x[j] <= 1, ok_j, j),
                          True,
                          Range(1, Length(_x), 1),
                        )

Statistics

On BinaryWord, called as CombinatorialStat(x, "Name").

Ascents St000292Positions i with w(i) < w(i+1).
Balance St000628The least q such that any two factors of one length differ by at most q ones.
BalancedPrefixCount St001355The nonempty prefixes with as many 0s as 1s.
BaselineCrossings St001730The times the path, a 1 a step up and a 0 a step down, crosses the baseline.
BorderCount St001884The prefixes shorter than the word that are also suffixes, the empty one included.
BorderLength St000295The length of the longest proper prefix that is also a suffix; 0 for none.
CatalanFactorCount St000876The factors in the Catalan factorization: the critical steps, and the middle Dyck word if it is not empty.
ChangeCount St000691The positions i where the letters i and i + 1 differ.
CriticalStepCount St000885The critical steps l + m in the Catalan factorization (D 0)^l D (1 D)^m.
CyclicShiftIndex St001436The position of the word among its distinct cyclic shifts in lexicographic order, from 0.
DecimalRepresentation St000289The word read as a binary numeral.
DecimalRepresentationWithLeadingOne St000827The word with a 1 put in front, read as a binary numeral.
DescentWordPreimageCount St000529The permutations whose descent word is this word.
DistinctCubeCount St001423The distinct nonempty words u with uuu a factor.
DistinctFactorCount St000294The distinct factors, the empty one included: the subword complexity.
DistinctSquareCount St001424The distinct nonempty words u with uu a factor.
DistinctSubsequenceCount St000518The distinct subsequences, the empty one included.
EvenPalindromicPrefixHalfLength St001413Half the length of the longest palindromic prefix of even length.
FirstOnePositionAfterAppendedOne St000326The position of the first 1 once a 1 is appended to the word: one more than the leading zeros.
Flex St001437The product of the word's lex (its position among its distinct cyclic shifts, from 1) and its frequency.
HammingWeight St000288The number of ones.
InternalInversions St000921The pairs i < j with w(i) > w(j) that lie in the same block of the sorted word.
Inversions St000293Pairs i < j with w(i) > w(j).
InversionSum St000347The sum of j - i over the pairs i < j with w(i) > w(j).
LatticePathsAboveWordCount St001365The paths of the word's length, ending anywhere, that stay weakly above the path the word gives.
LeadingOnesCount St000297The number of ones before the first 0.
LongestAlternatingFactor St000983The length of the longest factor in which every two neighboring letters differ.
LongestCatalanFactorSemilength St000875The semilength of the longest Dyck word in the Catalan factorization.
LongestConstantRun St000982The length of the longest run of equal letters.
LongestPalindromicFactor St001416The length of the longest factor that reads the same backwards.
LongestPalindromicFactorStartingWithOne St001419The length of the longest palindromic factor that begins with a 1.
LongestPalindromicPrefix St001415The length of the longest prefix that reads the same backwards.
LongestPalindromicSubsequence St001417The length of the longest subsequence that reads the same backwards.
LongestRunOfOnes St000392The length of the longest run of ones.
LongestYamanouchiPrefix St001371The length of the longest prefix in which no prefix has more ones than zeros.
LyndonFactorizationLength St001267The factors in the Lyndon factorization.
MajorIndex St000290The sum of the positions i with w(i) > w(i+1).
MinimalPeriod St000626The least p with w(i) = w(i + p) wherever both are letters.
ModularMajorIndex St001485The major index modulo the length of the word.
NonInversionSum St000348The sum of j - i over the pairs i < j with w(i) < w(j).
OddOneRunCount St000389The number of maximal runs of ones of odd length.
OddPalindromicPrefixHalfLength St001414The largest j such that the prefix of length 2 j + 1 is a palindrome.
OnePositionSum St000391The sum of the positions of the ones.
OneRunCount St000390The number of maximal runs of ones.
OnesMinusZeros St000878The number of ones less the number of zeros.
PalindromicDecompositionCount St000631The ways to write the word as a concatenation of palindromic factors.
PathDepth St000877The most zeros less ones among the prefixes.
PrimitiveFactorCount St001838The distinct nonempty factors that are not a power of a shorter word.
RepetitionExponent St000627The largest e such that the word is e copies of one word.
ReverseComplementFactorHalfLength St001420Half the length of the longest factor that is its own reverse complement.
ReverseComplementFactorHalfLengthStartingWithOne St001421Half the length of the longest factor that is its own reverse complement and begins with a 1.
SameEndpointPathsAboveWordCount St001313The paths with the word's number of ones and zeros that stay weakly above the path the word gives.
ShortestPalindromicDecompositionLength St000630The fewest palindromic factors the word is a concatenation of.
StrictlyIncreasingRuns St000393The maximal runs of strictly increasing letters.
SymmetricBorderLength St000296The length of the longest prefix whose reverse is a suffix.
SymmetryDegree St001524The positions i up to half the length where the letters i and n + 1 - i agree.
UniqueFactorLength St000922The least length for which all factors of that length are different.
ValleyFillingDegree St001721The number of times every valley 01 must be swapped for a peak 10, and a trailing 0 made a 1, to leave no zeros.
WeakMajorIndex St001930The sum of the positions i with w(i) >= w(i+1).

Maps

Into and out of BinaryWord, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From BinaryWord

AlternatingComplementBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00158Every second letter swapped for the other, starting with the second.
CodeCompositionBinaryWord → IntegerCompositionInjectionGraded mapMp00178The composition whose code is the word with a 1 put in front: each 1 opens a part, of 1 plus the zeros after it.
ComplementBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00105Each letter swapped for the other: 0 for 1 and 1 for 0.
CyclicShiftBinaryWord → BinaryWordinverseBijectionGraded mapMp00135Rotate the word one place to the left: the first letter moves to the end.
FinsetBinaryWord → FinsetinverseThe subset of 1..m a binary word of length m marks: the positions holding 1.
FlagZerosToZerosBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00269The word with as many zeros as this one, prepended with its reverse complement, has occurrences of 10.
FoataInversionsToMajorBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00316The inverse of Foata's bijection on words: peel off the last letter, rotate the blocks of the rest back.
FoataMajorToInversionsBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00096Foata's bijection on words: each letter is put on the end of the image so far, which is cut into blocks, and every block is rotated one place right.
GrayNextBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00272The next word in the Gray code: flip the first letter when the ones are even in number, else the letter after the first one.
GrayPreviousBinaryWord → BinaryWordinverseBijectionMp00273The previous word in the Gray code: flip the first letter when the ones are odd in number, else the letter after the first one.
IntegerCompositionBinaryWord → IntegerCompositioninverseThe composition of m + 1 a binary word of length m cuts out.
InverseCyclicShiftBinaryWord → BinaryWordinverseBijectionGraded mapMp00136Rotate the word one place to the right: the last letter moves to the front.
PathRowmotionBinaryWord → BinaryWordbijectionBijectionGraded mapMp00280Rowmotion of the word as a lattice path: the path whose peaks are the original's valleys with an up step appended.
ReverseBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00104The word read backwards.
RowmotionBinaryWord → BinaryWordbijectionBijectionGraded mapMp00278Rowmotion of the word as an order ideal of a product of two chains: the stretches between valleys reversed, each valley written 10.
RunCompositionBinaryWord → IntegerCompositionsurjectionSurjectionGraded mapMp00097The lengths of the maximal runs of equal letters, left to right.
RunSortBinaryWord → BinaryWordidempotentIdempotentGraded mapMp00224The word with its weakly increasing runs sorted lexicographically.
StandardPermutationBinaryWord → PermutationGraded mapMp00336The permutation ranking the letters of the word, equal letters from left to right.
TwistBinaryWord → BinaryWordinvolutionBijectionGraded mapInvolutionMp00200The first letter swapped for the other.
ValleysToPeaksBinaryWord → BinaryWordGraded mapMp00234Every valley 01 swapped for a peak 10, and a trailing 0 made a 1.
ZerosToFlagZerosBinaryWord → BinaryWordbijectioninverseBijectionGraded mapMp00268The word whose reverse complement, prepended, has as many occurrences of 10 as this has zeros.

To BinaryWord

BinaryWordDyckPath → BinaryWordInjectionGraded mapMp00093The Dyck word as a binary word: 1 for an up step, 0 for a down step.
BinaryWordIntegerPartition → BinaryWordInjectionMp00095The shape's boundary read from the first row down: 1 for a step down, 0 for a step left.
BinaryWordFinset → BinaryWordinverseA subset of 1..n as its characteristic word: letter i is 1 when i is a member.
CodeWordIntegerComposition → BinaryWordInjectionGraded mapMp00094The word that writes each part i as a one followed by i - 1 zeros.
ConnectivityWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00114Letter i is 1 when the first i entries are all smaller than the rest: the connectivity set as a binary word.
CutWordIntegerComposition → BinaryWordinverseA composition of n as the binary word of length n - 1 marking where it is cut.
DescentBottomWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00131Letter v is 1 when value v is a descent bottom: some larger value immediately precedes it.
DescentTopWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00130Letter v - 1 is 1 when value v is a descent top: some smaller value immediately follows it.
DescentWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00109Letter i is 1 when the word falls between positions i and i + 1: the descent set as a binary word.
OddPartsWordIntegerPartition → BinaryWordSurjectionMp00317The binary word marking which parts are odd, the parts taken largest first.
SignWordSignedPermutation → BinaryWordsurjectionSurjectionGraded mapMp00267The signs as a binary word: letter i is 1 when entry i is negative.
TableauDescentWordStandardTableau → BinaryWordsurjectionSurjectionGraded mapMp00134Letter i is 1 when entry i + 1 sits in a lower row than entry i.

2 more in FindStat, not implemented here

Mp00261BinaryWord → BinaryWordGraded mapBurrows-Wheeler
Mp00262BinaryWord → Posetsposet of factors

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(GrayCodes(3)) = 8$

live ↗

\mathrm{Count}(\mathrm{GrayCodes}(3))

Out

8

The first element in enumeration order