Exam Seating Rearrangements using DP

Problem Introduction

A professor has two exams for the same class. For the first exam, students sat in a specific arrangement of desks. For the second exam, the professor wants to rearrange seating so that no student sits in the exact same desk they used the first time. 

This prevents cheating (students can't rely on "what I saw from this desk last time") and ensures fairness.

How many different seating charts satisfy this constraint? If there are N students and N identical desks, how many valid rearrangements exist?

Why It Matters

Exam seating rearrangement is a practical derangement application with real consequences:

• Academic integrity: Prevents students from using previous vantage points or nearby collaborators

• Scheduling systems: Automated seating generators must produce valid derangements

• Logistics optimization: Similar constraints appear in conference seating and event planning

• Looking to step up your coding interview prep? Check out our Tutoring Page for personalized 1-on-1 coaching.*

Step-by-Step Breakdown

Step 1: Understanding the Constraints

Let's label students S₁, S₂, ..., Sₙ. Let desks D₁, D₂, ..., Dₙ represent the desks they used in the first exam. For the second exam, student Sᵢ cannot be assigned to desk Dᵢ.

This is mathematically identical to a derangement: a permutation of N items with no fixed points.

Step 2: Visualizing the Seating Graph

The diagram shows a valid rearrangement (a 3-cycle) and an invalid one (S₁ stayed at Desk 1).

Step 3: Small Case Analysis

2 students: A and B, desks 1 and 2.

• Valid: A→Desk2, B→Desk1 (swap)

• Invalid: A→Desk1, B→Desk2 (both in original spots)

• Count: 1 valid arrangement

3 students: A, B, C with desks 1, 2, 3.
Let's systematically count:

• Valid: (A→2, B→3, C→1) and (A→3, B→1, C→2)

• All other 4 permutations have at least one fixed point

• Count: 2 valid arrangements

4 students: The count jumps to 9 valid arrangements.

Step 4: Deriving the Recurrence Relation

Let E(N) be the number of valid exam seating arrangements for N students.

Step 1: Where does Student 1 sit? Student 1 cannot sit at Desk 1. So Student 1 chooses any of the other (N - 1) desks. Let's say Student 1 sits at Desk k.

Step 2: Where does Student k sit? Now consider Student k (the student originally at Desk k). Two possibilities:

Possibility 1: Student k sits at Desk 1

• Student 1 and Student k have swapped desks

• The remaining (N - 2) students must form a valid rearrangement among themselves

• Number of ways: E(N - 2)

Possibility 2: Student k does NOT sit at Desk 1

• Student 1 is at Desk k

• Student k cannot sit at Desk 1 (by this scenario) and also cannot sit at Desk k (original spot)

• This is equivalent to finding a valid rearrangement for the remaining (N - 1) students, with Desk 1 now "forbidden" for Student k

• Number of ways: E(N - 1)

Step 3: Combine
For each of the (N - 1) choices for Student 1's desk:

E(N) = (N - 1) × [E(N - 1) + E(N - 2)]

With base cases: E(1) = 0, E(2) = 1.

Step 5: Naive Recursive Implementation

def exam_seating_recursive(n: int) -> int:
    """
    Naive recursive solution for exam seating rearrangements.
    
    Time: O(2^n) - Exponential, impractical for n > 30
    Space: O(n) - Recursion stack depth
    
    This directly translates the recurrence but suffers from massive
    overlapping subproblems.
    """
    if n == 1:
        return 0  # One student cannot avoid their original desk
    if n == 2:
        return 1  # Only a swap between the two students
    
    return (n - 1) * (exam_seating_recursive(n - 1) + 
                      exam_seating_recursive(n - 2))

# Calculate for a typical class size
print(f"E(5) = {exam_seating_recursive(5)}")  # 44

Why this fails for real classrooms: A typical class has 30+ students. Computing E(30) recursively would require over a billion function calls.

Step 6: Top-Down DP with Memoization

def exam_seating_top_down(n: int, memo: dict = None) -> int:
    """
    Top-down dynamic programming with memoization.
    
    Time: O(n) - Each n computed once
    Space: O(n) - Memoization dictionary + recursion stack
    
    This makes computing E(30) instantaneous.
    """
    if memo is None:
        memo = {}
    
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n in memo:
        return memo[n]
    
    memo[n] = (n - 1) * (exam_seating_top_down(n - 1, memo) + 
                         exam_seating_top_down(n - 2, memo))
    return memo[n]

# Example for a real classroom
print(f"E(25) = {exam_seating_top_down(25):,}")
# Output: Approximately 1.6 × 10^25

Practical insight: For a class of 25 students, there are over 1.6 × 10^25 valid seating arrangements—far more than the number of atoms in a human body. The professor will never run out of options.

Step 7: Bottom-Up DP with Tabulation

def exam_seating_bottom_up(n: int) -> int:
    """
    Bottom-up dynamic programming using tabulation.
    
    Time: O(n)
    Space: O(n) - Full DP array
    
    This approach is useful when you need to compute all values
    up to n for analysis or visualization.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    dp = [0] * (n + 1)
    dp[1] = 0
    dp[2] = 1
    
    for i in range(3, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
    
    return dp[n]

def analyze_seating_growth(max_n: int = 15):
    """Analyze how E(N) grows with N."""
    print("N\tE(N)\t\t\tGrowth Factor")
    print("-" * 50)
    prev = 0
    for n in range(1, max_n + 1):
        current = exam_seating_bottom_up(n)
        if n > 2:
            ratio = current / prev if prev > 0 else 0
            print(f"{n}\t{current:,}\t\t{ratio:.2f}")
        else:
            print(f"{n}\t{current}")
        prev = current

analyze_seating_growth()

Output shows E(N) grows faster than exponentially, roughly N!/e.

Step 8: Space-Optimized Solution for Production Systems

def exam_seating_optimized(n: int) -> int:
    """
    Space-optimized bottom-up solution.
    
    Time: O(n)
    Space: O(1) - Only two variables
    
    This is ideal for implementing in actual seating assignment systems
    where memory efficiency matters.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    prev2 = 0  # E(1)
    prev1 = 1  # E(2)
    
    for i in range(3, n + 1):
        current = (i - 1) * (prev1 + prev2)
        prev2 = prev1
        prev1 = current
    
    return prev1

# Real-world usage: Check if a seating assignment is valid
def is_valid_seating(assignment: list) -> bool:
    """
    Check if a seating assignment is a valid derangement.
    
    Args:
        assignment: List where assignment[i] = desk assigned to student i
        
    Returns:
        True if no student gets their original desk, False otherwise
    """
    for i, desk in enumerate(assignment):
        if desk == i:  # Student i got desk i (their original)
            return False
    return True

# Example
valid = [2, 0, 1]  # Student0→Desk2, Student1→Desk0, Student2→Desk1
invalid = [0, 2, 1]  # Student0 got Desk0 (original)
print(f"Valid assignment valid? {is_valid_seating(valid)}")    # True
print(f"Invalid assignment valid? {is_valid_seating(invalid)}")  # False

Ready to crush your next technical interview?
Visit our Order Page now to grab our exclusive Dynamic Programming bootcamp courses!

Common Mistakes

Mistake 1: Assuming All Permutations Are Equally Likely in Random Assignment

When professors use software to randomize seating, they often assume a simple shuffle produces a valid derangement. But a random permutation has only a ~36.8% chance of being a derangement. You need rejection sampling or a derangement-specific generator.

Mistake 2: Forgetting the N=1 Edge Case

In implementation, forgetting that E(1) = 0 causes off-by-one errors. Some incorrectly set E(1) = 1, leading to incorrect counts for all larger N.

Mistake 3: Confusing Desks with Students

The desks are identical except for their labels (positions). The constraint is about the mapping from students to desk positions, not physical desk properties.

Mistake 4: Not Handling Large N in Production

For a university with 500 students per exam, E(500) has over 1,000 digits. Don't try to store the exact integer if you only need the probability. Use floating-point approximations or modular arithmetic.

Frequently Asked Questions

Q1: Can two students swap desks in the rearrangement?

A: Yes. Swaps are valid as long as neither student stays in their original desk. In fact, a derangement can consist entirely of swaps (e.g., N=2 is just one swap) or cycles of length 3 or more.

Q2: How does this apply to online proctoring?

A: Online proctoring systems use similar logic to assign virtual "seats" or camera positions. No student should get the same virtual seat twice to prevent predictability in exam monitoring.

Q3: What if the classroom has more desks than students?

A: Then it's not a derangement problem. You'd need to count injections (one-to-one mappings) where no student gets their original desk, but desks can be empty. This is a different combinatorial problem.

Q4: Is there a formula for the number of derangements without dynamic programming?

A: Yes: !N = round(N! / e). This approximation is exact for N ≥ 1 when rounded to the nearest integer. For N=4, 4!/e ≈ 24/2.71828 ≈ 8.829, rounded to 9. Works perfectly.

Conclusion

Exam seating rearrangements demonstrate how derangements solve real logistical problems. The recurrence E(N) = (N-1) × (E(N-1) + E(N-2)) is the same as other derangement problems, but the interpretation—seating charts, not gift exchanges—gives it different practical implications.

You've learned to implement this recurrence efficiently, from exponential recursion to O(1)-space optimization. More importantly, you've seen how to validate seating assignments and why random shuffling isn't enough. 

The next time you're in a classroom and notice you never sit in the same spot twice, you'll know the mathematics behind it.

Take Your Skills to the Next Level!
Want to master Advanced Dynamic Programming alongside FAANG engineers? Our platform has everything you need.

👉 Visit Our Tutoring Page to book a session today.
👉 Check Our Order Page for direct access to our full DP coursework!

👉 Delve into Derangements in detail for better mastery!