use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn slice_random_trait() {
    // SliceRandom provides shuffle and partial_shuffle
    let mut numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    
    // shuffle randomizes the entire slice
    numbers.shuffle(&mut thread_rng());
    println!("Shuffled: {:?}", numbers);
    
    // partial_shuffle randomizes only first n elements
    let mut numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let head = numbers.partial_shuffle(&mut thread_rng(), 3);
    println!("Partial: head={:?}, tail={:?}", head, numbers);
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn shuffle_example() {
    let mut items = vec!['a', 'b', 'c', 'd', 'e'];
    
    // shuffle randomizes all elements
    items.shuffle(&mut thread_rng());
    
    // Every element has equal probability of being in any position
    // The entire slice is now in random order
    
    println!("Shuffled: {:?}", items);
    // Example output: ['d', 'a', 'e', 'b', 'c']
}
 
// shuffle works by iterating through each position
// and swapping with a random position (including itself)
fn shuffle_algorithm() {
    // Fisher-Yates algorithm (what shuffle does internally):
    let mut slice = vec![1, 2, 3, 4, 5];
    let mut rng = thread_rng();
    
    // For each position i from 0 to len-1:
    for i in 0..slice.len() {
        // Pick random index j where i <= j < len
        let j = rng.gen_range(i..slice.len());
        // Swap elements at i and j
        slice.swap(i, j);
    }
    
    // Result: uniformly random permutation
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn partial_shuffle_example() {
    let mut items = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    
    // partial_shuffle(n) ensures:
    // - First n elements are randomly selected from the slice
    // - Remaining elements are in an unspecified order
    
    let head = items.partial_shuffle(&mut thread_rng(), 3);
    
    // head contains a reference to the shuffled head portion
    // items is modified in place
    
    println!("Head (first 3): {:?}", head);
    println!("Full slice: {:?}", items);
    
    // The head contains 3 randomly chosen elements
    // The remaining 7 elements are in some order (not shuffled)
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn algorithm_comparison() {
    // shuffle: Complete Fisher-Yates
    // For each position i from 0 to len-1:
    //   Pick random index j from i to len-1
    //   Swap elements at i and j
    // Result: Uniform random permutation
    
    // partial_shuffle: Partial Fisher-Yates
    // For each position i from 0 to n-1:
    //   Pick random index j from i to len-1
    //   Swap elements at i and j
    // Result: First n elements are random sample
    //         Remaining elements in arbitrary order
    
    // Time complexity:
    // shuffle: O(n) where n = slice length
    // partial_shuffle: O(k) where k = amount to shuffle
    
    // For n << slice.len(), partial_shuffle is much faster
}
 
// Example showing the difference
fn visualize_algorithm() {
    let mut full = vec![1, 2, 3, 4, 5];
    full.shuffle(&mut thread_rng());
    // All 5 positions are randomized
    // Cost: 5 iterations
    
    let mut partial = vec![1, 2, 3, 4, 5];
    partial.partial_shuffle(&mut thread_rng(), 2);
    // Only 2 positions are randomized
    // Cost: 2 iterations
    // Remaining 3 elements may have been swapped during process
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn return_values() {
    // shuffle returns ()
    let mut slice = vec![1, 2, 3, 4, 5];
    slice.shuffle(&mut thread_rng());
    // Just modifies in place, no return value
    
    // partial_shuffle returns a pair of mutable slices
    let mut slice = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let (head, tail) = slice.partial_shuffle(&mut thread_rng(), 3);
    
    // head: &mut [T] - the shuffled portion (first n elements)
    // tail: &mut [T] - the remainder (len - n elements)
    
    println!("Head: {:?}", head);  // 3 randomly chosen elements
    println!("Tail: {:?}", tail);  // Remaining 7 elements
    
    // Both are views into the original slice
    // You can access both independently
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn random_sampling() {
    let population = vec!["Alice", "Bob", "Charlie", "David", "Eve", 
                          "Frank", "Grace", "Henry", "Ivy", "Jack"];
    
    // Need 3 random people from 10
    
    // Wrong approach: shuffle all, take first 3
    let mut all_shuffled = population.clone();
    all_shuffled.shuffle(&mut thread_rng());
    let sample1: Vec<_> = all_shuffled.iter().take(3).collect();
    // Cost: O(10) operations
    
    // Better approach: partial_shuffle
    let mut partial = population.clone();
    let (sample, _) = partial.partial_shuffle(&mut thread_rng(), 3);
    let sample2: Vec<_> = sample.to_vec();
    // Cost: O(3) operations
    
    // For large collections, this difference is significant
    // Shuffling 1 million items to get 5 random ones: O(1,000,000)
    // Partial shuffling: O(5)
}
 
fn sampling_efficiency() {
    let large_dataset: Vec<i32> = (0..1_000_000).collect();
    
    // We need 10 random samples
    
    // Full shuffle: 1 million operations
    let mut full_shuffle = large_dataset.clone();
    full_shuffle.shuffle(&mut thread_rng());
    let sample: Vec<_> = full_shuffle.iter().take(10).collect();
    
    // Partial shuffle: 10 operations
    let mut partial = large_dataset.clone();
    let (head, _) = partial.partial_shuffle(&mut thread_rng(), 10);
    let sample: Vec<_> = head.to_vec();
    
    // Partial shuffle is 100,000x faster for this case
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn without_replacement() {
    let mut deck = vec!["A", "B", "C", "D", "E", "F", "G", "H"];
    
    // Draw 3 cards without replacement
    let (drawn, remaining) = deck.partial_shuffle(&mut thread_rng(), 3);
    
    println!("Drawn: {:?}", drawn);      // 3 random cards
    println!("Remaining: {:?}", remaining);  // 5 cards left
    
    // This is exactly what partial_shuffle is designed for:
    // - Select k items from n items
    // - Each item selected exactly once
    // - Random selection without replacement
}
 
fn lottery_system() {
    let mut participants: Vec<u32> = vec![101, 102, 103, 104, 105, 106, 107, 108];
    
    // Draw 3 winners
    let (winners, others) = participants.partial_shuffle(&mut thread_rng(), 3);
    
    println!("Winners: {:?}", winners);
    println!("Runners-up: {:?}", others);
    
    // winners is guaranteed to have 3 unique participants
    // No duplicates possible (unlike random sampling with replacement)
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn tail_behavior() {
    let mut items = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    
    // Before: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    
    let (head, tail) = items.partial_shuffle(&mut thread_rng(), 3);
    
    // head: 3 randomly selected elements (from the original 10)
    // tail: 7 remaining elements
    
    // Important: The tail is NOT shuffled
    // It contains the elements that weren't selected for head
    // In some arbitrary order (depends on swap operations)
    
    // If you need the tail shuffled too, call shuffle on it:
    tail.shuffle(&mut thread_rng());
    
    // Now both portions are randomized
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn memory_efficiency() {
    // Both shuffle and partial_shuffle are in-place
    // No additional memory allocation
    
    // shuffle: O(1) extra space
    let mut large = vec![0u64; 1_000_000];
    large.shuffle(&mut thread_rng());
    // Uses only a few bytes for indices and RNG state
    
    // partial_shuffle: O(1) extra space
    let mut large = vec![0u64; 1_000_000];
    large.partial_shuffle(&mut thread_rng(), 10);
    // Same memory usage
    
    // Compare to other approaches:
    
    // Choosing 10 random indices without shuffle:
    use rand::seq::index;
    let indices: Vec<usize> = index::sample(&mut thread_rng(), 1_000_000, 10)
        .into_vec();
    // Allocates Vec<usize> for indices
    
    // Using partial_shuffle is more memory efficient
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn edge_cases() {
    let mut items = vec![1, 2, 3, 4, 5];
    
    // If k > len, partial_shuffle acts like shuffle
    let (head, tail) = items.partial_shuffle(&mut thread_rng(), 100);
    
    // head.len() == 5 (the entire slice)
    // tail.len() == 0 (empty)
    
    // This is graceful degradation
    
    // If k == 0, nothing changes
    let mut items = vec![1, 2, 3, 4, 5];
    items.partial_shuffle(&mut thread_rng(), 0);
    // Slice is unchanged
    
    // If k == len, equivalent to full shuffle
    let mut items = vec![1, 2, 3, 4, 5];
    items.partial_shuffle(&mut thread_rng(), 5);
    // Same as items.shuffle(&mut thread_rng())
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn card_game_example() {
    let mut deck: Vec<&str> = &[
        "A♠", "2♠", "3♠", "4♠", "5♠", "6♠", "7♠", "8♠", "9♠", "10♠", "J♠", "Q♠", "K♠",
        "A♥", "2♥", "3♥", "4♥", "5♥", "6♥", "7♥", "8♥", "9♥", "10♥", "J♥", "Q♥", "K♥",
        "A♦", "2♦", "3♦", "4♦", "5♦", "6♦", "7♦", "8♦", "9♦", "10♦", "J♦", "Q♦", "K♦",
        "A♣", "2♣", "3♣", "4♣", "5♣", "6♣", "7♣", "8♣", "9♣", "10♣", "J♣", "Q♣", "K♣",
    ].to_vec();
    
    // Deal 5 cards to each of 4 players
    
    // Option 1: Full shuffle (O(52))
    // deck.shuffle(&mut thread_rng());
    // Then deal sequentially
    
    // Option 2: Deal from partial shuffles (more efficient for multiple deals)
    // Only shuffle as needed
    
    // Deal to player 1: partial shuffle first 5
    let (hand1, remaining) = deck.partial_shuffle(&mut thread_rng(), 5);
    println!("Player 1: {:?}", hand1);
    
    // Now remaining contains 47 cards
    // Deal to player 2
    let (hand2, remaining) = remaining.partial_shuffle(&mut thread_rng(), 5);
    println!("Player 2: {:?}", hand2);
    
    // And so on...
}

use rand::seq::SliceRandom;
use rand::thread_rng;
 
fn comparison_table() {
    // shuffle:
    // - Randomizes entire slice
    // - Time: O(n) where n = slice length
    // - Space: O(1) in-place
    // - Returns: ()
    // - Use when: You need all elements in random order
    
    // partial_shuffle:
    // - Randomizes first k elements
    // - Time: O(k) where k = amount to shuffle
    // - Space: O(1) in-place
    // - Returns: (head, tail) mutable slices
    // - Use when: You need random sample of k elements
    
    // When to use which:
    
    // 1. Need full random order? Use shuffle
    let mut playlist = vec!["song1", "song2", "song3", "song4", "song5"];
    playlist.shuffle(&mut thread_rng());
    // Play all songs in random order
    
    // 2. Need random sample of k? Use partial_shuffle
    let mut large_list: Vec<i32> = (0..10000).collect();
    let (sample, _) = large_list.partial_shuffle(&mut thread_rng(), 10);
    // Get 10 random items efficiently
    
    // 3. Need random order AND want to process in batches? Use shuffle
    let mut items: Vec<i32> = (0..100).collect();
    items.shuffle(&mut thread_rng());
    // Process in random order
    
    // 4. Selecting without replacement? Use partial_shuffle
    let mut candidates = vec!["A", "B", "C", "D", "E"];
    let (winners, _) = candidates.partial_shuffle(&mut thread_rng(), 2);
    // 2 unique random selections
}

// Both use Fisher-Yates (Knuth shuffle):
// 
// shuffle:
// for i in 0..len {
//     j = random(i..len)
//     swap(i, j)
// }
//
// partial_shuffle(n):
// for i in 0..n {
//     j = random(i..len)
//     swap(i, j)
// }
// Stop after n iterations

// Large collection, small sample:
// slice.len() = 1,000,000
// need k = 10 random elements
 
// shuffle: O(1,000,000) operations
// partial_shuffle: O(10) operations
 
// Speedup: 100,000x faster