Develop an algorithm to generate all unique permutations of a multiset.
- User
Develop an algorithm to generate all unique permutations of a multiset.
- Assistant
Algorithm to Generate All Unique Permutations of a Multiset
Problem Overview
Given a multiset (represented as an array/list with possible duplicate elements), generate all unique permutations without duplicates. For example:
- Input:
[1, 1, 2] - Output:
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Naive permutation generation (e.g., Heap's algorithm) produces duplicates for multisets. This algorithm uses backtracking with duplicate skipping to ensure uniqueness efficiently.
Approach
- Sort the input: Ensures identical elements are adjacent, enabling duplicate detection.
- Backtracking:
- Build the permutation incrementally.
- Track used indices with a boolean array.
- For each position, iterate through elements:
- Skip if already used.
- Duplicate skip rule: If the current element equals the previous one and the previous one is unused, skip it (prevents generating identical branches).
- Base case: When the path length equals input length, add a copy to results.
- Backtrack: Remove the last element and mark as unused.
This generates exactly the unique permutations in O(n! / (k₁! × k₂! × ... × kₘ!)) time, where
nis length andk_iare frequencies of distinct elements (optimal, as it matches the output size).Pseudocode
function generateUniquePermutations(nums): sort(nums) // O(n log n) result = empty list used = array of False with size n path = empty list backtrack(path, nums, used, result) return result function backtrack(path, nums, used, result): if length(path) == length(nums): append copy-of(path) to result return for i from 0 to length(nums)-1: if used[i]: continue // Skip duplicates: same as prev and prev unused if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue // Choose this element used[i] = True append nums[i] to path backtrack(path, nums, used, result) // Backtrack pop last from path used[i] = FalsePython Implementation (for clarity)
def generate_unique_permutations(nums): def backtrack(path, nums, used, result): if len(path) == len(nums): result.append(path[:]) # Copy list return for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(nums[i]) backtrack(path, nums, used, result) path.pop() used[i] = False nums.sort() result = [] used = [False] * len(nums) backtrack([], nums, used, result) return result # Example usage print(generate_unique_permutations([1, 1, 2])) # Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]Example Walkthrough:
[1, 1, 2](sorted)- Start: path = []
- Level 1 (i=0,1=1): Pick first
1→ path=[1]- Level 2 (i=1,2=2): Skip i=1 (dup & unused prev), pick i=2 → path=[1,2]
- Level 3: Pick i=1 → [1,2,1]
- Backtrack
- Level 2 (i=1,2=2): Skip i=1 (dup & unused prev), pick i=2 → path=[1,2]
- Level 1 (i=2=2): Pick
2→ path=[2]- Level 2: Pick first
1→ [2,1,1]
- Level 2: Pick first
- Skips ensure no
[1,1,2]duplicate from second1.
Complexity
- Time: O(n! / ∏k_i!) × O(n) (for copying paths); exponential but optimal for output size.
- Space: O(n) recursion depth + O(output size).
- Handles edge cases: empty list →
[]; all unique → all perms; all identical → single perm.
This is production-ready and widely used (e.g., LeetCode 47). For very large
n, consider iterative approaches or output streaming. - Input:
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.