Randomized Permutations Without Lists

I'm writing a new interpreted language called Boss. It has Roguelike syntax and in fact the general idea is for it to be a version of Rogue that doesn't require a C++ compiler or development environment.

As I go I'm writing increasingly sophisticated toy programs to test out Boss. It's ironic that I'm writing the same kinds of simple programs as I did 30 years ago but now for entirely different reasons. Back then it was to learn programming and now it's to test my compiler. Heck yeah!

As my current testbed program I've been writing and improving a 2D maze generator. The basic algorithm is simple:

  1. Fill an odd-sized rectangle with all walls.
  2. Randomly pick an odd-numbered starting location and visit it.
  3. At each location, recursively visit all four adjacent locations that are two steps away, in a random order, unless you've already been to the adjacent location or it's out of bounds.
  4. As you visit a new location, knock down the wall at the new location and the wall in-between the previous location and the new location.

Here is a simple Boss implementation of the maze generator.

MazeGen(109,25).display

class MazeGen
  PROPERTIES
    width, height : Int32
    maze = Character[]

    offsets = [ XY(0,-1), XY(-1,0), XY(0,1), XY(1,0) ]

  METHODS
    method init( width:Int32, height:Int32 )
      generate( width, height )

    method generate( width, height )
      maze.resize( width * height )
      maze.fill('#')
      local start_i = Random.int32((width-2)/2+1) * 2 + 1
      local start_j = Random.int32((height-2)/2+1) * 2 + 1
      visit( start_i, start_j, 0, 0 )

    method display
      local j = 0
      while (j < height)
        local i = 0
        while (i < width)
          print maze[j*width+i]
          ++i
        endWhile
        println
        ++j
      endWhile

    method visit( i:Int32, j:Int32, di:Int32, dj:Int32 )
      local mid_i = i + di
      local mid_j = j + dj
      i = mid_i + di
      j = mid_j + dj
      if (i < 0 or j < 0 or i >= width or j >= height) return
      local index = j * width + i
      if (maze[index] == ' ') return

      maze[mid_j*width+mid_i] = ' ' # 1 step
      maze[index] = ' '             # 2 steps

      local dirs = [0,1,2,3]
      dirs.shuffle
      while (dirs.count)
        local dir = dirs.remove_last
        local offset = offsets[ dir ]
        visit( i, j, offset.x, offset.y )
      endWhile

endClass

And here is the console output it produces.

Below is the output of the same program that stops after 200 recursions. It might be easier to understand the depth-first algorithm with this halfway-finished maze: it's like a worm that tunnels through rock, going in random direction at each location but making sure not to cross its own path. When it reaches a dead end it backtracks to the most recent position that still has at least one direction to explore and strikes out in one of those directions.

I've written this algorithm many times and these days I wince a bit at allocating a list of randomized directions for each recursion. It's no big deal for this scale of program, but it's just the principle of the thing.

This time I ended up brainstorming a way to generate a random permutations of a sequence of an arbitrary length without needing to allocate a list for storage. The caveat is that to avoid needing a list, code must be designed for a specific sequence length (such as length four for the four directions for the maze generator). Here's how it works.

Say we want to print the numbers 0 through 9 out in a random order.

  1. It's easy to pick the first number: random(0,9). Let's say we ended up with
    r1 = n1 = 3 (r1 = random pick, n1 = resulting sequence number).
  2. Our second number then needs to be 0-2 or 4-9. But if we treat the range as wrapping around there's a simpler way to think of it: 0-2 or 4-9 becomes (3 + 1-9) % 10, or (3 + 0-8 + 1) % 10. Whatever our first number r1 is, the second number will be n2 = (r1 + random(0,8) + 1) % 10. Essentially we're just picking another number out of a contiguous range, adding it to the previous number, and wrapping it around if it goes off the end. Let's say random(0,8) returned r2 = 7 and so the second number is n2 = (r1 + r2 + 1) % 10 = (3 + 7 + 1) % 10 = 1.
  3. If the second number is n2 = (r1 + r2 + 1) % 10, the third number is n3 = (r1 + r3 + 1) % 10, where r3 is any random number 0-8 except for r2. Another way to express "any random number 0-8 except for r2" is (r2 + random(0,7) + 1) % 9, which uses the same wraparound trick. The full equation for the third number becomes n3 = r1 + (r2 + random(0,7) + 1) % 9) % 10.
  4. You may see the pattern developing. To select a random permutation of numbers 0..9, we'll need 10 random numbers:
    r1 = random(0,9)
    r2 = random(0,8)
    r3 = random(0,7)
    ...
    r10 = random(0,0)

    Each successive sequence expands the previous rX ... % N with
    (rX + rY + 1) % (N-1):
    n1 = r1
    n2 = (r1 + r2 + 1) % 10
    n3 = (r1 + (r2 + r3 + 1) % 9 + 1) % 10
    n4 = (r1 + (r2 + (r3 + r4 +1) % 8 + 1) % 9 + 1) % 10
    ...

The pattern is recursive in a general sense and yet it is not well-suited to recursive programming because computing each number requires all random picks thus far.

Here is a recursive Rogue implementation which does use a list (the very thing I'm trying to avoid):

permutation( 10, Int32[] )

routine permutation( count:Int32, r_stack:Int32[] )
  local r = Random.int32( count )
  local n = r
  local limit = count + 1
  forEach (previous_r in r_stack step -1)
    n = (n + previous_r + 1) % limit
    ++limit
  endForEach
  println n
  r_stack.add( r )
  if (count > 1) permutation( count-1, r_stack )
endRoutine

The maze algorithm just needs a small, fixed-size random permutation of 4 directions, so we can just hard-code the equations listed further up. In my case I did this:

method random_directions->Int32
  local r1 = Random.int32(4)
  local r2 = Random.int32(3)
  local r3 = Random.int32(2)
  local d1 = r1
  local d2 = (r1 + r2 + 1) % 4
  local d3 = (r1 + (r2 + r3 + 1) % 3 + 1) % 4
  local d4 = (0 + 1 + 2 + 3) - (d1 + d2 + d3)
  return (d1:<<:6) | (d2:<<:4) | (d3:<<:2) | d4
  # Returns bits AABBCCDD, where each AA etc. is a direction 0-3.

My full Boss maze program, which also connects adjoining walls using box-drawing characters.

class MazeGen
  PROPERTIES
    width, height : Int32
    maze = Character[]

    offsets = [ XY(0,-1), XY(-1,0), XY(0,1), XY(1,0) ]
    walls =
    [           # ULDR
      ' '       # ----
      '\u2501'  # ---R
      '\u2503'  # --D-
      '\u250F'  # --DR
      '\u2501'  # -L--
      '\u2501'  # -L-R
      '\u2513'  # -LD-
      '\u2533'  # -LDR
      '\u2503'  # U---
      '\u2517'  # U--R
      '\u2503'  # U-D-
      '\u2523'  # U-DR
      '\u251B'  # UL--
      '\u253B'  # UL-R
      '\u252B'  # ULD-
      '\u254B'  # ULDR
    ]

  METHODS
    method init( width:Int32, height:Int32 )
      generate( width, height )

    method generate( width, height )
      maze.resize( width * height )
      maze.fill('#')
      local start_i = Random.int32((width-2)/2+1) * 2 + 1
      local start_j = Random.int32((height-2)/2+1) * 2 + 1
      visit( start_i, start_j, 0, 0 )
      make_adjoining_walls

    method display
      local j = 0
      while (j < height)
        local i = 0
        while (i < width)
          print maze[j*width+i]
          ++i
        endWhile
        println
        ++j
      endWhile

    method has_wall( i:Int32, j:Int32 )->Logical
      if (i < 0 or j < 0 or i >= width or j >= height) return false
      return maze[j*width+i] != ' '

    method make_adjoining_walls
      local index = width * height
      while (index > 0)
        --index
        if (maze[index] != ' ')
          local i = index % width
          local j = index / width
          local uldr = 0
          if (has_wall(i,j-1)) uldr |= 0b1000
          if (has_wall(i-1,j)) uldr |= 0b0100
          if (has_wall(i,j+1)) uldr |= 0b0010
          if (has_wall(i+1,j)) uldr |= 0b0001
          maze[index] = walls[uldr]
        endIf
      endWhile

    method visit( i:Int32, j:Int32, di:Int32, dj:Int32 )
      local mid_i = i + di
      local mid_j = j + dj
      i = mid_i + di
      j = mid_j + dj
      if (i < 0 or j < 0 or i >= width or j >= height) return
      local index = j * width + i
      if (maze[index] == ' ') return

      maze[mid_j*width+mid_i] = ' ' # 1 step
      maze[index] = ' '             # 2 steps

      local dirs = random_directions
      loop 4
        local dir = dirs & 3
        dirs = dirs :>>>: 2
        local offset = offsets[ dir ]
        visit( i, j, offset.x, offset.y )
      endLoop

    method random_directions->Int32
      local r1 = Random.int32(4)
      local r2 = Random.int32(3)
      local r3 = Random.int32(2)
      local d1 = r1
      local d2 = (r1 + r2 + 1) % 4
      local d3 = (r1 + (r2 + r3 + 1) % 3 + 1) % 4
      local d4 = (0 + 1 + 2 + 3) - (d1 + d2 + d3)
      return (d1:<<:6) | (d2:<<:4) | (d3:<<:2) | d4
      # Returns bits AABBCCDD, where each AA etc. is a direction 0-3.
endClass

MazeGen(109,25).display