Angular中如何实现题目顺序约束检查并规避循环冲突？

This problem is a perfect fit for topological sorting—a technique designed to order elements with directional dependencies (like "q1 must come before q4"). To add randomness while respecting all constraints, we can modify the standard topological sort algorithm to randomly select eligible nodes at each step.

Step 1: Define the Data Model #

Let’s ground this in concrete terms:

• Each question is represented by a unique numeric ID (e.g., q1 = 1, q2 = 2, etc.).
• Your constraints array is a list of [prevId, nextId] pairs, where prevId must appear before nextId in the final sorted list.

Step 2: Implement the Algorithm #

We’ll use Kahn's Algorithm (an in-degree based approach) with a random twist to generate valid, randomized orderings. Here’s a TypeScript implementation tailored to your needs:

type QuestionId = number;
type Constraint = [QuestionId, QuestionId];

function constrainedShuffle(
  allQuestionIds: QuestionId[],
  constraints: Constraint[]
): QuestionId[] | null {
  // Build adjacency list and in-degree map for the graph
  const adjacencyList = new Map<QuestionId, QuestionId[]>();
  const inDegree = new Map<QuestionId, number>();

  // Initialize maps with all questions
  allQuestionIds.forEach(id => {
    adjacencyList.set(id, []);
    inDegree.set(id, 0);
  });

  // Populate graph from constraints
  constraints.forEach(([prev, next]) => {
    adjacencyList.get(prev)!.push(next);
    inDegree.set(next, inDegree.get(next)! + 1);
  });

  // Start with nodes that have no dependencies (in-degree 0)
  let eligibleNodes = allQuestionIds.filter(id => inDegree.get(id) === 0);
  const result: QuestionId[] = [];

  // Process nodes randomly to introduce shuffle
  while (eligibleNodes.length > 0) {
    // Pick a random eligible node to add randomness
    const randomIndex = Math.floor(Math.random() * eligibleNodes.length);
    const currentId = eligibleNodes.splice(randomIndex, 1)[0];
    
    result.push(currentId);

    // Update dependencies for neighboring nodes
    adjacencyList.get(currentId)!.forEach(neighborId => {
      const newDegree = inDegree.get(neighborId)! - 1;
      inDegree.set(neighborId, newDegree);
      if (newDegree === 0) {
        eligibleNodes.push(neighborId);
      }
    });
  }

  // Check for cycles (if not all questions are included in result)
  if (result.length !== allQuestionIds.length) {
    console.error("Cycle detected in constraints! A valid order is impossible.");
    return null;
  }

  return result;
}

How It Works #

1. Graph Construction: We convert your constraints into a directed graph where each edge prev → next enforces the "prev before next" rule.
2. Eligible Nodes: Nodes with no incoming edges (in-degree 0) have no dependencies and can be placed early in the order.
3. Random Selection: Instead of processing eligible nodes in a fixed order, we pick one at random each time. This ensures valid randomization while honoring all constraints.
4. Cycle Detection: If the final result doesn’t include all questions, it means there’s a cycle in your constraints (e.g., q1 before q2, q2 before q1)—a scenario where no valid order exists.

Example Usage #

// List of all question IDs
const questions = [1, 2, 3, 4];
// Constraints: q1 before q4, q3 before q2
const constraints: Constraint[] = [[1,4], [3,2]];

// Generate a valid randomized order
const shuffled = constrainedShuffle(questions, constraints);
console.log(shuffled); 
// Possible outputs: [3,1,2,4], [1,3,2,4], [3,1,4,2], etc.
// Notice q1 always comes before q4, q3 always before q2

Key Notes #

• Randomness: The randomness comes from choosing eligible nodes randomly. Each run can produce a different valid order.
• Cycle Handling: The function returns null if a cycle is detected—you should handle this case (e.g., alert the user to fix conflicting constraints).
• Scalability: This algorithm runs in O(V + E) time (V = number of questions, E = number of constraints), making it efficient even for larger lists.

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