So after some testing I've noticed some interesting results. Using the LRU page replacement algorithm hasn't really been yielding better results. Often enough it faults just as much as FIFO, sometimes even a couple more. At the best, it's performing a small percentage better.
For example, given a 1000 digit reference string and 15 page frames...
Number of frames: 15
FIFO Faults: 848
LRU Faults: 850
Obviously, this can't be correct. I've ran through this probably ~20 times and I get similar results every time and never do I see the expected results of ~35% less page faults using LRU.
I now understand a little more. I thought you were using different strings for them at the same time (hope that made sense, if not I will re-explain myself). But still a normal program (IMHO) would access memory more sequentially, maybe you should try ensuring your randomization algorithm has a slight tendency to use on of say the previous 5 results it has made?
PS: Thank you naraku9333, the pdf helped a lot with the visualization.