Skip to content
TheChatArchiveThe Chat Archive
Grok 4.1 Fast· xaiHugging Face Frontier Reasoning Traces

Develop an algorithm to generate all unique permutations of a multiset.

  1. User

    Develop an algorithm to generate all unique permutations of a multiset.

  2. 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

    1. Sort the input: Ensures identical elements are adjacent, enabling duplicate detection.
    2. 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).
    3. Base case: When the path length equals input length, add a copy to results.
    4. Backtrack: Remove the last element and mark as unused.

    This generates exactly the unique permutations in O(n! / (k₁! × k₂! × ... × kₘ!)) time, where n is length and k_i are 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] = False
    

    Python 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 1 (i=2=2): Pick 2 → path=[2]
      • Level 2: Pick first 1 → [2,1,1]
    • Skips ensure no [1,1,2] duplicate from second 1.

    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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.