6

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

Practically, N will be very large, say 1000. I want to randomly sample this large space of 2^1000 integers, but I need to generate something like a random walk because the application in mind can only hop from one number to the next by flipping one bit.

Improve this question
6
  • How many integers do you want to sample? (How long is your "random" walk?) The longer you go, the more constrained it becomes (because you must have no repeats), and the more predictable the next integer becomes. Commented Jun 11, 2011 at 19:00
  • I probably want several million to tens of millions of samples. Something like 2^20 - 2^25. I am also interested in algorithms which almost never repeat (a few repeats might be OK). This is for Monte Carlo simulation. Commented Jun 11, 2011 at 19:01
  • 3
    @Victor: Ah, true Monte Carlo simulations are done with random walks that don't have the "never repeats" constraint. In fact, if you add a constraint like "never repeats", the resulting is no longer a Markov process, and most of the theorems about Monte Carlo simulations don't apply. If your application is really Monte Carlo simulation, then Ethan's answer is good and you should accept it. Commented Jun 11, 2011 at 19:06
  • Yes, I know Monte Carlo usually allows repeats, but I'm using the term loosely here. For my application, I'd prefer to get better coverage of the sampling space since I want to determine a probability distribution depending on the integers. Commented Jun 11, 2011 at 19:36
  • 1
    Is "never repeats" a strict requirement, or would "repeats only very infrequently" suffice? Commented Jun 11, 2011 at 20:06

3 Answers 3

Reset to default
5

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

In order to satisfy randomness you will need to store previously generated numbers (thanks ShreevatsaR). Additionally, you may run into a scenario where no non-repeating answers are possible so this will require a backtracking algorithm as well.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You also need to check that there are no repeats. If you do this by keeping all the previous results and checking them, that is a lot of additional space and time.
I would just remember the last k bits you flipped (for some small k, like 3 or 4) and do not flip any of those. This guarantees you take at least k steps "away" from the current point before taking even one step "towards" it again, so it should make repetitions pretty rare on a N=1000 space I think. (Still possible, of course.)
1

This makes me think of fractals - following a boundary in a julia set or something along those lines.

If N is 1000, use a 2^500 x 2^500 fractal bitmap (obviously don't generate it in advance - you can derive each pixel on demand, and most won't be needed). Each pixel move is one pixel up, down, left or right following the boundary line between pixels, like a simple bitmap tracing algorithm. So long as you start at the edge of the bitmap, you should return to the edge of the bitmap sooner or later - following a specific "colour" boundary should always give a closed curve with no self-crossings, if you look at the unbounded version of that fractal.

The x and y axes of the bitmap will need "Gray coded" co-ordinates, of course - a bit like oversized Karnaugh maps. Each step in the tracing (one pixel up, down, left or right) equates to a single-bit change in one bitmap co-ordinate, and therefore in one bit of the resulting values in the random walk.

EDIT

I just realised there's a problem. The more wrinkly the boundary, the more likely you are in the tracing to hit a point where you have a choice of directions, such as...

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

Whichever direction you enter this point, you have a choice of three ways out. Choose the wrong one of the other two and you may return back to this point, therefore this is a possible self-crossing point and possible repeat. You can eliminate the continue-in-the-same-direction choice - whichever way you turn should keep the same boundary colours to the left and right of your boundary path as you trace - but this still leaves a choice of two directions.

I think the problem can be eliminated by making having at least three colours in the fractal, and by always keeping the same colour to one particular side (relative to the trace direction) of the boundary. There may be an "as long as the fractal isn't too wrinkly" proviso, though.

The last resort fix is to keep a record of points where this choice was available. If you return to the same point, backtrack and take the other alternative.

Improve this answer

Comments

0

While an algorithm like this:

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

…would return a random sequence of integers differing each by 1 bit, it would require a huge array for backtracing to ensure uniqueness of numbers. Further more your running time would increase exponentially(?) with increasing density of your backtrace, as the chance to hit a new and non-repeating number decreases with every number in the sequence.

To reduce time and space one could try to incorporate one of these:

Bloom Filter

Use a Bloom Filter to drastically reduce the space (and time) needed for uniqueness-backtracing.

As Bloom Filters come with the drawback of producing false positives from time to time a certain rate of falsely detected repeats (sic!) (which thus are skipped) in your sequence would occur.

While the use of a Bloom Filter would reduce the space and time your running time would still increase exponentially(?)…

Hilbert Curve

A Hilbert Curve represents a non-repeating (kind of pseudo-random) walk on a quadratic plane (or in a cube) with each step being of length 1.
Using a Hilbert Curve (on an appropriate distribution of values) one might be able to get rid of the need for a backtrace entirely. To enable your sequence to get a seed you'd generate n (n being the dimension of your plane/cube/hypercube) random numbers between 0 and s (s being the length of your plane's/cube's/hypercube's sides). Not only would a Hilbert Curve remove the need for a backtrace, it would also make the sequencer run in O(1) per number (in contrast to the use of a backtrace, which would make your running time increase exponentially(?) over time…)
To seed your sequence you'd wrap-shift your n-dimensional distribution by random displacements in each of its n dimension.

Ps: You might get better answers here: CSTheory @ StackExchange (or not, see comments)

Improve this answer

6 Comments

The Hilbert curve is very predictable - whether it can be called pseudo-random depends heavily on the application. Gray codes have already been mentioned, and there is a relationship between Gray codes and the Hilbert curve.
@Steve314: Well, without (or equal) seeds rand() will generate the same sequence and is considered pseudo-random. Good point though. I forgot to add a mention of a possible way of seeding to my answer. Added it now. Basically a random displacement shift with wrapping seeded by a random seed. So while it would always generate the same pattern the actual sequence of numbers would highly depend on the seed's shift distance and the distribution's nature.
Using a Bloom filter would not allow production of a duplicate. A false positive would prevent production of a unique number that hashes to the same values as did a number that was already produced.
@jim-mischel: Absolutely true. Fixed. Need some sleep, I guess. ;)
That said, a Bloom filter would be an excellent solution to this problem. We're talking generating 2^25 numbers in a space of 2^1000. A Bloom filter with N=2^25 and a false positive rate of one in a million would require only about 120 MB. You can reduce that memory requirement (and the cost of calculating keys) by allowing for more false positives which in this case most likely wouldn't adversely affect the results.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.