1
$\begingroup$

Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.

What would be an efficient way to generate the corresponding permutation matrix (having sparsity 1)?

A brute-force solution would be to go through all the integers from $0$ to $2^{n-1}$, converting each of them from binary to Gray using smth like

def convert_gray(binary):
   binary = int(binary, 2)
   binary ^= (binary >> 1)
   return bin(binary)[2:]

considering each outcome as a binary, and filling the corresponding matrix entry.

I am wondering if there exists a faster and a more compact solution?

Improve this question
$\endgroup$
3
  • $\begingroup$ How are you storing your permutation matrix? If you are storing it as a dense matrix, that is, as a list of $4^n$ entries, then the algorithm you describe is already optimal, since generating the Gray sequence takes a lot less time than $4^n$. You can speed that part up by generating the Gray sequence as a sequence, but it won't make much difference in running time. $\endgroup$
    – Yuval Filmus
    Commented Jan 30, 2021 at 20:11
  • $\begingroup$ In my application, I will store at as a numpy array, because I will later multiply it by another matrix... $\endgroup$
    – mavzolej
    Commented Jan 30, 2021 at 20:20
  • 1
    $\begingroup$ Numpy arrays are dense. It will take $4^n$ time just to touch all entries in your matrix. This is a lot more than generating a Gray sequence even in a naive way. $\endgroup$
    – Yuval Filmus
    Commented Jan 30, 2021 at 20:54

0

Reset to default

Your Answer