Strange shuffle() behavior

[Browni3141]

Perhaps I just don't understand what shuffle() is supposed to do. I read the reference on this site thinking it would have the same behavior as random_shuffle(), but with a more complex random number generator than rand().

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

#include "card.h"

using namespace std;

int main()
{

    const int SEED = 12;

    vector <Card> deck;
    for (int i = int(Suit::CLUB); i <= int(Suit::SPADE); i++)
        for (int j = int(Rank::TWO); j <= int(Rank::ACE); j++)
        {
            deck.push_back(Card(static_cast<Rank>(j), static_cast<Suit>(i)));
        }
    //int total = 0, best = 0;
    //auto copy(deck);
    for (int i = 1; true; i++)
    {
        shuffle(deck.begin()+7, deck.end(), mt19937_64(SEED));
        auto mySort = [](Card& l, Card& r) { return toInt(l) > toInt(r); };

        //sort(deck.begin(), deck.begin()+2, mySort);
        //sort(deck.begin()+2, deck.begin()+5, mySort);
        //sort(deck.begin()+7, deck.begin()+9, mySort);
        deck[7].print(cout);
        deck[8].print(cout);
        cout << '\n';
        if (i%8 == 0)
            cin.get();
    }
    return 0;
}

I get very strange output. With a period length of eight, the cards in the second column appear in the first column.:

TdAc
5s3d
Kd7d
ThQh
8s4h
6dKh
2d4s
TcAd

Ac2s
3d9h
7d3s
Qh9s
4hQd
KhQs
4sKc
Ad6s

2sKs
9h9d
3s3h
9s5h
QdAh
QsJc
KcJd
6sJh

This is part of a larger program, but I have commented out all other code. I don't think it's necessary to include the contents of "card.h" or "card.cpp."

My compiler is Cygwin 64. Oddly, when I compile with GCC I don't observe the same behavior. The code seems to work with CodeBlocks default GCC.

[tpb]

You're forgetting the nature of seeding the generator. Just like srand, it should only be done once in the run of the program.

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> deck(52);
    std::iota(deck.begin(), deck.end(), 0);
    std::mt19937_64 rng(std::random_device{}());
    std::shuffle(deck.begin(), deck.end(), rng);
    for (int n: deck)
        std::cout << "A23456789TJQK"[n%13] << "CDHS"[n/13] << ' ';
    std::cout << '\n';
}

[Peter87]

I get very strange output. With a period length of eight, the cards in the second column appear in the first column.

Why wouldn't they? You shuffle all cards except for the first seven and then you print the eighth and ninth card. There is nothing that prevents the eighth card from ending up as the ninth card at a later time after you have shuffled the deck again.

[JLBorges]

#include <iostream>
#include <array>
#include <random>
#include <algorithm>

struct card
{
    enum class suit { SPADE, HEART, DIAMOND, CLUB };
    static constexpr int NSUITS = 4 ;

    enum class rank { TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE };
    static constexpr int NRANKS = 13 ;

    suit s ;
    rank r ;

    using deck = std::array< card, NSUITS*NRANKS > ;
};

std::ostream& operator<< ( std::ostream& stm, card::suit suit )
{
    const char symbols[] = "shdc" ;
    return stm << symbols[ int(suit) ] ;
}

std::ostream& operator<< ( std::ostream& stm, card::rank rank )
{
    const char symbols[] = "23456789TJQKA" ;
    return stm << symbols[ int(rank) ] ;
}

std::ostream& operator<< ( std::ostream& stm, card c )
{
    return stm << c.r << c.s ;
}

std::ostream& operator<< ( std::ostream& stm, const card::deck& deck )
{
   for( std::size_t i = 0 ; i < deck.size() ; ++i )
   {
       stm << deck[i] << ' ' ;
       if( i%card::NRANKS == (card::NRANKS-1) ) stm << '\n' ;
   }

   return stm ;
}

card::deck make_deck()
{
    card::deck d ;

    for( int s = 0 ; s < card::NSUITS ; ++s )
        for( int r = 0 ; r < card::NRANKS ; ++r )
            d[ s*card::NRANKS + r ] = { card::suit(s), card::rank(r) } ;

    return d ;
}

card::deck& shuffle( card::deck& d )
{
    static std::mt19937 rng( std::random_device{}() ) ;

    std::shuffle( d.begin(), d.end(), rng ) ;
    return d ;
}

int main()
{
    auto deck = make_deck() ;
    std::cout << deck << '\n' ;

    for( int i = 0 ; i < 3  ; ++i )
    {
        shuffle(deck) ;
        std::cout << "-----------\n\n" << deck << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/e2b37929195be3bf

[tpb]

#include <iostream>
#include <random>
#include <algorithm>
#include <array>

class Deck {
public:
    constexpr static int NSuits = 4, NValues = 13;

    class Card {
        int n;
    public:
        Card(int n=0) : n(n) {}    

        char suit()  const { return "CDHS"         [n / NValues]; }

        char value() const { return "23456789TJQKA"[n % NValues]; }

        friend std::ostream& operator<<(std::ostream& os, const Card& c) {
            return os << c.value() << c.suit();
        }
    };

    Deck() { std::iota(cards.begin(), cards.end(), 0); }

    void shuffle() {
        static std::mt19937 rng(std::random_device{}());
        std::shuffle(cards.begin(), cards.end(), rng);
    }

    friend std::ostream& operator<<(std::ostream& os, const Deck& d) {
        size_t i = 0;
        for (const auto& c: d.cards)
            std::cout << c << (++i % Deck::NValues ? ' ' : '\n');
        return os;
    }

private:
    std::array<Card, NSuits * NValues> cards;
};

int main() {
    Deck d;
    std::cout << d << '\n';
    d.shuffle();
    std::cout << d;
}

(EDIT: It doesn't run properly on cpp.sh. Neither does JLBorges'. It should show the unshuffled deck, which it does, and then the shuffled one, which it doesn't.)

[Browni3141]

Peter87 wrote:

Why wouldn't they? You shuffle all cards except for the first seven and then you print the eighth and ninth card. There is nothing that prevents the eighth card from ending up as the ninth card at a later time after you have shuffled the deck again.

I think you misunderstood. The behavior is observed with a period of
eight shuffles. A card doesn't sometimes re-appear, it always re-appears in a predictable way.

Look at my output again. If we denote each row in the output as an element in a sequence. A_i,0 = A_i-8,1

tpb wrote:

You're forgetting the nature of seeding the generator. Just like srand, it should only be done once in the run of the program.

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

int main()
{
std::vector<int> deck(52);
std::iota(deck.begin(), deck.end(), 0);
std::mt19937_64 rng(std::random_device{}());
std::shuffle(deck.begin(), deck.end(), rng);
for (int n: deck)
std::cout << "A23456789TJQK"[n%13] << "CDHS"[n/13] << ' ';
std::cout << '\n';
}

Oh, I am kind of embarrassed it was that simple. I somehow didn't realize that I was creating a new instance of the rng every time shuffle() was called.

It's very strange to me that the behavior was different for GCC vs. Cygwin, though.

JLBorges, does your code create a new rng seeded with a true random number every time shuffle() is called? Pseudo-randomness is more useful within the context of my project. I have simply declared mt19937_64 rng(SEED) outside of my loop and it works great.

Thanks to all who replied. Sorry the problem wasn't more interesting.

[JLBorges]

> JLBorges, does your code create a new rng seeded with a true random number every time shuffle() is called?

No. The rng is created only once, on the first call to shuffle(). The object has static storage duration.