[javascript] JavaScript 배열을 무작위 화하는 방법은 무엇입니까?

다음과 같은 배열이 있습니다.

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

랜덤 화 / 셔플하는 방법은 무엇입니까?

답변

사실상의 비 편향 셔플 알고리즘은 Fisher-Yates (일명 Knuth) 셔플입니다.

참조 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];
shuffle(arr);
console.log(arr);

스 니펫 확장

사용 된 알고리즘에 대한 추가 정보

답변

Fisher-Yates의 최적화 된 버전 인 Durstenfeld shuffle 의 JavaScript 구현은 다음과 같습니다 .

/* Randomize array 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;
    }
}

각 원본 배열 요소에 대해 임의의 요소를 선택하고 카드 덱에서 무작위로 선택하는 것처럼 다음 추첨에서 제외합니다.

이 영리한 제외는 선택한 요소를 현재 요소와 교체 한 다음 나머지 요소에서 다음 임의 요소를 선택하여 최적의 효율성을 위해 뒤로 반복하여 임의 선택이 단순화되고 (항상 0에서 시작할 수 있음) 최종 요소를 건너 뜁니다.

알고리즘 런타임은 O(n)입니다. 참고 먼저, 원래의 배열은 수정과의 복사본을 만들고 싶어하지 않는, 그래서 만약 셔플이 자리에서 이루어집니다 .slice(0).

편집하다: ES6 / ECMAScript 2015로 업데이트

새로운 ES6을 사용하면 한 번에 두 개의 변수를 할당 할 수 있습니다. 이것은 한 줄의 코드로 할 수 있기 때문에 두 변수의 값을 바꾸고 싶을 때 특히 유용합니다. 이 기능을 사용하는 동일한 기능의 짧은 형식은 다음과 같습니다.

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

답변

경고!
이 알고리즘 은 비효율적 이고 강력하게 편향되어 있으므로 사용 하지 않는 것이 좋습니다 . 의견을 참조하십시오. 아이디어가 그렇게 드물지 않기 때문에 나중에 참조하기 위해 여기에 남겨두고 있습니다.

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

답변

Array의 protoype로 사용할 수 있거나 사용해야합니다.

ChristopheD에서 :

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

답변

맵과 정렬로 쉽게 할 수 있습니다.

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]

let shuffled = unshuffled
  .map((a) => ({sort: Math.random(), value: a}))
  .sort((a, b) => a.sort - b.sort)
  .map((a) => a.value)

배열의 각 요소를 객체에 넣고 무작위 정렬 키를 제공합니다.
우리는 임의의 키를 사용하여 정렬
원본 객체를 얻기 위해 매핑을 해제합니다

다형성 배열을 섞을 수 있으며 정렬은 Math.random만큼 임의적이며 대부분의 목적에 충분합니다.

요소는 각 반복을 재생성하지 않는 일관된 키에 대해 정렬되고 각 비교는 동일한 분포에서 가져 오기 때문에 Math.random 분포의 비 랜덤 성은 취소됩니다.

속도

시간 복잡도는 빠른 정렬과 마찬가지로 O (N log N)입니다. 공간 복잡도는 O (N)입니다. 이것은 Fischer Yates shuffle만큼 효율적이지 않지만 제 의견으로는 코드가 상당히 짧고 기능적입니다. 배열이 큰 경우 Fischer Yates를 사용해야합니다. 수백 개의 항목이있는 작은 배열이있는 경우이 작업을 수행 할 수 있습니다.

답변

underscore.js 라이브러리를 사용하십시오. 이 방법 _.shuffle()은 좋습니다. 다음은 그 방법에 대한 예입니다.

var _ = require("underscore");

var arr = [1,2,3,4,5,6];
// Testing _.shuffle
var testShuffle = function () {
  var indexOne = 0;
    var stObj = {
      '0': 0,
      '1': 1,
      '2': 2,
      '3': 3,
      '4': 4,
      '5': 5
    };
    for (var i = 0; i < 1000; i++) {
      arr = _.shuffle(arr);
      indexOne = _.indexOf(arr, 1);
      stObj[indexOne] ++;
    }
    console.log(stObj);
};
testShuffle();

답변

새로운!

더 짧고 아마도 더 빠른 Fisher-Yates shuffle 알고리즘

그것은 동안 사용합니다 —
비트 단위부터 바닥까지 (십진수 10 자리 (32 비트)까지)
불필요한 폐쇄 및 기타 물건 제거

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) : 90 바이트

데모
http://jsfiddle.net/vvpoma8w/

* 크롬을 제외한 모든 브라우저에서 더 빠를 것입니다.

궁금한 점이 있으면 물어보십시오.

편집하다

네 빠릅니다

성능 : http://jsperf.com/fyshuffle

최고 투표 기능 사용.

편집
초과 계산이 있었으며 (-c + 1 필요 없음) 아무도 눈치 채지 못했습니다.

더 짧고 (4 바이트) 더 빠릅니다 (테스트 해보세요!).

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/

읽기 가능 버전 (원래 버전을 사용이 느린, 바르가 폐쇄 및처럼 쓸모. “;”, 코드 자체도 짧은 … 어쩌면이 글을 읽을 방법 ‘작게하다’자바 스크립트 코드 BTW, 당신은 할 수 없습니다 위의 코드와 같은 자바 스크립트 축소 기에서 다음 코드를 압축하십시오.)

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
 }
}