Generate a random sequence of integers that differs by 1 bit without repeats

Question

I need to generate a (pseudo) random sequence of N bit integers, where consecutive integers differ from the previous one by only 1 bit, and the sequence never repeats. I know that Gray code will generate non-repeating sequences with a difference of 1 bit, and LFSR will generate non-repeating random sequences, but I'm not sure how to combine these ideas to create what I want.

In practice, N will be very large, say 1000. I want to randomly try this large number of integers 2 ^ 1000 integers, but I need to create something like a random walk, because the application in my mind can only skip from one number to then flip one bit.

Answer 1

Use any random number generator algorithm to generate an integer from 1 to N (or from 0 to N-1 depending on the language). Use the result to determine the bit index for the flip.

To satisfy the randomness, you will need to save the previously generated numbers (thanks to ShreevatsaR). In addition, you may encounter a scenario in which there are no duplicate answers, so this will also require a reverse tracking algorithm.

Answer 2

It makes me think about fractals - after the border in a set of julia or something like that.

If N is 1000, use a 2 ^ 500 x 2 ^ 500 fractal bitmap (obviously, do not generate it in advance - you can get each pixel on demand, and most of them will not be needed). Each pixel movement is one pixel up, down, left, or right, following the border between the pixels, as a simple algorithm for tracing a raster image. Until you start from the edge of the bitmap, you should return to the edge of the bitmap sooner or later - after a certain “color” border you should always give a closed curve without self-intersections if you look at an unlimited version of this fractal.

The x and y axes of the bitmap, of course, will need the "gray coding" coordinates, a bit like oversized Carnot maps. Each step in the trace (one pixel up, down, left, or right) corresponds to a one-bit change in one raster coordinate and, therefore, in one bit of the resulting values ​​in a random walk.

EDIT

I just realized that the problem. The more wrinkled the border, the more likely you are to trace to get to the point where you have a choice of directions, for example ...

* | . ---+--- . | * 

In which direction you are entering this point, you have a choice of three options. Choose the wrong one of the other two, and you can go back to this point, so this is a possible intersection point and possible repetition. You can eliminate the option of “continuing in one direction” - depending on how you turn, you should keep the same border colors to the left and right of your border path as you trace, but this still leaves choice in two directions.

I think that the problem can be eliminated by making at least three colors in the fractal and always preserving the same color on one specific side (relative to the direction of the trace) of the border. Maybe "while the fractal is not too wrinkled," however.

The final fix is ​​to keep track of the points where this choice was available. If you return to the same point, step back and take another alternative.

Answer 3

While such an algorithm:

 seed() i = random(0, n) repeat: i ^= >> (i % bitlen) yield i 

... will return a random sequence of integers that differ by 1 bit from each other, to ensure the uniqueness of the numbers, a huge array will be needed for backtracking. Moreover, your working time will increase exponentially (?) With an increase in the density of your return line, since the probability of getting into a new and non-repeating number decreases with each number in the sequence.

To reduce time and space, you can try to include one of them:

Bloom filter

Use the Bloom Filter to dramatically reduce the space (and time) required for unique back-tracking.

Since Flower Filters have the disadvantage of creating false positives from time to time, there will be a certain rate of false detected repeats (sic!) (Which are thus skipped) in your sequence.

While using Bloom Filter will reduce space and time, your uptime will increase exponentially (?) ...

Hilbert curve

A Hilbert curve is a non-repeating (pseudo-random) walk on a quadratic plane (or in a cube), and each step has a length of 1.
Using the Hilbert Curve (with an appropriate distribution of values), you can completely get rid of the need for the opposite direction. To include your sequence for getting the seed, you must generate n ( n as the size of your cube / cube / hypercube) random numbers between 0 and s ( s being the length of the plane of your cube / cube / hypercube). Not only does the Hilbert Curve eliminate the need for backtrace, it also makes the sequencer work in O(1) per number (as opposed to using backtrace, which would increase your uptime) exponentially (?) Over time ...)
To seed a sequence, you transfer your n dimensional distribution to random offsets in each of the n dimensions.

---

Ps: Here you can get better answers: CSTheory @StackExchange (or not, see comments)