How to efficiently build a random list from a given list without recurrences in JS?

Question

I have a comma separated string, out of which I need to create a new string which contains a random order of the items in the original string, while making sure there are no recurrences. For example: Running 1,2,3,1,3 will give 2,3,1 and another time 3,1,2, and so on.

I have a code which picks a random item in the original string, and then iterates over the new string to see if it does not exist already. If it does not exist - the item is inserted. However, I have a feeling this can be improved (in C# I would have used a hashtable, instead of iterating every time on the new array). One improvement can be removing the item we inserted from the original array, in order to prevent cases where the random number will give us the same result, for example.

I'd be happy if you could suggest improvements to the code below.

originalArray = originalList.split(',');            
for (var j = 0; j < originalArray.length; j++) {
    var iPlaceInOriginalArray = Math.round(Math.random() * (originalArray.length - 1));
    var bAlreadyExists = false;             
    for (var i = 0; i < newArray.length; i++) {
        if (newArray[i].toString() == originalArray[iPlaceInOriginalArray].toString()) {
            bAlreadyExists = true;
            break;
        }
    }

if (!bAlreadyExists)
    newArray.push(originalArray[iPlaceInOriginalArray]);
}

Thanks!

Answer 1

With your solution, you are not guaranteed not to pick same number several times, thus leaving some others of them never being picked. If the number of elements is not big (up to 100), deleting items from the source array will give the best result.
Edit

originalArray = originalList.split(',');            
for (var j = 0; j < originalArray.length; j++) {
    var iPlaceInOriginalArray = Math.round(Math.random() * (originalArray.length - 1 - j));
var bAlreadyExists = false;             
for (var i = 0; i < newArray.length; i++) {
    if (newArray[i].toString() == originalArray[iPlaceInOriginalArray].toString()) {
        bAlreadyExists = true;
        break;
    }
}

var tmp = originalArray[originalArray.length - 1 - j];
originalArray[originalArray.Length - 1 - j] = originalArray[iPlaceInOriginalArray];
originalArray[iPlaceInOriginalArray] = tmp;

if (!bAlreadyExists)
    newArray.push(originalArray[iPlaceInOriginalArray]);
}

Answer 2

You can still use a 'hash' in javascript to remove duplicates. Only in JS they're called objects:

function removeDuplicates(arr) {
    var hash = {};
    for (var i=0,l=arr.length;i<l;i++) {
        hash[arr[i]] = 1;
    }
    // now extract hash keys... ahem...
    // I mean object members:
    arr = [];
    for (var n in hash) {
        arr.push(n);
    }
    return arr;
}

Oh, and the select random from an array thing. If it's ok to destroy the original array (which in your case it is) then use splice:

function randInt (n) {return Math.floor(Math.random()*n)}

function shuffle (arr) {
    var out = [];
    while (arr.length) {
        out.push(
            arr.splice(
                randInt(arr.length),1 ));
    }
    return out;
}

// So:
newArray = shuffle(
               removeDuplicates(
                   string.split(',') ));

Answer 3

// If you sort the first array, it is quicker to skip duplicates, and you can splice each unique item into its random position as you build the new array.

var s= 'Function,String,Object,String,Array,Date,Error,String,String,'+ 'Math,Number,RegExp,Group,Collection,Timelog,Color,String';

var A1= s.split(',').sort(), A2= [], tem;
while(A1.length){
 tem= A1.shift();
 while(A1[0]== tem) tem= A1.shift();
 if(tem) A2.splice(Math.floor(Math.random()*A2.length), 0, tem);
}

alert(A2.join(', '))