Uma maneira eficiente de aleatoriamente uma matriz - código de embaralhamento

Question

Fiquei feito essa pergunta em uma entrevista e dei várias soluções, mas o entrevistador não estava convencido. Estou interessado em encontrar uma solução. Por favor, jogue seus pontos de vista:

P: Escreva uma estrutura de dados eficiente para implementar o Shuffle em um iPod. Ele deve tocar todas as músicas, cada vez em ordem aleatória diferente, a mesma música não deve ser repetida. (principalmente O (n))

Uma solução, pensei depois da entrevista: posso fazer uma classificação rápida randomizada sem recursão. Onde nós escolhemos aleatoriamente 1 pivô O (1) e depois fazemos o Quicksort O (n). Agora, as músicas serão classificadas em alguma ordem e eu as toco até o fim. Quando chegar ao fim, vou escolher novamente um pivô aleatório e, repetir esse processo repetidamente.

Atenciosamente, Sethu

Answer 1

Coloque todas as músicas em uma matriz ... para cada elemento na matriz, trocam -a com uma posição aleatória.

Answer 2

Você quer o Fisher-Yates Shuffle. Esteja ciente dos erros de implementação mencionados nessa página, pois sua resposta atualmente aceita cai em um.

Answer 3

Bem, a primeira solução de tempo linear que vem à mente:

Você pode fazer uma lista vinculada de todas as músicas, que levariam sobre O (n) (dado que as inserções são operações de tempo constantes). Em seguida, gerar um número aleatório, módulo do tamanho da lista para obter um índice aleatório e remover esse índice e anexá -lo a uma nova lista (ambas são operações de tempo constantes).

Uma inserção para cada remoção O (n) + A para cada O (n) + uma segunda inserção o (n). Isso levaria em geral a uma solução de tempo linear.

Editar: Eu esqueci completamente de caminhar pela lista. Então, em vez disso, você pode fazer do resultado uma matriz de comprimento fixo. Coloque a cabeça da lista vinculada, atribua -lhe o índice aleatório e preencha a matriz.

Answer 4

Os algoritmos de Nate (editados) e Brian são o Shuffle O (n) Fisher -Yates, enquanto se arrasta pela classificação é O (nLogn), mas pode realmente ser mais rápido na prática (http://en.wikipedia.org/wiki/fisher% E2%80%93YATES_SHUFFUS#comparação_with_other_shuffling_algorithms). Receber a música que se arrastar pode ter consequências insignificantes, mas se você estiver escrevendo um algoritmo de embaralhamento para um jogo de pôquer on -line, certifique -se de saber o que está fazendo (http://www.cigital.com/news/index.php?pg= Art & Artid = 20).

Answer 5

Eu sou iniciante, deixe -me dizer uma solução que se lembra, se alguma coisa estiver errada, por favor me faça saber.

Vamos supor que as músicas sejam armazenadas na lista individual ou duplamente vinculada. Toda vez que o tocador de música é aberto, escolha um número aleatório menor que (qualquer número que você desejar) assuma k e reverte todos os nós da lista da lista, faça -o da mesma forma duas vezes ou no máximo três (como você desejar) que levaria O ( 2n) ou o (3n) tempo para embaralhar. Finalmente, tenha um ponteiro para o último nó da lista. E toda vez que uma música é ouvida (um nó é visitado) Remova o nó e insira -o ao lado do último nó que pode ser feito no tempo O (1). Isso continua até que o tocador de música esteja fechado.

Obrigado, ansioso para saber a correção da resposta.

Answer 6

O que você quer é o Fisher-Yates Shuffle. Aqui está uma implementação em Java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

Como funciona, trata toda a matriz como um chapéu e começa a puxar elementos aleatórios e alinhá -los na frente da matriz. Todos os elementos depois i estão 'no balde', todos os elementos antes i são embaralhados.