formula to pick every pixel in a bitmap without repeating

Question

I'm looking for an algorithm, I am programming in swift now but pseudocode or any reasonably similar "C family" syntax will do.

Imagine a large list of values, such as pixels in a bitmap. You want to pick each one in a visually random order, one at a time, and never pick the same one twice, and always end up picking them all.

I used it before in a Fractal generator so that it was not just rendering line by line, but built it up slowly in a stochastic way, but that was long ago, in a Java applet, and I no longer have the code.

I do not believe it used any pseudo-random number generator, and the main thing I liked about it is that it did not make the rendering time take longer than the just line by line approach. Any of the shuffling algorithms I looked at would make the rendering take longer with such a large number of values to deal with, unless I'm missing something.

EDIT: I used the shuffling an array approach. I shuffle once when the app loads, and it does not take that long anyway. Here is the code for my "Dealer" class.

import Foundation
import Cocoa
import Quartz

class Dealer: NSObject
{
  //########################################################
  var deck = [(CGFloat,CGFloat)]()
  var count = 0
  //########################################################
  init(_ w:Int, _ h:Int)
  {
    super.init()
    deck.reserveCapacity((w*h)+1)
    for y in 0...h
    {
      for x in 0...w
      {
        deck.append((CGFloat(x),CGFloat(y)))
      }
    }
    self.shuffle()
  }
  //########################################################
  func shuffle()
  {
    var j:Int = 0
    let total:Int = deck.count-1
    for i:Int in 0...total
    {
      j = Int(arc4random_uniform(UInt32(total)))
      deck.swapAt(i, j)
    }
  }
  //########################################################
  func deal() -> (CGFloat,CGFloat)
  {
    let result = deck[count]
    let total:Int = deck.count-1
    if(count<total) { count=count+1 } else { count=0 }
    return(result)
  }
  //########################################################
}

The init is called once, and it calls shuffle, but if you want you can call shuffle again if needed. Each time you need a "card" you call Deal. It loops to the beginning when the "deck" is done.

Answer 1

if you got enough memory space to store all the pixel positions you can shuffle them:

const int xs=640;            // image resolution
const int ys=480;
color pixel[sz];             // image data
const int sz=xs*ys;          // image size 
int adr[sz],i,j;
for (i=0;i<sz;i++) adr[i]=i; // ordered positions
for (i=0;i<sz;i++)           // shuffle them
 {
 j = random(sz);             // pseudo-randomness with uniform distribution 
 swap(pixel[i],pixel[j]);
 }

this way you got guaranteed that each pixel is used once and most likely all of them are shuffled ...

Answer 2

You need to implement a pseudo-random number generator with a theoretically known period, which is greater than but very close to the number of elements in your list. Suppose R() is a function that implements such a RNG.

Then:

for i = 1...N
    do
        idx = R()
    while idx > N
    output element(idx)
end

• If the period of the RNG is greater than N, this algorithm is guaranteed to finish, and never output the same element twice
• If the period of the RNG is close to N, this algorithm will be fast (i.e. the do-while loop will mostly do 1 iteration).
• If the RNG has good quality, the visual output will look pleasant; here you have to do experiments and decide what is good enough for you

To find a RNG that has an exactly-known period, you should examine theory on RNGs, which is very extensive (maybe too extensive); Wikipedia has useful links. Start with Linear congruential generators: they are very simple, and there is a chance they will be of good enough quality.