javascript - जावास्क्रिप्ट सरणी को यादृच्छिक(शफल) कैसे करें?




arrays shuffle (20)

ईएस 6, 2018 के साथ

कुछ उत्तरों को नवीनतम ES6 के साथ छोटा किया जा सकता है।

जगह में शफल ऐरे

function shuffleArray (array){
    for (let i = array.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [array[i], array[rand]] = [array[rand], array[i]];
    }
}

ईएस 6 के साथ हम एक बार में दो मान असाइन कर सकते हैं। यह विशेष रूप से ऊपर पंक्ति 4 में आसान है, जहां कोड की एक पंक्ति में दो चर बदल दिए जाते हैं।

मूल ऐरे बरकरार रहें और एक शफल सरणी वापस करें

यदि आप अधिक शुद्ध फ़ंक्शन बनाना चाहते हैं, और मूल सरणी को बरकरार रखना चाहते हैं, तो आप सरणी को डुप्लिकेट कर सकते हैं और फिर उसी एल्गोरिदम को चला सकते हैं।

function getShuffledArray (arr){
    let newArr = [...arr]
    for (let i = newArr.length - 1; i > 0; i--) {
        const rand = Math.floor(Math.random() * (i + 1));
        [newArr[i], newArr[rand]]=[newArr[rand], newArr[i]];
    }
    return newArr;
}

एक आरोही एल्गोरिदम

नीचे एल्गोरिदम आरोही लूप का उपयोग करता है। यह कम सहज, अभी तक छोटा और मान्य है।

function getShuffledArrayAsc (arr){
    let newArr = [...arr];
    for (let i = 1; i < newArr.length ; i++) {
        const rand = Math.floor( Math.random() * (i + 1) ); 
        [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
    }
    return newArr;
}

यादृच्छिक कार्य की परीक्षण विश्वसनीयता

क्रोम में और नोड दोनों में नीचे 'testShuffledArrayFun' को पारित किए जाने पर ऊपर दिए गए कार्यों को भी वितरण प्रस्तुत किया गया। यह एक यादृच्छिक कार्य से हम क्या उम्मीद करेंगे के अनुसार है।

function testShuffledArrayFun(getShuffledArrayFun){
    // Tests the reliability of the suffleArrayFunction, by callying it 1,000 times and presenting the distribution. 
    const testArr = [0,1,2,3,4];
    const countArr = testArr.map( position => // for for each possible position in the shuffledArr, for each possible value, we'll create a counter. the counter of value 0 in position 0 will be countArr[0][0]
        testArr.map( value => 0)  
    )

    const n = 10000;
    for (var i=0 ; i<n ; i++){
        // We'll call getShuffledArrayFun for n times. For each shuffledArray we receive we'll increment the counterArr accordingly. At the end we'll print the distribution.
        var shuffledArr = getShuffledArrayFun(testArr);
        shuffledArr.forEach(
            (value, key) => {countArr[key][value]++}
        );
    }

    countArr.forEach(
        (valueCountArr,key) => {
            console.log(`Position ${key}:`);
            valueCountArr.forEach(
                (count,originalValue) => {
                    console.log(`The Value ${originalValue} appeared ${count*100/n}% `);
                }
            );
        }
    );
}

मेरे पास इस तरह की एक सरणी है:

var arr1 = ["a", "b", "c", "d"];

मैं इसे यादृच्छिक / शफल कैसे कर सकता हूं?


एक शफल फ़ंक्शन जो स्रोत सरणी को नहीं बदलता है

यहां मेरे 5 सेंट हैं। यदि आप स्रोत शेल को म्यूटेट करने के लिए अपने शफल फ़ंक्शन की कामना नहीं करते हैं , तो आप इसे स्थानीय चर में कॉपी कर सकते हैं, फिर बाकी को एक साधारण शफल तर्क के साथ करें

function shuffle(array) {
  var result = [], source = array.concat([]);

  while (source.length) {
    let index = Math.floor(Math.random() * source.length);
    result.push(source[index]);
    source.splice(index, 1);
  }

  return result;
}

Shuffling logic : pick up a random index, then add the corresponding element to the result array and delete it from the source array copy . Repeat this action until the source array gets empty .

And if you really want it short, here's how far I could get:

function shuffle(array) {
  var result = [], source = array.concat([]);

  while (source.length) {
    let index = Math.floor(Math.random() * source.length);
    result.push(source.splice(index, 1)[0]);
  }

  return result;
}

CoolAJ86 के answer का एक सरल संशोधन जो मूल सरणी को संशोधित नहीं करता है

 /**
 * Returns a new array whose contents are a copy shuffled of the array.
 * @param {Array} a items to shuffle.
 * https://.com/a/2450976/1673761
 */
const shuffle = (array) => {
  let currentIndex = array.length;
  let temporaryValue;
  let randomIndex;
  const newArray = array.slice();
  // While there remain elements to shuffle...
  while (currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    // And swap it with the current element.
    temporaryValue = newArray[currentIndex];
    newArray[currentIndex] = newArray[randomIndex];
    newArray[randomIndex] = temporaryValue;
  }
  return newArray;
};

ES2015 के साथ आप इसका उपयोग कर सकते हैं:

Array.prototype.shuffle = function() {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]]
  }
  return this;
}

उपयोग:

[1, 2, 3, 4, 5, 6, 7].shuffle();

[समुदाय संपादित करें: यह उत्तर गलत है; टिप्पणी देखो। इसे भविष्य के संदर्भ के लिए यहां छोड़ा जा रहा है क्योंकि विचार दुर्लभ नहीं है।]

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});

अन्य सभी उत्तर Math.random () पर आधारित हैं जो तेज़ है लेकिन क्रिप्टोग्राफिक स्तर यादृच्छिकरण के लिए उपयुक्त नहीं है।

यादृच्छिकरण के क्रिप्टोग्राफिक स्तर के लिए Web Cryptography API का उपयोग करते समय नीचे दिया गया कोड प्रसिद्ध Fisher-Yates एल्गोरिदम का उपयोग कर रहा है।

var d = [1,2,3,4,5,6,7,8,9,10];

function shuffle(a) {
	var x, t, r = new Uint32Array(1);
	for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) {
		crypto.getRandomValues(r);
		x = Math.floor(r / 65536 / 65536 * m) + i;
		t = a [i], a [i] = a [x], a [x] = t;
	}

	return a;
}

console.log(shuffle(d));


एक पुनरावर्ती समाधान:

function shuffle(a,b){
    return a.length==0?b:function(c){
        return shuffle(a,(b||[]).concat(c));
    }(a.splice(Math.floor(Math.random()*a.length),1));
};

कोई ऐरे से प्रोटोटाइप के रूप में इसका उपयोग कर सकता है (या चाहिए):

क्रिस्टोफ से:

Array.prototype.shuffle = function() {
  var i = this.length, j, temp;
  if ( i == 0 ) return this;
  while ( --i ) {
     j = Math.floor( Math.random() * ( i + 1 ) );
     temp = this[i];
     this[i] = this[j];
     this[j] = temp;
  }
  return this;
}

डी-फैक्टो निष्पक्ष शफल एल्गोरिदम फिशर-येट्स (उर्फ नुथ) शफल है।

https://github.com/coolaj86/knuth-shuffle देखें

आप यहां एक महान दृश्यता देख सकते हैं (और मूल पोस्ट इस से जुड़ा हुआ है )

function shuffle(array) {
  var currentIndex = array.length, temporaryValue, randomIndex;

  // While there remain elements to shuffle...
  while (0 !== currentIndex) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    // And swap it with the current element.
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }

  return array;
}

// Used like so
var arr = [2, 11, 37, 42];
arr = shuffle(arr);
console.log(arr);

इस्तेमाल किए गए एल्गोरिदम के बारे में कुछ और जानकारी।


नया!

छोटे और शायद * तेजी से फिशर-येट्स शफल एल्गोरिदम

  1. यह उपयोग करता है ---
  2. फर्श के लिए bitwise (10 दशमलव अंकों तक संख्या (32 बिट))
  3. अनावश्यक बंद और अन्य सामान हटा दिया
function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d
}

स्क्रिप्ट आकार (फ़ंक्शन नाम के रूप में fy के साथ): 90bytes

डेमो http://jsfiddle.net/vvpoma8w/

* शायद क्रोम को छोड़कर सभी ब्राउज़रों पर तेजी से।

अगर आप को कोई भी सवाल है, तो बस पूछो।

संपादित करें

हाँ यह तेज़ है

प्रदर्शन: http://jsperf.com/fyshuffle

शीर्ष मतदान कार्यों का उपयोग कर।

संपादित करें अतिरिक्त में एक गणना थी (की आवश्यकता नहीं है - सी + 1) और कोई भी ध्यान नहीं दिया

छोटा (4bytes) और तेज़ (परीक्षण करें!)।

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d
}

कैचिंग कहीं और var rnd=Math.random और फिर rnd() उपयोग बड़े सरणी पर थोड़ा सा प्रदर्शन भी बढ़ाएगा।

http://jsfiddle.net/vvpoma8w/2/

पठनीय संस्करण (मूल संस्करण का उपयोग करें। यह धीमा है, बंद बेकार हैं, बंद होने की तरह और ";", कोड स्वयं भी छोटा है ... शायद इसे पढ़ें जावास्क्रिप्ट कोड को 'छोटा करें' कैसे करें , बीटीडब्ल्यू आप सक्षम नहीं हैं उपरोक्त की तरह जावास्क्रिप्ट मिनीफायर में निम्न कोड को संपीड़ित करें।)

function fisherYates( array ){
 var count = array.length,
     randomnumber,
     temp;
 while( count ){
  randomnumber = Math.random() * count-- | 0;
  temp = array[count];
  array[count] = array[randomnumber];
  array[randomnumber] = temp
 }
}

मुझे इस प्रश्न के डुप्लिकेट पर "लेखक द्वारा हटाए गए" उत्तरों में लटकने वाला यह संस्करण मिला। कुछ अन्य उत्तरों के विपरीत जिनके पास पहले से ही कई अपवॉट हैं, यह है:

  1. असल में यादृच्छिक
  2. जगह में नहीं (इसलिए shuffle बजाए shuffle नाम)
  3. कई प्रकारों के साथ यहां पहले से मौजूद नहीं है

यहां एक jsfiddle उपयोग में दिखा रहा है

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}

यहां फिशर-येट्स का एक कंप्यूटर-अनुकूलित संस्करण, डर्स्टनफेल्ड शफल का एक जावास्क्रिप्ट कार्यान्वयन है:

/**
 * Randomize array element order in-place.
 * Using Durstenfeld shuffle algorithm.
 */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

फिशर-येट्स एल्गोरिदम प्रत्येक मूल सरणी तत्व के लिए एक यादृच्छिक तत्व चुनकर काम करता है, और उसके बाद इसे अगले ड्रॉ से बाहर कर देता है। कार्ड के डेक से यादृच्छिक रूप से चुनने की तरह।

यह बहिष्कार वर्तमान तत्व के साथ चुने हुए तत्व को स्वैप करके और शेष से अगले यादृच्छिक तत्व को चुनकर एक चालाक तरीके से किया जाता है (कंप्यूटर द्वारा उपयोग के लिए Durstenfeld द्वारा आविष्कार किया गया)। इष्टतम दक्षता के लिए, लूप पीछे की ओर चलता है ताकि यादृच्छिक पिक सरलीकृत हो (यह हमेशा 0 पर शुरू हो सकता है), और यह अंतिम तत्व छोड़ देता है क्योंकि अब कोई अन्य विकल्प नहीं है।

इस एल्गोरिदम का चलने का समय ओ (एन) है। ध्यान दें कि शफल जगह में किया जाता है। इसलिए यदि आप मूल सरणी को संशोधित नहीं करना चाहते हैं, तो इसकी प्रतिलिपि पहले .slice(0) साथ .slice(0)

ES6 / ECMAScript 2015 को अपडेट कर रहा है

नया ES6 हमें एक बार में दो चर निर्दिष्ट करने की अनुमति देता है। यह विशेष रूप से आसान होता है जब हम दो चर के मानों को स्वैप करना चाहते हैं, क्योंकि हम इसे कोड की एक पंक्ति में कर सकते हैं। इस सुविधा का उपयोग करते हुए, एक ही फ़ंक्शन का एक छोटा रूप यहां दिया गया है।

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

सबसे छोटा arrayShuffle समारोह

function arrayShuffle(o) {
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
}

सबसे पहले, जावास्क्रिप्ट में विभिन्न सॉर्टिंग विधियों की एक शानदार दृश्य तुलना के लिए bost.ocks.org/mike/shuffle/compare.html

दूसरा, यदि आपके ऊपर उपरोक्त लिंक पर एक त्वरित नज़र डाली है तो आपको पता चलेगा कि random order अन्य तरीकों की तुलना में अपेक्षाकृत अच्छी तरह से प्रदर्शन करता प्रतीत होता है, जबकि नीचे दिखाए गए अनुसार बेहद आसान और तेज़ करने के लिए तेज़ है:

function shuffle(array) {
  var random = array.map(Math.random);
  array.sort(function(a, b) {
    return random[array.indexOf(a)] - random[array.indexOf(b)];
  });
}

संपादित करें : जैसा कि @ एग्रीर्स द्वारा इंगित किया गया है, तुलना फ़ंक्शन को सूचकांक के बजाय मूल्यों के साथ बुलाया जाता है, यही कारण है कि आपको indexOf का उपयोग करने की आवश्यकता है। ध्यान दें कि यह परिवर्तन कोड को बड़े सरणी के लिए उपयुक्त बनाता है क्योंकि indexOf ओ (एन) समय में चलता है।


Fisher-Yates जावास्क्रिप्ट में shuffle। मैं इसे यहां पोस्ट कर रहा हूं क्योंकि दो उपयोगिता कार्यों (स्वैप और रैंडआईन्ट) का उपयोग यहां अन्य उत्तरों की तुलना में एल्गोरिदम को स्पष्ट करता है।

function swap(arr, i, j) { 
  // swaps two elements of an array in place
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function randInt(max) { 
  // returns random integer between 0 and max-1 inclusive.
  return Math.floor(Math.random()*max);
}
function shuffle(arr) {
  // For each slot in the array (starting at the end), 
  // pick an element randomly from the unplaced elements and
  // place it in the slot, exchanging places with the 
  // element in the slot. 
  for(var slot = arr.length - 1; slot > 0; slot--){
    var element = randInt(slot+1);
    swap(arr, element, slot);
  }
}

Randomize array

 var arr = ['apple','cat','Adam','123','Zorro','petunia']; 
 var n = arr.length; var tempArr = [];

 for ( var i = 0; i < n-1; i++ ) {

    // The following line removes one random element from arr 
     // and pushes it onto tempArr 
     tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]);
 }

 // Push the remaining item onto tempArr 
 tempArr.push(arr[0]); 
 arr=tempArr; 

From a theoretical point of view, the most elegant way of doing it, in my humble opinion, is to get a single random number between 0 and n!-1 and to compute a one to one mapping from {0, 1, …, n!-1} to all permutations of (0, 1, 2, …, n-1) . As long as you can use a (pseudo-)random generator reliable enough for getting such a number without any significant bias, you have enough information in it for achieving what you want without needing several other random numbers.

When computing with IEEE754 double precision floating numbers, you can expect your random generator to provide about 15 decimals. Since you have 15!=1,307,674,368,000 (with 13 digits), you can use the following functions with arrays containing up to 15 elements and assume there will be no significant bias with arrays containing up to 14 elements. If you work on a fixed-size problem requiring to compute many times this shuffle operation, you may want to try the following code which may be faster than other codes since it uses Math.random only once (it involves several copy operations however).

The following function will not be used, but I give it anyway; it returns the index of a given permutation of (0, 1, 2, …, n-1) according to the one to one mapping used in this message (the most natural one when enumerating permuations); it is intended to work with up to 16 elements:

function permIndex(p) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
    var tail = [];
    var i;
    if (p.length == 0) return 0;
    for(i=1;i<(p.length);i++) {
        if (p[i] > p[0]) tail.push(p[i]-1);
        else tail.push(p[i]);
    }
    return p[0] * fact[p.length-1] + permIndex(tail);
}

The reciprocal of the previous function (required for your own question) is below; it is intended to work with up to 16 elements; it returns the permutation of order n of (0, 1, 2, …, s-1) :

function permNth(n, s) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
    var i, j;
    var p = [];
    var q = [];
    for(i=0;i<s;i++) p.push(i);
    for(i=s-1; i>=0; i--) {
        j = Math.floor(n / fact[i]);
        n -= j*fact[i];
        q.push(p[j]);
        for(;j<i;j++) p[j]=p[j+1];
    }
    return q;
}

Now, what you want merely is:

function shuffle(p) {
    var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000];
    return permNth(Math.floor(Math.random()*fact[p.length]), p.length).map(
            function(i) { return p[i]; });
}

It should work for up to 16 elements with a little theoretical bias (though unnoticeable from a practical point of view); it can be seen as fully usable for 15 elements; with arrays containing less than 14 elements, you can safely consider there will be absolutely no bias.


Randomize array using array.splice()

function shuffleArray(array) {
   var temp = [];
   var len=array.length;
   while(len){
      temp.push(array.splice(Math.floor(Math.random()*array.length),1)[0]);
      len--;
   }
   return temp;
}
//console.log("Here >>> "+shuffleArray([4,2,3,5,8,1,0]));

demo


Array.prototype.shuffle=function(){
   var len = this.length,temp,i
   while(len){
    i=Math.random()*len-- |0;
    temp=this[len],this[len]=this[i],this[i]=temp;
   }
   return this;
}

var shuffle = function(array) {
   temp = [];
   for (var i = 0; i < array.length ; i++) {
     temp.push(array.splice(Math.floor(Math.random()*array.length),1));
   }
   return temp;
};




shuffle