2

Could someone help me to change the random walk to self-avoiding random walk? I tried to do that but not successful. Below is the code for the random walk.

THIS IS MY WORKING CODE.


def random_walk_3D(N):
    Nsteps = range(N)
    xp,yp,zp = [0],[0],[0]
    pos = [0,0,0]
    rand = np.random.uniform(0,1,N)
    for i in Nsteps:
        # depending on the random number go right
        # left, up or down
        if 0.00000 <= rand[i] < 1.0/6.0: pos[0] = pos[0]+1
        if 1.0/6.0 <= rand[i] < 2.0/6.0: pos[0] = pos[0]-1
        if 2.0/6.0 <= rand[i] < 3.0/6.0: pos[1] = pos[1]+1
        if 3.0/6.0 <= rand[i] < 4.0/6.0: pos[1] = pos[1]-1
        if 4.0/6.0 <= rand[i] < 5.0/6.0: pos[2] = pos[2]+1
        if 5.0/6.0 <= rand[i] < 6.0/6.0: pos[2] = pos[2]-1
        xp.append(pos[0])
        yp.append(pos[1])
        zp.append(pos[2])

    return xp,yp,zp
Hardik Shah
  • 4,042
  • 2
  • 20
  • 41

1 Answers1

0

I believe main problem here would be that self avoiding walk does not always have a fixed number of points it can go to. By definition any point can be visited only once, thus on each step the number of viable directions vary, and in your current code it is fixed.

You definitely should store the history of visited points in more friendly way. I would say a list of tuples in form (x, y, z) is a way to go. This allows you to check easier whether a direction you are considering to choose has been already visited. Generally in each step you should go as follow:

  1. determine which way the walker can go.
  2. choose the direction randomly with equal probability.
  3. save the position in history, as to not visit it again.

A simple code for this you can find below:

import random


def get_possible_directions(point):
    """Point is in form (x, y, z)"""
    directions = [
        (point[0]+1, point[1], point[2]),  # right
        (point[0]-1, point[1], point[2]),  # left
        (point[0], point[1]+1, point[2]),  # forward
        (point[0], point[1]-1, point[2]),  # backward
        (point[0], point[1], point[2]+1),  # up
        (point[0], point[1], point[2]-1)   # down
    ]
    return directions


def random_walk_3D(N):
    Nsteps = range(N)
    current_position = (0, 0, 0)
    visited_points = []
    for _ in Nsteps:
        visited_points.append(current_position)
        all_directions = get_possible_directions(current_position)
        not_visited_directions = [direction for direction in all_directions if direction not in visited_points]
        current_position = random.choice(not_visited_directions)

    xp, yp, zp = zip(*visited_points)
    return xp, yp, zp  # returns tuples. If you want lists, just do list(xp), ...


if __name__ == "__main__":
    x, y, z = random_walk_3D(10)
    print(x)
    print(y)
    print(z)

You might want to take a look at random documentation. As for the last step in function this could help you.

TheDecks
  • 86
  • 3