变位词（Anagram）代码优化提速及错位排列计数方案咨询

Hey there! Let's fix that slow permutation/derangement issue you're dealing with. The biggest bottleneck in your original code is that it generates all possible permutations first and then filters out the derangements (permutations with no element in its original position). For 10 elements that's ~3.6 million permutations, and for 11 it jumps to ~40 million—no wonder it's crawling! We can fix this by building derangements directly during the permutation process, which cuts down on unnecessary work drastically.

Key Optimizations We'll Implement #

• Generate derangements directly: Skip any recursive branch where we place an element in its original position, instead of filtering after the fact.
• Reduce memory overhead: Process each valid derangement as we generate it, instead of storing all permutations in a huge list first.
• Minimize unnecessary conversions: Cut down on ToList()/ToArray() calls that waste time and memory.
• Track counts and numbers: Add derangement numbering directly in the generation step without extra overhead.

Modified Full Code #

private void btnGo_Click(object sender, EventArgs e)
{
    this.Size = new Size(632, 430);
    button1.Visible = true;

    // Clean up input (remove empty entries from multiple spaces)
    string[] items = txtItems.Text.Split(' ', StringSplitOptions.RemoveEmptyEntries);
    int itemCount = items.Length;

    lstPermutations.Items.Clear();
    long derangementCount = 0;

    // Arrays to track selection state and current permutation
    bool[] inSelection = new bool[itemCount];
    string[] currentPermutation = new string[itemCount];

    // Generate derangements directly (no full permutation list!)
    GenerateDerangements(items, inSelection, currentPermutation, 0, ref derangementCount);

    // Update UI with total derangement count
    txtNumPermutations.Text = derangementCount.ToString();
}

// Recursively generate only valid derangements (no element in original position)
private void GenerateDerangements(string[] originalItems, bool[] inSelection, string[] currentPermutation, int nextPosition, ref long derangementCount)
{
    int itemCount = originalItems.Length;

    // If we've filled all positions, this is a valid derangement
    if (nextPosition == itemCount)
    {
        derangementCount++;
        // Format output based on checkbox state
        string output = checkBox1.Checked 
            ? string.Join("", currentPermutation) 
            : string.Join(" ", currentPermutation);
        // Add numbered entry to the list
        lstPermutations.Items.Add($"#{derangementCount}: {output}");
        return;
    }

    // Try each unused item for the current position
    for (int i = 0; i < itemCount; i++)
    {
        if (!inSelection[i])
        {
            // Skip placing the item in its original position (derangement rule)
            if (i == nextPosition)
                continue;

            // Mark item as selected and add to current permutation
            inSelection[i] = true;
            currentPermutation[nextPosition] = originalItems[i];

            // Recurse to fill remaining positions
            GenerateDerangements(originalItems, inSelection, currentPermutation, nextPosition + 1, ref derangementCount);

            // Unmark item for next iterations
            inSelection[i] = false;
        }
    }
}

// Optional: Calculate derangement count mathematically (for validation)
private long CalculateDerangementCount(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 0;
    return (n - 1) * (CalculateDerangementCount(n - 1) + CalculateDerangementCount(n - 2));
}

What Changed & Why #

1. Direct Derangement Generation:

   • The new GenerateDerangements method skips any attempt to place an item in its original position (if (i == nextPosition) continue;), so we never generate invalid permutations in the first place. For n=10, this cuts the number of recursive calls from ~3.6 million to ~1.3 million—huge savings!

2. Memory Savings:

   • We no longer store all permutations in a List<List<T>>—instead, we add each valid derangement directly to the list box as we generate it. This avoids holding millions of objects in memory at once, which boosts both speed and stability.

3. Numbered Entries:

   • We track derangementCount as a reference parameter, incrementing it each time we complete a valid derangement. This lets us add numbered entries (#1: ..., #2: ...) without extra post-processing.

4. Cleaner Input Handling:

   • Added StringSplitOptions.RemoveEmptyEntries to avoid empty strings if the user enters multiple spaces.

Additional Tips for Even More Speed #

• Handle Duplicate Elements: If your input can have duplicate items, add a check to skip duplicate values in the loop (e.g., if originalItems[i] == originalItems[i-1] and inSelection[i-1] == false, skip). This avoids generating duplicate derangements.
• Use StringBuilder: For very long outputs, replace string.Join with a StringBuilder to reduce string allocation overhead.
• Async Processing: If you're dealing with n>12, consider running the generation in a background thread (using Task.Run) to keep the UI responsive.

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