Odpowiedzi:
Tasowanie kart to algorytm, który łatwo jest napisać intuicyjnie i całkowicie się myli. Istnieje dobre odniesienie do prawidłowego wdrażania tasowania kart na Wikipedii . To, co tu prezentuję, to bardzo nieznacznie uproszczona wersja algorytmu opisana na tej stronie w części Nowoczesny algorytm .
Oto podstawowy pomysł, w prostym języku angielskim:
Rozważ talię kart. W tej dyskusji możesz mieć dowolną liczbę kart w talii i mogą one zaczynać się w dowolnej kolejności.
Będziemy mówić o „pozycji” w talii, gdzie „pozycja” to liczba kart znajdujących się wyżej w talii niż karta w tej pozycji. Na przykład karta na górze talii znajduje się w pozycji 0, karta poniżej, która jest w pozycji 1 (ponieważ jest o 1 karta wyżej - górna karta), aw standardowej talii 52 kart dolna karta znajduje się na pozycji 51, ponieważ 51 kart jest wyżej niż w talii.
Teraz bierzemy pod uwagę każdą pozycję w talii, pojedynczo, zaczynając od dołu i idąc w górę na szczyt.
Dla każdej pozycji losowo wybieramy jedną z kart, które znajdują się w tej pozycji lub w pozycji o niższym numerze (pamiętaj, że górna część talii to 0, a my pracujemy w górę z dołu talii, więc dla każdej pozycji skutecznie zbierasz wszystkie karty na tej pozycji i powyżej i losowo wybierasz jedną z tych kart).
Po dokonaniu losowego wyboru zamieniamy kartę na pozycję, którą aktualnie rozważamy, na losowo wybraną kartę. Jeśli losowo wybraliśmy kartę, która była już w tej pozycji, nie jest przeprowadzana zamiana.
Po zamianie (lub braku zamiany, jeśli losowo wybraliśmy kartę, która była już w rozważanej pozycji), przechodzimy do następnej pozycji w talii i kontynuujemy.
W Pseudokod, a n oznacza liczbę kart w talii, a jest tablicą reprezentującą pokład, algorytm wygląda tak:
for each i in [n .. 1] do
j ← random integer in [ 0 .. i ]
exchange a[j] and a[i]
Najpierw musisz zdefiniować sekwencję wszystkich kart, które chcesz przetasować:
List<Card> shuffled = new ArrayList<Card>();
shuffled.addAll(allCards);
Następnie przechodzisz przez każdą pozycję w sekwencji i losowo przypisujesz jej kartę.
Random random = new Random();
for (int i = shuffled.size() - 1; i >= 0; i--) {
int j = random.nextInt(i + 1);
/* swap cards i,j */
Card card = shuffled.get(i);
shuffled.set(i, shuffled.get(j));
shufflet.set(j, card);
}
Teraz shuffled
jest losowa sekwencja wszystkich twoich kart.
Chciałbym włączyć się i wspomnieć o „szyfrowaniu z zachowaniem formatu” jako metodzie tasowania kart w grze.
Zasadniczo potrzebujesz algorytmu szyfrowania, który przyjmuje wartość od 0 do 51, oraz klucz (ziarno losowe) i wyrzuca wartość od 0 do 51. Ponieważ szyfrowanie jest z definicji odwracalne, co oznacza, że żadne 2 liczby wejściowe nie mogą być zaszyfrowane ten sam numer wyjściowy, co oznacza, że jeśli zaszyfrujesz od 0 do 51, otrzymasz od 0 do 51 jako wyjście w innej kolejności. Innymi słowy, masz tasowanie i nawet nie musisz wykonywać żadnego przetasowania.
W takim przypadku musisz stworzyć lub znaleźć algorytm szyfrowania, który wziął 6 bitów i wypluł 6 bitów (0–63). Aby wyciągnąć następną kartę z talii, będziesz mieć zmienną indeksu, która zaczyna się od zera, zaszyfrujesz ten indeks, zwiększysz indeks i spojrzysz na wartość, która wyszła z szyfru. Jeśli wartość wynosi> = 52, ignorujesz ją i generujesz nowy numer (i oczywiście ponownie zwiększasz indeks). Ponieważ szyfrowanie 0–63 spowoduje, że dane wyjściowe będą miały wartość 0–63, w innej kolejności po prostu ignorujesz każdą wychodzącą wartość> = 52, dzięki czemu masz algorytm, który przyjmuje 0–51 i wyrzuca 0–51.
Aby przetasować talię, ustaw indeks z powrotem na zero i zmień klucz szyfrowania (seeduj losowo).
Twój algorytm nie musi być jakością kryptograficzną (i nie powinno tak być, ponieważ byłoby to drogie obliczeniowo!). Jednym z naprawdę dobrych sposobów wymyślenia algorytmu szyfrowania o niestandardowych rozmiarach, takiego jak ten, byłoby skorzystanie z sieci feistel, która pozwala dostosować rozmiar i jakość w zależności od potrzeb. Dla okrągłej funkcji sieci feistel zaleciłbym coś takiego jak murmurhash3, ponieważ jest szybki i ma dobry efekt lawinowy, co sprawiłoby, że losowanie wydawałoby się losowe.
Sprawdź mój post na blogu, aby uzyskać jeszcze bardziej szczegółowe informacje i kod źródłowy: http://blog.demofox.org/2013/07/06/fast-lightweight-random-shuffle-functionality-fixed/
Java 1.5 enum poradnik ma ciekawy sposób wdrożenia talię kart, budując pomost, tasowanie i radzenia sobie. Wszystko bardzo proste przy użyciu enum
s iCollections
public class Card {
public enum Rank { DEUCE, THREE, FOUR, FIVE, SIX,
SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }
public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }
private final Rank rank;
private final Suit suit;
private Card(Rank rank, Suit suit) {
this.rank = rank;
this.suit = suit;
}
public Rank rank() { return rank; }
public Suit suit() { return suit; }
public String toString() { return rank + " of " + suit; }
private static final List<Card> protoDeck = new ArrayList<Card>();
// Initialize prototype deck
static {
for (Suit suit : Suit.values())
for (Rank rank : Rank.values())
protoDeck.add(new Card(rank, suit));
}
public static ArrayList<Card> newDeck() {
return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
}
}
I klasa zarządzająca talią.
public class Deal {
public static void main(String args[]) {
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);
List<Card> deck = Card.newDeck();
Collections.shuffle(deck);
for (int i=0; i < numHands; i++)
System.out.println(deal(deck, cardsPerHand));
}
public static ArrayList<Card> deal(List<Card> deck, int n) {
int deckSize = deck.size();
List<Card> handView = deck.subList(deckSize-n, deckSize);
ArrayList<Card> hand = new ArrayList<Card>(handView);
handView.clear();
return hand;
}
}
Po prostu użyj funkcji takiej jak itertools jak w Pythonie. Nie znam nazwy tej samej funkcji w Java try ”. Http://code.google.com/p/neoitertools/ ”
Znajdź wszystkie permutacje obiektu zwanego „kartami”
ArrayList deckCards = new ArrayList<Card>();
//add your cards to the deck
deckCards.add(card1);
deckCards.add(card2);
deckCards.add(card3);
....
//shuffle the array list
Collections.shuffle(deckCards);