Java排列生成程序的实现分析及复杂度详解请求

Let’s break down how this recursive permutation generator works, how it aligns with the O(n*n!) time complexity you noted, and some key implementation details to watch for.

1. High-Level Overview #

This code uses a recursive insertion approach to generate all permutations of a list. The core idea is: take the first element of the list, recursively generate all permutations of the remaining elements, then insert that first element into every possible position of each of those sub-permutations.

The main method is straightforward:

• It initializes a sample list ([1,2,3]).
• Calls listPermutations to generate all permutations.
• Iterates over the result and prints each permutation (each print operation takes O(n) time per permutation, as you mentioned).

2. Recursive Core: The listPermutations Method #

Let’s walk through this method step by step.

Base Case (Empty List) #

if (list.size() == 0) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    result.add(new ArrayList<Integer>());
    return result;
}

When the input list is empty, we return a list containing one empty list. This is our recursive termination condition—there’s exactly one permutation of an empty list (the empty list itself). This operation runs in O(1) time.

Recursive Step #

First, we extract the first element from the input list:

Integer firstElement = list.remove(0);
List<List<Integer>> recursiveReturn = listPermutations(list);

We recursively generate all permutations of the remaining elements (the list with the first element removed). For a list of length k, this recursive call returns (k-1)! permutations (since that’s how many permutations exist for a list of length k-1).

Next, we build the full set of permutations by inserting the first element into every possible position of each sub-permutation:

for (List<Integer> li : recursiveReturn) {
    for (int index = 0; index <= li.size(); index++) {
        List<Integer> temp = new ArrayList<Integer>(li);
        temp.add(index, firstElement);
        returnMe.add(temp);
    }
}

• For each sub-permutation li (length k-1), there are k possible insertion positions (from 0 to li.size(), inclusive).
• We create a copy of li (new ArrayList<Integer>(li)) to avoid modifying the original sub-permutation—critical for preserving the recursive results.
• Inserting firstElement at position index gives us a new permutation of length k, which we add to the result list.

3. Time Complexity Breakdown #

Let’s verify why this algorithm runs in O(n*n!) time:

Recursive Time Calculation #

Let T(k) be the time to generate permutations for a list of length k:

• T(0) = O(1) (base case)
• For k > 0, the total operations scale with the sum of k*k! from k=1 to n.

Here’s why:

• For each list length k, we generate k! permutations.
• Each permutation of length k requires inserting an element into a list of length k-1 (an O(k) operation for ArrayList, since elements need to be shifted).
• The sum sum_{k=1}^n k*k! simplifies to (n+1)! - 1, which is asymptotically equivalent to O(n*n!) (since (n+1)! = (n+1)*n!, which falls into the same complexity class as n*n!).

Printing Overhead #

Printing each permutation takes O(n) time (one print operation per element), and there are n! permutations. So total printing time is O(n*n!), matching the generation time.

4. Key Implementation Observations #

• Side Effect on Input List: The list.remove(0) modifies the original input list passed to the recursive call. For example, the intList in main will be empty after listPermutations returns. If you need to preserve the original list, modify the code to create a copy before removing the first element:

  List<Integer> subList = new ArrayList<>(list);
  Integer firstElement = subList.remove(0);
  List<List<Integer>> recursiveReturn = listPermutations(subList);
  

• Immutable Permutations: By creating a new ArrayList for each insertion (new ArrayList<Integer>(li)), we ensure each permutation is an independent list. This prevents unintended modifications to existing permutations during the insertion loop.

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