Skip to main content
Adicionei um link de aula válida sobre complexidade O(n).
Fonte Link
Icaro Martins
  • 4,3mil
  • 14
  • 24
  • 35

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aqui - aquioutro link  ).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aqui).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aqui - outro link  ).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aquiaqui).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aqui).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aqui).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}
Fonte Link
Caio Felipe Pereira
  • 4,6mil
  • 1
  • 19
  • 40

Curioso ninguém ter mencionado o Fisher-Yates, que talvez seja o algoritmo mais clássico para permutar um set finito. O mais interessante é o fato de todos os possíveis retornos do algoritmo serem igualmente prováveis (em inglês, o termo para isso é unbiased).

Aqui você pode ler um artigo interessante que mostra como construir esse algoritmo, desde o pseudo-código até um resultado de complexidade O(n) (você pode ler mais sobre complexidade aqui).

Para os TL;DR, a implementação final do algoritmo é

function shuffle(array) {
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}