如何在Python中生成数组的所有无重复全排列？

Got it, let's break this down clearly. First, let's make sure we're on the same page about full permutations: a full permutation of an array is every possible unique rearrangement where each element appears exactly once in the sequence. For your example array=[1,2,3], that gives the 6 permutations you listed: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.

How to Conceptually Generate Full Permutations #

Before diving into code, let's walk through the manual logic—this helps you understand the algorithm behind it:

• Fix the first element: Pick the first element (e.g., 1), then generate all permutations of the remaining elements ([2,3]), which are [2,3] and [3,2]. Combine these to get 1 2 3 and 1 3 2.
• Shift to the next element: Fix 2 as the first element, generate permutations of [1,3] ([1,3] and [3,1]), resulting in 2 1 3 and 2 3 1.
• Repeat for the final element: Fix 3 first, permute [1,2] to get 3 1 2 and 3 2 1.

Python Implementations for Unique Full Permutations #

Now let's look at two solid ways to generate unique permutations in Python—one using a built-in library (fast and straightforward) and one custom recursive implementation (great for learning the underlying logic).

1. Using itertools.permutations (Built-in Library) #

Python's standard itertools module has a permutations function that handles permutations out of the box. Note that if your array has duplicate elements, it will generate duplicate permutations based on element positions, so we'll add a step to deduplicate those:

import itertools

# Example with no duplicate elements
array = [1,2,3]
# Get all permutations (returns an iterator of tuples)
all_permutations = list(itertools.permutations(array))
# Convert tuples to space-separated strings for output
for perm in all_permutations:
    print(' '.join(map(str, perm)))

# Example with duplicate elements (to get unique permutations)
array_with_duplicates = [1,1,2]
# Use a set to eliminate duplicate permutations, then convert back to list
unique_perms = list(set(itertools.permutations(array_with_duplicates)))
print("\nUnique permutations for [1,1,2]:")
for perm in unique_perms:
    print(' '.join(map(str, perm)))

2. Custom Recursive Backtracking Implementation #

If you want to build the logic yourself (or need more control over the process), a backtracking approach is ideal. This implementation automatically skips duplicate elements to avoid redundant permutations:

def generate_unique_permutations(nums):
    permutations = []
    
    def backtrack(start_index):
        # When we've reached the end of the array, save the current permutation
        if start_index == len(nums):
            permutations.append(' '.join(map(str, nums.copy())))
            return
        
        # Track elements we've already used at this position to avoid duplicates
        used = set()
        for i in range(start_index, len(nums)):
            if nums[i] in used:
                continue
            used.add(nums[i])
            
            # Swap the current element to the start position
            nums[start_index], nums[i] = nums[i], nums[start_index]
            # Recurse on the remaining elements
            backtrack(start_index + 1)
            # Swap back (backtrack) to reset for the next iteration
            nums[start_index], nums[i] = nums[i], nums[start_index]
    
    backtrack(0)
    return permutations

# Test with your example array
print("Permutations for [1,2,3]:")
for p in generate_unique_permutations([1,2,3]):
    print(p)

# Test with an array containing duplicates
print("\nUnique permutations for [1,1,2]:")
for p in generate_unique_permutations([1,1,2]):
    print(p)

This backtracking function works by fixing elements one position at a time. We use a set to track which elements we've already placed at the current index, ensuring we don't generate duplicate permutations when the input has repeated values. After recursing on the rest of the array, we swap elements back to reset the state for the next iteration.

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