java: перетасовка карт,

Question

Это интервью-вопросы. Пожалуйста, дайте несколько советов:

Используйте vector для реализации метода, перемешайте колоду карт.

public class Card {
    private int value;
    Card(int v) {
        value = v;
        }

    public void print(){
        System.out.print(value+";");
    }
}



public class DeckShuffle {

    private final int num;
    Vector<Card> deck = new Vector<Card>();

// implement this shuffle function. DO NOT USE Collections.shuffle() !!
public void shuffle(){
// your code goes here!
}



}

Answer 1

Код для Collections.shuffle() можно найти в исходном пакете для JDK или из OpenJDK, но алгоритм довольно прост (в основном такой же для коллекции, как и для массива):

given a[]
for i <- 0..a.length-2
  rnd_index <- random(i, a.length) #inclusive, exclusive
  swap a[i] and a[rnd_index]
next

Это работает на месте, поэтому вам не нужна дополнительная параллельная память.Это известно как случай Фишера Йетса .

Answer 2

void Shuffle()
{
  int n= deck.size();
  Vector<Card> v = new Vector<Card>(n);


  for (int i = 0; i < n; i++) {
     int j = (int)((i-1) * Math.random() )+ 1;
     if ( i != j ) {
         swap(cards, i, j);
     }
  }

  deck = v;
}

Answer 3

Вот что приходит на ум:

public void shuffle() {
    Vector<Card> v = new Vector<Card>(deck.size());
    int size = deck.size();
    for(int i = 0; i < size; i++) {
        int index = Math.random() * deck.size();
        Card c = deck.remove(index);
        v.add(c);
    }
    deck = v;
}

Это сухой код, тестирование не проводится.