如何优化生成符合约束的课程展示顺序的presOrder函数？

Great question! Using itertools.permutations to generate all possible permutations works for small class sizes, but it gets painfully slow once you have more than 8-10 names (since permutation count grows factorially). Here are targeted optimizations to make your presOrder function faster, more efficient, and more robust:

1. Generate Derangements Directly (Skip Non-Qualifying Permutations) #

Instead of generating every permutation and filtering out non-derangements (where someone stays in their previous position), generate random derangements directly. The probability of a random permutation being a derangement is ~1/e (~37%), so this is efficient even for moderate class sizes.

import random

def generate_random_derangement(original):
    k = len(original)
    if k == 1:
        return original.copy()  # No derangement possible for a single person
    
    while True:
        shuffled = original.copy()
        random.shuffle(shuffled)
        # Check if no element stays in its original position
        if all(shuffled[i] != original[i] for i in range(k)):
            return shuffled

2. Speed Up Cyclic Shift Checks #

Your original notRandom function likely checks all possible cyclic shifts, which is O(k²) time. Instead, find the shift value from the first element and verify if the rest of the permutation follows that shift pattern—this cuts the check to O(k) time.

def is_cyclic_shift(candidate, prev):
    k = len(candidate)
    if k <= 1:
        return True  # Trivial case (only possible if k=1)
    
    # Create a lookup dict for fast index retrieval (critical for large k)
    prev_index_map = {name: idx for idx, name in enumerate(prev)}
    try:
        shift = prev_index_map[candidate[0]]
    except ValueError:
        return False  # Should never happen since candidate is a permutation
    
    # Verify all elements follow the shift
    for i in range(k):
        if candidate[i] != prev[(i + shift) % k]:
            return False
    return True

For reverse cyclic shifts, just check if the candidate is a cyclic shift of the reversed previous week's order:

def is_reverse_cyclic_shift(candidate, prev):
    reversed_prev = prev[::-1]
    return is_cyclic_shift(candidate, reversed_prev)

3. Combine Checks & Terminate Early #

When generating each week's order, first generate a derangement, then check if it's a cyclic/reverse cyclic shift. If it is, generate another derangement—this avoids wasting time checking non-derangements for cyclic shifts.

4. Handle Edge Cases Gracefully #

Some class sizes make it impossible to generate a valid second week:

• k=1: Only one possible order, can't change
• k=2: The only derangement is swapping positions, which is a cyclic shift
• k=3: All derangements are cyclic shifts of the original order

Add a check to avoid infinite loops or invalid outputs:

def can_generate_multiple_weeks(k):
    return k >= 4  # Only possible for 4+ names

5. Optimized presOrder Function #

Putting it all together:

def presOrder(n, names):
    k = len(names)
    if k == 0:
        return []
    
    result = [names.copy()]
    if n == 1:
        return result
    
    # Check if multiple weeks are possible
    if not can_generate_multiple_weeks(k):
        raise ValueError(f"Cannot generate {n} weeks for {k} names—no valid permutations exist beyond the first week.")
    
    for _ in range(n-1):
        prev_week = result[-1]
        reversed_prev = prev_week[::-1]
        
        while True:
            candidate = generate_random_derangement(prev_week)
            # Check if candidate is a forbidden cyclic shift
            if not is_cyclic_shift(candidate, prev_week) and not is_cyclic_shift(candidate, reversed_prev):
                break
        
        result.append(candidate)
    
    return result

Additional Tips for Very Large Class Sizes #

• For k > 20, replace the shuffle-based derangement generator with a deterministic O(k) derangement algorithm (e.g., swapping elements with a non-matching index) to avoid rare loops.
• Precompute the reversed previous week once per iteration instead of re-generating it in each check.

This optimized version maintains all your requirements while being drastically faster for larger class sizes, and handles edge cases that could cause infinite loops or invalid outputs.

内容的提问来源于stack exchange，提问作者Clifton