How to preserve array keys when removing elements?

Question

I'd like to build a text string by inserting the characters at random, but in place order (as a kind of effect) . So far I've got:

// make a string and an array
var input = "Hello, world!",
    output = [];
// split the string
input = input.split('');

My idea is then to call this

function addAnElement(){
  // check if there are any left
  if(input.length){
     // pick an element at random
     var rand = Math.floor(Math.random() * input.length);
     // remove it, so we don't call it again
     var element = input.splice(rand,1);
     // insert it
     output[rand] = element;
     // use the string returned as new innerHTML, for example 
     return output.join('');
     // repeat until finished
     setTimeout(addAnElement,5);
  }
}

I'm hoping this would return something like:

'e'
'er'
...
'Hel, or!'
...
'Helo, Word!'
... and finally ...
'Hello, World!'

The problem, of course, is that the array is re-indexed when spliced - and this yields gibberish. I think the answer must be to link the elements to their positions in input and then insert them intact, sorting by key if necessary before returning. How do I do this?

Answer 1

How about something like this:

var input = 'Hello world',
    inputIndexes = [],
    output = [];

for (var i = 0; i < input.length; i++) { 
    inputIndexes[i] = i;
};

function addAnElement() {
    if (inputIndexes.length) {
        var rand = Math.floor(Math.random() * inputIndexes.length);
        var element = inputIndexes.splice(rand, 1);
        output[element] = input[element];
        //console.log(output.join(' '));
        document.getElementById('text').innerHTML = output.join(' ');
        setTimeout(addAnElement, 2000);

    }
}

addAnElement();

http://jsfiddle.net/fg2ybz8j/

Answer 2

You can avoid it by not using splice. Instead, clear an entry when you've used it, and keep a count of the entries you've cleared.

E.g.:

var entriesLeft = input.length;
function addAnElement(){
   // pick an element at random, re-picking if we've already
   // picked that one
   var rand;
   do {
      rand = Math.floor(Math.random() * input.length);
   }
   while (!input[rand]);

   // get it
   var element = input[rand];
   // clear it, so we don't use it again
   input[rand] = undefined;
   // insert it
   output[rand] = element;
   // repeat until finished
   if (--entriesLeft) {
       setTimeout(addAnElement,5);
   }
   // use the string returned as new innerHTML, for example 
   return output.join('');
}

Of course, that loop picking a random number might go on a while for the last couple of characters. If you're worried about that, you can create a randomized array of the indexes to use up-front. This question and its answers address doing that.

Live Example:

var input = "Hello, there!".split("");
var output = [];
var entriesLeft = input.length;

function addAnElement() {
  // pick an element at random, re-picking if we've already
  // picked that one
  var rand;
  do {
    rand = Math.floor(Math.random() * input.length);
  }
  while (!input[rand]);

  // get it
  var element = input[rand];
  // clear it, so we don't use it again
  input[rand] = undefined;
  // insert it
  output[rand] = element;
  // repeat until finished
  if (--entriesLeft) {
    setTimeout(addAnElement, 5);
  }
  // use the string returned as new innerHTML, for example 
  document.body.innerHTML = output.join('');
}

addAnElement();

---

Side note: Notice how I've moved the call to setTimeout before the return. return exits the function, so there wouldn't be any call to setTimeout. That said, I'm confused by the need for the return output.join(''); at all; all calls but the first are via the timer mechanism, which doesn't care about the return value. In the live example, I've replaced that return with an assignment to document.body.innerHTML.

---

Here's a demonstration of the method that shuffles an array of indexes instead. It uses the shuffle method from this answer, but I'm not saying that's necessarily the best shuffle method.

function shuffle(array) {
  var tmp, current, top = array.length;
  if (top)
    while (--top) {
      current = Math.floor(Math.random() * (top + 1));
      tmp = array[current];
      array[current] = array[top];
      array[top] = tmp;
    }
  return array;
}

var input = "Hello, there".split("");
var output = [];
var indexes = input.map(function(entry, index) {
  return index;
});
shuffle(indexes);
var n = 0;

function addAnElement() {
  // get this index
  var index = indexes[n];
  // get this loop's element
  var element = input[index];
  // insert it
  output[index] = element;
  // repeat until finished
  if (++n < indexes.length) {
    setTimeout(addAnElement, 5);
  }
  // use the string returned as new innerHTML, for example 
  document.body.innerHTML = output.join("");
}

addAnElement();