Statistical Estimates of the n-Bit Gray Codes by Restricted Random Generation of Permutations of 1 to 2(n)

摘要

The number of n-bit Gray codes is the number in a well-defined subset of the permutations of the integers 1 to 2 sub n. Generating random permutations with associated estimates under suitably restrictive selection rules produces a discrete distribution whose expectation value is the number of such codes. The number of Hamiltonian circuits on the n-cube (cyclic Gray codes) is a further subset which can readily be estimated also. Reliable statistical estimates up to n = 6 were produced with reasonable speed by computer implementation of this Monte Carlo process; excellent agreement with the exact values for n = 4 and 5 was obtained. Proofs are given of the validity of the technique and of an upper bound for the total number of Gray codes. The technique could also be used to count permutation subsets other than Gray codes. Keywords: Reprints. (Author)