Как проверить, достаточно ли перемешана колода карт в Java

Question

Я должен проверить и проверить, не перетасовал ли этот метод колоду карт.Вот если код для фактической части перетасовки.

 public void randomShuffle () {
               for (int i = 0; i < DECK_SIZE; i++) {
                   int place = (int)((Math.random()*(51-i))+i);
                   Card temp = this.cardAt(i);
                   this.cardList[i] = this.cardAt(place);
                   this.cardList[place] = temp;
           }
       }

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

static void randomShuffleTest () {
       Deck deck1 = Deck.newDeckOf52();
       Deck deck2 = Deck.newDeckOf52();
       deck2.randomShuffle();           

       assert false == deck1.equals(deck2);
    }

Итак, мой вопрос: как мне проверить, достаточно ли было что-то перемешано?

Answer 1

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

Я думаю, вам лучше спросить об этом на math.stackexchange.com ... где болтаются умные парни. Если они могут объяснить «математику» простыми словами (для глупых ИТ-специалистов, таких как вы и я), вы сможете писать тесты на Java.

---

Когда я говорю: «Вы не можете сделать это» ... очевидно, вы можете проверить, не была ли колода вообще перетасована, или она не повредила колоду. Но ни один из них не является заслуживающим доверия тестом для ваших критериев ... "достаточно перемешанный".

Answer 2

Точный тест невозможен .Просто верь своему алгоритму.или используйте Collections.shuffle()

Answer 3

Вы не можете.Невозможно определить, была ли перетасована колода, потому что теоретически в результате перетасовки колода может быть точно в порядке.

Answer 4

Точно так же, как сказал Марк Байерс, алгоритм тасования может создать колоду, которая находится в точном порядке. Но если это происходит в каждом последующем запуске, то это определенно плохой алгоритм! Таким образом, правильный алгоритм перетасовки должен создавать последовательности карт таким образом, чтобы распределение карт в i-й позиции было равномерным. Пусть S(i)={c(1)(i),c(2)(i),...,c(54)(i)} будет i-й последовательностью (i-й результат вашего алгоритма). Тогда c (j) (i) относительно (i) должно следовать (приблизительно) равномерному распределению. Чтобы проверить, верно ли это, запустите ваш алгоритм несколько тысяч раз, и в каждой позиции j = 1,2, ..., 54 посчитайте частоту, с которой появляется каждая отдельная карта. Числа должны быть более или менее равными. В идеале, если вы запустите алгоритм 54000 раз, вы должны увидеть каждую карту в каждой позиции 1000 раз. Я сильно сомневаюсь, будет ли это так, используя Math.random(). Используйте java.util.Random для лучших результатов. Вот как вы работаете с Random:

final java.util.Random random = new java.util.Random(seed);

и каждый раз, когда вам нужен случайный дубль:

random.nextDouble();

Метод Collections.shuffle(); делает именно это. Если вам нужны RNG лучше, чем Java-реализация Random, вы, скорее всего, должны приступить к собственной реализации.

Answer 5

Одной из мер может быть сортировка перетасованной колоды и проверка того, сколько «операций» потребовалось.Очевидно, что эта мера будет зависеть от алгоритма сортировки.

С другой стороны, вы можете найти где-нибудь здесь статистическую меру: http://en.wikipedia.org/wiki/Randomness_tests.

Answer 6

Прежде всего мне нравится этот вопрос (интересный).

• Прежде всего, я хотел бы знать, каково ваше определение "достаточно перемешано?" Вы можете даже измерить это? У вас есть руководящие принципы для этого? Должны ли, например, как минимум пять карт, но в другом месте? Вы можете легко написать тест, чтобы проверить, сколько карт или в другом месте, но достаточно ли этого?
• Я также думаю, что Марк прав в создании перетасованной колоды, которая имитирует оригинальную колоду (хотя я сомневаюсь, что вероятность очень мала). Поэтому тестирование будет очень трудным, иначе вы можете отказаться от перетасованной колоды, если она имитирует оригинал. Таким образом, вашего теста будет достаточно
• Кроме того, я считаю, что вы, вероятно, должны использовать упоминание Джигаром о Collections.shuffle() вместо того, чтобы что-то писать самостоятельно?

Answer 7

Лучший способ проверить это - это протестировать 1000 раз или около того и записывать каждый раз, когда тест проходит успешно.В конечном итоге вы действительно хотите знать, что тест работает 98-99% времени, поэтому, если результат составляет ~ 99% +/- 1%, вы должны быть хорошими, и тест всегда должен проходить.

• перетасованная рука не должна совпадать с оригинальной.
• длина обеих должна быть одинаковой.
• сумма всех карточек должна быть одинаковой (или похожей)

пример кода в swift:

func testShuffled() {
    var hand1 = [3,4,5,6,7,1,2,8,9,10,11,12,2,3,4,5,6,7,8,9,10,11,12]
    var count =  0

    for _ in 0..<1000 {
        let hand2 = hand1.shuffled()

        if (hand1 != hand2 && hand1.count == hand2.count &&
            hand1.reduce(0, combine: +) == hand2.reduce(0, combine: +)) {
            count += 1
        }
        hand1 = hand2
    }
    let result = Double(count) / 1000.00
    XCTAssertEqualWithAccuracy(result, 1, accuracy: 0.02)
}