Generating a random order.

Eeyorelife

I can't remember why, but I've decided that I want to figure out how to generate a random order with no repeats. My sketch picks out the numbers 1 through 4 in a random order. I have hard coded it so that each number checks if it is equal to any of the previous numbers and then picks a new number if it is. This makes it tedious to change the size of the array n. So I'd like a more generic code where I can change the size of the array and the rest solves itself.

void setup() {
  int [] n = new int[4];
  for ( int i=0; i<4; i++) {
    n[i] = int(random(4));


    if (i = 1) {
      while (n[i] == n[0]) {
        n[i] = int(random(4));
      }
    }

    if (i = 2) {
      while (n[i] == n[0] || n[i] == n[1]) {
        n[i] = int(random(4));
      }
    }

    if (i = 3) {
      while (n[i] == n[0] || n[i] == n[1] || n[i] == n[2]) {
        n[i] = int(random(4));
      }
    }
  }


  println(n[0]);
  println(n[1]);
  println(n[2]);
  println(n[3]);
}

jeremydouglass

@Eeyorelife --

If you use an IntList rather than an int[] array, you can use the built-in shuffle() method, which does exactly what you want:

https://processing.org/reference/IntList_shuffle_.html

If you really want to shuffle an int[], you have to implement it yourself. Our very own @PhiLo of this forum currently has the top-rated answer on StackOverflow for how to do this.

http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array

There are dozens of closely related approaches, but honestly it is a bit of a pain.

I actually recently wrote a method like this to shuffle a list of colors. Here it is:

int[] colorsArrayShuffle (int count, int[] colorValues) {
  // shuffle, then take top n -- as per http://stackoverflow.com/a/8115744/7207622
  // by shuffling an int array as per http://stackoverflow.com/a/1520212/7207622
  int[] array = colorsArray(colorValues);
  int index, temp;
  for (int i = array.length - 1; i > 0; i--)
  {
    index = (int)random(i + 1);
    temp = array[index];
    array[index] = array[i];
    array[i] = temp;
  }
  return subset(array, 0, count);
}

Eeyorelife

I actually new about the IntList shuffle(), but I wanted to be able to do it without it. Because I'm stubborn.

That's a really neat way to do it @jeremydouglass ! But I really don't understand how it works. Would you mind explaining it to me?

I actually managed to solve it myself like thi:

int num = 6;
int [] n = new int[num];

void setup() {
  for ( int i=0; i<num; i++) {
    n[i] = int(random(num));
    boolean redo = false;

    while (1==1) {
      for (int j=0; j<i; j++) {
        if (n[i] == n[j]) redo = true;
      }
      if (redo) {
        n[i] = int(random(num));
        redo = false;
      } else break;
    }
    println(n[i]);
  }

}

It's not as compact as your solution, but it works.

jeremydouglass

@Eeyorelife --

The code says:

for (int i = array.length - 1; i > 0; i--) {

"Walk backwards through an array. At each step..."

  index = (int)random(i + 1);
  temp = array[index];

"...pick any index from the beginning to where we are now, and set it aside."

  array[index] = array[i];
  array[i] = temp;

"Swap the current index value with that one."

}

When you get to index 1 and swap it with either index 0 or itself, you are done!

Note that this performs exactly length swaps. It also allows self swaps, so all potential array orders are possible. If you shuffle {1,2} you could get back either {1,2} or {2,1}. Many implementations make a mistake on this so that shuffling {1,2} can only return {2,1} and nothing else.

Eeyorelife

Thanks a lot @jeremydouglass !

I still have some questions about the code though, if you don't mind.

Walk backwards through an array

Why? Why do you walk backwards? You are not adding or removing anything?

pick any index from the beginning to where we are now

Why? Why not pick any one? Why does it have to be one between now and the start?

It's an ingenious solution. I was really focused on checking every number, so this blew my mind.

jeremydouglass

@Eeyorelife --

Why do you walk backwards?

Why not pick any one?

These answers are related. See discussion of the Fisher Yates shuffle and the Durstenfeld implementation for computer science:

• https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm

Imagine two pieces of paper. After each step you cross out a number somewhere on the old list and add that number to the new list. This loop is just storing that new list at the end of the old one! They are your answers. Each step the new list gets longer by one number and the old list gets shorter, until one has been replaced by the other.

So, for an unshuffled list:

0,1,2,3,4,5

The shuffle walks back through it, swapping:

0,1,2,3,4,5  |
          ^
0,1,2,3,5    |  4
        ^
0,5,2,3      |  1,4
      ^
3,5,2        |  0,1,4
    ^

It randomly chose "4,1,0" in order, then wrote them backwards on the new list. The numbers still left on the old list look shuffled, but that doesn't matter -- 3, 5, and 2 are all equally likely of being the next number. The real shuffling that has happened so far is the 0,1,4.

2,5           |  3,0,1,4
  ^
              |  2,5,3,0,1,4

Notice that the last swap happened to swap "5" with "5" -- a self-swap. If this wasn't possible, all shuffle combinations would not be equally likely (and some would be impossible).

So the final result is:

2,5,3,0,1,4

If it helps, imagine a basket full of balls with numbers written on them. The algorithm pulled out the balls 4, 1, 0, 3, 5, 2. Each single swap pulls out and then sets aside a ball that is still in the basket and then sets it aside. Moving the index is "setting the ball aside" as part of the answer, and then getting the next part of the answer from the smaller basket.

Note also that walking backwards is a design pattern that in general makes array code safe for additions or deletions. If you modified the code later, the fact that you chose a backwards order by default makes it robust. If you forget that it isn't backwards, you might easily introduce bugs, skipping an item or referring to one that doesn't exist etc. etc. For this reason many people just make all their array access loops backwards unless there is a good reason not to.

Eeyorelife

That's awesome! The wikipedia article really helped!

Two more questions:

They look shuffled, but... Well, they are shuffled, aren't they? Could you not just do this, and save some time:

int[] colorsArrayShuffle (int count, int[] colorValues) {
  // shuffle, then take top n -- as per <a href="http://stackoverflow.com/a/8115744/7207622" target="_blank" rel="nofollow">http://stackoverflow.com/a/8115744/7207622</a>;
  // by shuffling an int array as per <a href="http://stackoverflow.com/a/1520212/7207622" target="_blank" rel="nofollow">http://stackoverflow.com/a/1520212/7207622</a>;
  int[] array = colorsArray(colorValues);
  int index, temp;
  for (int i = int((array.length)/2); i > 0; i--)
  {
    index = (int)random(i + 1);
    temp = array[index];
    array[index] = array[i];
    array[i] = temp;
  }
  return subset(array, 0, count);
}

And still, why not pick any number? Your solution of restriction:

0,1,2,3,*4*,5

0,*1*,2,3,5     |  4

*0*,5,2,3       |  1,4

*3*,5,2         |  0,1,4

*2*,5           |  3,0,1,4

                     |  5,2,3,0,1,4
Result: 5,2,3,0,1,4

My alternative solution of liberty:

0,1,*2*,3,4,5

0,*1*,5,3,4      | 2

0,4,5,*3*        | 1,2

0,4,5              | 3,*1*,2

*0*,4,1          | 3,5,2

1,4                | 0,3,5,2

Result 1,4,0,3,5,2

Does this makes sense or am I being an asshat now?

jeremydouglass

Could you not just do this, and save some time?

Please explain what you mean.

My alternative solution of liberty

If I recall (and this is not my area of expertise) the issue is either that "liberty" is less efficient, or that it gives results in which different orderings are not equally probable, or both.

You could test this easily yourself. Run your restriction() and liberty() 1,000,000 times each on {1,2,3}. Tally the results -- there are only 6 possible results (123,132,213,231,312,321). Are all orders equally likely from both? How long did each take to run?

Eeyorelife

When you've come this far: 3,5,2 | 0,1,4 you have a seemingly random order. If you do the three last steps you have a random order, but what you're left with so far is probably good enough. So if you mix up one half of the numbers you automatically mix up the other half as well. My theory: it looks random, therefore it is.

You are most likely right. With your method you are guaranteed a completely random order. But is that even possible? Is possible to achieve true randomness?

Java calculates a random number by multiplying a seed value with a bunch of predetermined values. The seed is most likely the current time in milliseconds. But because the calculations are predetermined, the number can never be truly random. So if you are depending on a true random number, or as close as you can get, for example because of security reasons, you should not use the built in function random(). And in most cases, you don't ned a completely random number, you just need a number that is very hard to predict. Not impossible to predict, because that is impossible, but very hard.

So my theory is still: it looks random, therefore it is.

Eeyorelife

Thank you for your input @jeremydouglass

I learned some really neat stuff.

jeremydouglass

I see what you mean about shuffling half-way. It does produce an out-of-order sequence -- and fast! It has a problem, though.

Consider this:

1,2,3,4

Now we shuffle it to produce a secret password. Shuffle is permutations, and permutations are computed by factorial: 4x3x2x1. So there are 24 possible passwords, right?

No. In this case there are not that many possible passwords, which makes the shuffle much less random, even though it looks random. For example, try swapping halfway to create these results:

1,2,3,4 -> 3,4,2,1
1,2,3,4 -> 4,1,2,3

You can't do it. So if "shuffle" means "like a deck of cards" then swapping only halfway through the list doesn't work, because there are secret rules about which outcomes can happen and which ones can't.