retrieving elements from a list randomly

edited April 2017 in How To...

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 ;-)

Answers

  • Answer ✓

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

  • edited March 2018 Answer ✓

    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

  • thanks a lot!

  • 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;
    }
    //
    
  • edited March 2018 Answer ✓

    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;
    }
    
  • thanks a lot!

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

  • edited January 2017 Answer ✓

    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

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

  • I was asking that for doing Scrabble...

    ;-)

  • edited April 2017 Answer ✓

    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.

  • edited April 2017
    • @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
  • edited April 2017
    /**
     * 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();
    }
    
  • @GoToLoop I didn't suggest you don't know, just that others on this forum may not know.

Sign In or Register to comment.