Как перетасовать карты для карточной игры?

Я пытаюсь разработать карточную игру для Android. Может кто-нибудь посоветовать мне, как написать код для эффективного перетасовки игральных карт?

Перестановка карт - это алгоритм, который легко написать интуитивно, и при этом он совершенно ошибается. В Википедии есть хорошая ссылка для правильной реализации перетасовки карт . То, что я представляю здесь, это очень упрощенная версия алгоритма, описанная на этой странице в разделе Современный алгоритм .

Вот основная идея на простом английском:

Рассмотрим колоду карт. Для этого обсуждения вы можете иметь любое количество карт в колоде, и они могут начинаться в любом порядке.

Мы будем говорить о «позиции» в колоде, где «позиция» - это количество карт в колоде выше, чем карта в этой позиции. Например, карта в верхней части колоды находится в позиции 0, карта в нижней части - в позиции 1 (потому что на 1 карту выше ее - верхняя карта), а в стандартной колоде из 52 карт - нижняя Карта находится на позиции 51, так как 51 карта выше, чем в колоде.

Теперь мы рассмотрим каждую позицию в колоде, одну за другой, начиная снизу и продвигаясь вверх.

Для каждой позиции мы случайным образом выбираем одну из карт, которая находится в этой позиции или в позиции с меньшим номером (помните, что верх колоды равен 0, и мы работаем вверх от нижней части колоды, поэтому для каждой позиции вы эффективно подбираете все карты в и выше этой позиции и случайным образом выбираете одну из этих карт).

Когда мы сделали случайный выбор, мы меняем карту в позиции, которую мы сейчас рассматриваем, на карту, которую мы выбрали случайным образом. Если мы случайно выбрали карту, которая уже находилась в этой позиции, то обмен не выполняется.

После обмена (или без обмена, если мы случайно выбрали карту, которая уже находилась в позиции, которую мы рассматривали), мы переходим к следующей позиции в колоде и продолжаем.

В псевдокоде с п является количество карт в колоде, и быть массивом , представляющий колоду, алгоритм выглядит следующим образом :

for each i in [n .. 1] do
     j ← random integer in [ 0 .. i ]
     exchange a[j] and a[i]

Сначала вы определяете последовательность всех карт, которые хотите перемешать:

List<Card> shuffled = new ArrayList<Card>();
shuffled.addAll(allCards);

Затем вы проходите каждую позицию в последовательности и случайным образом назначаете ей карту.

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

Теперь shuffledэто случайная последовательность всех ваших карт.

Я хотел бы присоединиться и упомянуть «шифрование с сохранением формата» в качестве метода перетасовки карт в игре.

По сути, у вас есть алгоритм шифрования, который принимает значение от 0 до 51, и ключ (начальное перемешивание) и выплевывает значение от 0 до 51. Поскольку шифрование является обратимым по определению, это означает, что любые 2 входных числа не могут быть зашифрованы в тот же номер выхода, что означает, что если вы зашифровали от 0 до 51, вы получите от 0 до 51 в качестве вывода в другом порядке. Другими словами, у вас есть тасование, и вам даже не нужно делать какие-либо реальные тасования.

В этом случае вам нужно было бы создать или найти алгоритм шифрования, который бы занимал 6 бит и выплевывал 6 бит (0-63). Чтобы вытянуть следующую карту из колоды, у вас будет индексная переменная, которая начинается с нуля, вы должны зашифровать этот индекс, увеличить индекс и посмотреть значение, полученное из шифра. Если значение> = 52, вы игнорируете его и генерируете новое число (и, конечно, снова увеличиваете индекс). Поскольку шифрование 0-63 приведет к выводу 0-63 в другом порядке, вы просто игнорируете любое значение, которое выходит> = 52, так что ваш алгоритм принимает 0-51 и выплевывает 0-51.

Чтобы переставить колоду, установите индекс обратно на ноль и измените ключ шифрования (случайное начальное число).

Ваш алгоритм не должен быть криптографическим (и не должен быть, потому что это будет дорого в вычислительном отношении!). Один действительно хороший способ придумать алгоритм шифрования нестандартного размера, подобный этому, - это использовать сеть Feistel, которая позволяет настраивать размер и качество в зависимости от ваших потребностей. Для функции округления в сети Feistel я бы порекомендовал что-то вроде murmurhash3, потому что он быстрый и обладает хорошим лавинным эффектом, благодаря которому перетасовки выглядят хорошо рандомизированными.

Прочтите мой пост в блоге для получения более подробной информации и исходного кода: http://blog.demofox.org/2013/07/06/fast-lightweight-random-shuffle-functionality-fixed/

В учебнике по java 1.5 enum есть интересный способ реализации колоды карт, наращивания колоды, тасования и раздачи. Все очень просто, используя enums иCollections

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

И класс для управления колодой.

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

Просто используйте функцию наподобие itertools, как в Python. Мне не известно имя той же функции в Java, попробуйте ". Http://code.google.com/p/neoitertools/ "

Узнайте все перестановки объекта под названием «карты»

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