Ch12.8: Shuffling with std::shuffle

Overview

::std::shuffle from <algorithm> randomly reorders elements in a range. It requires a UniformRandomBitGenerator, which ibuf_white_hole_engine satisfies, giving you cryptographically secure shuffling.

Shuffling is essential for:

Card games and board games
Lotteries and random drawings
Randomized algorithms
Monte Carlo simulations
Any application requiring unpredictable ordering

Basic Usage


#include <fast_io.h>
#include <fast_io_device.h>
#include <vector>
#include <algorithm>

int main() {
    using namespace ::fast_io::io;

    // Create a secure random engine
    ::fast_io::ibuf_white_hole_engine eng;

    // Create a deck of cards (1-52)
    ::fast_io::vector<int> deck;
    for (int i{1}; i != 53; ++i) {
        deck.push_back(i);
    }

    println("Before shuffle:");
    for (::std::size_t i{}; i != 10; ++i) {
        print(deck[i], " ");
    }
    println("...");

    // Shuffle the deck
    ::std::shuffle(deck.begin(), deck.end(), eng);

    println("\nAfter shuffle:");
    for (::std::size_t i{}; i != 10; ++i) {
        print(deck[i], " ");
    }
    println("...");
}

Shuffling Different Container Types

::std::shuffle works with any container that provides random-access iterators:

Shuffling Strings


#include <fast_io.h>
#include <fast_io_device.h>
#include <algorithm>

int main() {
    using namespace ::fast_io::io;

    ::fast_io::ibuf_white_hole_engine eng;

    ::fast_io::string text = u8"The quick brown fox";
    println("Original: ", text);

    ::std::shuffle(text.begin(), text.end(), eng);
    println("Shuffled: ", text);
}

Shuffling Custom Objects


#include <fast_io.h>
#include <fast_io_device.h>
#include <vector>
#include <algorithm>

struct Card {
    int suit;  // 0-3
    int rank;  // 1-13
};

int main() {
    using namespace ::fast_io::io;

    ::fast_io::ibuf_white_hole_engine eng;

    // Create a deck of Card objects
    ::fast_io::vector<Card> deck;
    for (int suit{}; suit != 4; ++suit) {
        for (int rank{1}; rank != 14; ++rank) {
            deck.push_back({suit, rank});
        }
    }

    // Shuffle the deck
    ::std::shuffle(deck.begin(), deck.end(), eng);

    // Print first 5 cards
    println("First 5 cards:");
    for (::std::size_t i{}; i != 5; ++i) {
        println("  Suit: ", deck[i].suit, ", Rank: ", deck[i].rank);
    }
}

Shuffling Arrays


#include <fast_io.h>
#include <fast_io_device.h>
#include <array>
#include <algorithm>

int main() {
    using namespace ::fast_io::io;

    ::fast_io::ibuf_white_hole_engine eng;

    ::std::array<int, 10> numbers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    println("Before: ");
    for (auto n : numbers) {
        print(n, " ");
    }
    print("\n");

    ::std::shuffle(numbers.begin(), numbers.end(), eng);

    println("After:  ");
    for (auto n : numbers) {
        print(n, " ");
    }
    print("\n");
}

Partial Shuffling

Sometimes you only need to shuffle part of a container, or you need to draw random samples without full shuffling. You can use iterator ranges:


#include <fast_io.h>
#include <fast_io_device.h>
#include <vector>
#include <algorithm>

int main() {
    using namespace ::fast_io::io;

    ::fast_io::ibuf_white_hole_engine eng;

    // Create a vector of 100 elements
    ::fast_io::vector<int> data;
    for (int i{}; i != 100; ++i) {
        data.push_back(i);
    }

    // Shuffle only the first 10 elements
    ::std::shuffle(data.begin(), data.begin() + 10, eng);

    println("First 10 elements (shuffled):");
    for (::std::size_t i{}; i != 10; ++i) {
        print(data[i], " ");
    }
    print("\n");

    println("Elements 10-19 (unchanged):");
    for (::std::size_t i{10}; i != 20; ++i) {
        print(data[i], " ");
    }
    print("\n");
}

Shuffling vs Sampling

If you need to draw a random sample without modifying the original container, consider using ::std::sample (C++17) instead of shuffling:


#include <fast_io.h>
#include <fast_io_device.h>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    using namespace ::fast_io::io;

    ::fast_io::ibuf_white_hole_engine eng;

    // Original data
    ::fast_io::vector<int> population;
    for (int i{}; i != 100; ++i) {
        population.push_back(i);
    }

    // Draw 10 random samples without modifying population
    ::fast_io::vector<int> sample;
    ::std::sample(population.begin(), population.end(),
                  ::std::back_inserter(sample), 10, eng);

    println("Population (unchanged): ");
    for (::std::size_t i{}; i != 10; ++i) {
        print(population[i], " ");
    }
    println("...");

    println("\nRandom sample of 10:");
    for (auto val : sample) {
        print(val, " ");
    }
    print("\n");
}

::std::sample is more efficient than shuffling when you only need a few random elements from a large container.

Security Considerations

Using ibuf_white_hole_engine with ::std::shuffle provides cryptographically secure shuffling. However, be aware of these considerations:

Performance: Secure shuffling is slower than using a fast PRNG like ::std::mt19937_64. For non-security applications (games, simulations), consider using a seeded fast PRNG instead.
Predictability: If an attacker can observe enough shuffles, they might infer patterns. For high-security applications, create a new engine instance for each shuffle operation.
Reproducibility: If you need reproducible shuffles (for testing), use ::std::mt19937_64 seeded with ::std::seed_seq from a secure source (see Ch12.4).

Key Takeaways

::std::shuffle requires a UniformRandomBitGenerator, which ibuf_white_hole_engine satisfies.
Use ::std::shuffle with ibuf_white_hole_engine for cryptographically secure shuffling in games, lotteries, and security-sensitive applications.
Works with any container providing random-access iterators: ::fast_io::vector, ::std::array, ::fast_io::string, etc.
Use iterator ranges for partial shuffling.
For random sampling without full shuffling, use ::std::sample (C++17).
For non-security applications, consider using a fast PRNG like ::std::mt19937_64 for better performance.