retrieving elements from a list randomly

Chrisir

hello all,

obviously an old problem. It occurs in different forms.

E.g. in a scrabble game we have to hand out letters to the players. But they are not distributed evenly over the Alphabet, so there are not as many Qs than Es in the game (reflecting the distribution of letters in normal English texts).

Let's therefore assume, I make a char array, where this distribution is reflected, so it's

EEEEEEEEEQAAAAAAMMOO or so.

Now retrieving elements from this list randomly:

When I retrieved a letter I can't retrieve it again. I can replace it with a character that is a stop sign like #.

EEEEE#EEEQAAAAAAMMOO

But then when retrieving a letter later in the game, most slots hold #-signs.

##E################O#

So a typical random like

randomNumberIndex = int(random(listOfLetters.length())); would most times fail, so I would have to repeat it until hitting a letter. Bad.

But what is the most efficient way of solving this? An ArrayList and then shorten the ArrayList ?

Thanks!

Best, Chrisir ;-)

GoToLoop

Shuffle the array! Then pick each char from beginning to end. *-:)

GoToLoop

A pity Processing doesn't provide a shuffle() array utility like it does for sort(). :(

There's 1 for p5.js. It's a piece of cake to convert it to Java: :)>-
https://GitHub.com/processing/p5.js/blob/master/src/utilities/array_functions.js#L207-#L223

Chrisir

thanks a lot!

Chrisir

int[] testList = {
  0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6
}; 


void setup() {
  size(1400, 99);
  background(0);

  printArray(testList);
  println (""); 

  testList=shuffleArray(testList);
  printArray(testList);
  //
}

void draw() {
  //
}

// ------------------------------------------

int[] shuffleArray (int[] arr) {

  // Randomizes the order of the elements of an array. Implements
  // http : // Bost.Ocks.org/mike/shuffle/ 
  // Fisher-Yates Shuffle Algorithm

  int idx = arr.length;

  while (idx > 1) {

    int rnd = int ( random(idx) ) ;

    // swap 
    int tmp = arr[--idx];
    arr[idx] = arr[rnd];
    arr[rnd] = tmp;
  }

  return arr;
}
//

GoToLoop

You were fast! Here's mine as well. Just finished it: :P

/**
 * Shuffle Char Array (v1.03)
 * GoToLoop (2017-Jan-29)
 *
 * Forum.Processing.org/two/discussion/20529/
 * retrieving-elements-from-a-list-randomly#Item_5
 */

final char[] letters = "EEEEEEEEEQAAAAAAMMOO".toCharArray();

void setup() {
  println(str(letters));
  shuffle(letters);
  println(str(letters));
  exit();
}

@ SafeVarargs final char[] shuffle(final char... arr) {
  if (arr == null)  return null;

  int idx = arr.length;

  while (idx > 1) { 
    final int rnd = (int) random(idx--);
    final char tmp = arr[idx];
    arr[idx] = arr[rnd];
    arr[rnd] = tmp;
  }

  return arr;
}

Chrisir

thanks a lot!

shuffle is much better than shortening an ArrayList on the way as my first idea was........ ;-)

GoToLoop

Well, for lists, how about IntList? It's got a shuffle() method already: *-:)
https://Processing.org/reference/IntList_shuffle_.html

Besides int[], we can use it for char[], short[], byte[] and even boolean[].
Just use int() to convert the array type to int[], passing it to IntList's constructor:
https://Processing.org/reference/intconvert_.html

After shuffle(), use array() to get an int[] again from it:
https://Processing.org/reference/IntList_array_.html

Finally, use char(), byte() or boolean() in order to get the original array type back: :ar!

1. https://Processing.org/reference/charconvert_.html
2. https://Processing.org/reference/byteconvert_.html
3. https://Processing.org/reference/booleanconvert_.html

Of course, that's miles slower than implementing our own shuffle() for each desired array type. 8-X

Lord_of_the_Galaxy

P.S. Shuffle already exists - Collections.shuffle()

Chrisir

I was asking that for doing Scrabble...

;-)

Lord_of_the_Galaxy

And I used Collections.shuffle() ;)

But, as you already know, I posted that because that's what this forum is for - if anyone wants to shuffle, they can find it here now.

GoToLoop

• @Lord_of_the_Galaxy, I knew already that shuffle() exists as an utility function for Collection containers. :-\"
• I've even mentioned IntList::shuffle() here as another alternative approach too. :P
• However, its array counterpart doesn't exist for reasons unknown! :-@
• That's why I've made a customized 1 just for char[] arrays. \m/
• It spares us the time & memory spent to instantiate another container only to use its shuffle() method. #:-S

GoToLoop

/**
 * Shuffle Char Array via IntList (v1.0)
 * GoToLoop (2017-Apr-27)
 *
 * forum.Processing.org/two/discussion/20529/
 * retrieving-elements-from-a-list-randomly#Item_12
 */

char[] letters = "EEEEEEEEEQAAAAAAMMOO".toCharArray();

void setup() {
  println(str(letters));

  IntList il = new IntList(int(letters));
  il.shuffle(this);

  letters = char(il.array());
  println(str(letters));

  exit();
}

Lord_of_the_Galaxy

@GoToLoop I didn't suggest you don't know, just that others on this forum may not know.