Permutations II

// C++ Implementation
class Solution {
public:
    vector<vector<int>> generatePermutations(vector<int>& elements) {
        vector<vector<int>> solutions;
        unordered_map<int, int> frequency;
        for (int element : elements) frequency[element]++;
        vector<int> currentCombination;
        permuteRecursively(frequency, currentCombination, elements.size(), solutions);
        return solutions;
    }
    void permuteRecursively(unordered_map<int, int>& frequency, vector<int>& combination, int length,
                   vector<vector<int>>& solutions) {
        if (combination.size() == length) {
            solutions.push_back(combination);
            return;
        }
        for (auto& pair : frequency) {
            int value = pair.first;
            int count = pair.second;
            if (count == 0) continue;
            combination.push_back(value);
            frequency[value]--;
            permuteRecursively(frequency, combination, length, solutions);
            combination.pop_back();
            frequency[value]++;
        }
    }
};

The provided C++ code outlines a solution for generating all unique permutations of a list of numbers, potentially including duplicates. This task is effectively executed using backtracking and an unordered map to manage the frequency of each element, ensuring an efficient manner of handling repetitions. Below is a breakdown of how the code operates:

• Initialization of Data Structures:

  • A vector<vector<int>> named solutions to store all the unique permutations.
  • An unordered_map<int, int> called frequency to count occurrences of each number in the input elements.

• Building Frequency Map:

  • Loop through each number in the elements vector and update its count in the frequency map.

• Recursive Function – permuteRecursively:

  • Checks if the size of the current permutation combination matches the original list's length. If true, the permutation is complete and added to solutions.
  • Iterates through each element in the frequency map:
    • If an element's count is zero, it continues to the next element (as none are left to place).
    • Otherwise, the element is added to the current combination, its count is decreased, and the function recurses to fill the next position in the combination.
    • After recursion, the last added element is removed (backtracking) and its count restored, allowing the next potential element to be considered at the current position in the permutation.

• Generation and Return of Results:

  • The generatePermutations function returns the solutions vector, containing all unique permutations generated.

The method efficiently handles the generation of permutations by advancing only with valid sequences using the counts in the frequency map, thereby avoiding duplicates without requiring complex logic or additional data structures. Make sure to include preprocessing if required, depending on how the initial input is provided or could vary.

class PermutationGenerator {
    public List<List<Integer>> generatePermutations(int[] elements) {
        List<List<Integer>> allPermutations = new ArrayList<>();
    
        // Map for counting occurrences
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int element : elements) {
            frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
        }
    
        LinkedList<Integer> currentCombination = new LinkedList<>();
        backtrackPermutations(currentCombination, elements.length, frequencyMap, allPermutations);
        return allPermutations;
    }
    
    private void backtrackPermutations(
        LinkedList<Integer> currentComb,
        Integer totalLength,
        HashMap<Integer, Integer> frequencyMap,
        List<List<Integer>> allPermutations
    ) {
        if (currentComb.size() == totalLength) {
            allPermutations.add(new ArrayList<>(currentComb));
            return;
        }
    
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            Integer currentElement = entry.getKey();
            Integer currentCount = entry.getValue();
            if (currentCount == 0) continue;
                
            currentComb.addLast(currentElement);
            frequencyMap.put(currentElement, currentCount - 1);
    
            backtrackPermutations(currentComb, totalLength, frequencyMap, allPermutations);
    
            currentComb.removeLast();
            frequencyMap.put(currentElement, currentCount);
        }
    }
}

The Java solution provided generates all unique permutations of a given array where the elements might have duplicates. This is achieved using backtracking, a common technique for exploring all possible configurations of a problem space. Here is a detailed breakdown of the approach taken:

• A HashMap called frequencyMap is utilized to store the frequency of each element in the input array. This helps in handling duplicates by ensuring that each permutation includes the correct count of elements.

• The generatePermutations function initiates the process by preparing the data structure for the permutations (allPermutations), and invoking the backtrackPermutations helper method with the initial state.

• In backtrackPermutations, a LinkedList called currentComb is used to build permutations incrementally:

  1. If the length of currentComb equals the length of the input array, a complete permutation is achieved. This permutation is then added to allPermutations.

  2. The function then iterates through each entry in frequencyMap. If the count of an element is not zero, the element is added to the current combination, and its count is decremented in the map. This ensures not to use the element more times than it appears in the original array.

  3. A recursive call is made with the updated state (current combination and frequency map).

  4. After the recursive call, the last element added to the combination is removed (backtrack), and its count in the frequency map is restored.

The advantage of this method lies in efficiently handling duplicates by managing counts of elements, thus avoiding generating non-unique permutations only to filter them out later. This implementation helps in optimizing time complexity relative to approaches that generate all permutations and then remove duplicates.

struct hash_table_entry {
    int key;
    int count;
    UT_hash_handle hh;
};
    
void recursiveBacktrack(int* arr, int arrSize, int* sequence, int seqLength, int** results,
                        int* resultCount, int** resultColSizes,
                        struct hash_table_entry* elementsCount) {
    if (seqLength == arrSize) {
        results[*resultCount] = malloc(arrSize * sizeof(int));
        memcpy(results[*resultCount], sequence, arrSize * sizeof(int));
        resultColSizes[0][*resultCount] = arrSize;
        (*resultCount)++;
        return;
    }
    struct hash_table_entry *element, *tempElement;
    HASH_ITER(hh, elementsCount, element, tempElement) {
        if (element->count > 0) {
            sequence[seqLength] = element->key;
            element->count--;
            recursiveBacktrack(arr, arrSize, sequence, seqLength + 1, results, resultCount,
                               resultColSizes, elementsCount);
            element->count++;
        }
    }
}
    
int** generateUniquePermutations(int* elements, int elementsSize, int* outSize,
                                 int** outColumnSizes) {
    struct hash_table_entry *elementsCount = NULL, *entry;
    for (int i = 0; i < elementsSize; i++) {
        HASH_FIND_INT(elementsCount, &elements[i], entry);
        if (entry == NULL) {
            entry = malloc(sizeof(struct hash_table_entry));
            entry->key = elements[i];
            entry->count = 1;
            HASH_ADD_INT(elementsCount, key, entry);
        } else {
            entry->count++;
        }
    }
    int** output = malloc(10000 * sizeof(int*));
    *outColumnSizes = malloc(10000 * sizeof(int));
    *outSize = 0;
    int* sequence = malloc(elementsSize * sizeof(int));
    recursiveBacktrack(elements, elementsSize, sequence, 0, output, outSize, outColumnSizes,
                       elementsCount);
    return output;
}

This C program allows the generation of unique permutations of a given set of integers, which can include duplicates, and outputs them in a 2D integer array. The solution leverages a combination of recursive backtracking and a hash table to efficiently track and manage the count of each element during the permutation generation process.

The generateUniquePermutations function initializes the hash table for element counts, checks and increments counts while iterating through the input array. It also prepares the output structure and triggers the recursive permutation generation via the recursiveBacktrack function.

• In the recursiveBacktrack function:
  • If the current sequence length matches the array size, the sequence is stored as a permutation.
  • Iterates over the hash table to explore permutations from elements with remaining counts, manipulating counts recursively to generate permutations without duplicates.

The use of hash tables (UT_hash_handle) from uthash.h library facilitates quick lookup, addition, and deletion to manage element frequencies effectively during permutation generation. The primary function allocates memory for the necessary structures and initializes them appropriately to handle up to 10,000 permutations initially, which implies that adjustment may be needed based on input size or unique permutations possible to prevent memory overflow or under-allocation.

Ensure proper freeing of allocated memory in actual implementation to avoid memory leaks. This C program is particularly adept at dealing with permutations of arrays where elements might repeat, directly addressing challenges related to duplicate values. Make sure to include uthash.h in your environment when compiling and executing this solution.

// JavaScript Code
var findUniquePermutations = function (elements) {
    let output = [];
    let freqMap = {};
    elements.forEach(element => {
        if (!freqMap[element]) freqMap[element] = 0;
        freqMap[element]++;
    });
    function explore(path, length) {
        if (path.length === length) {
            output.push([...path]);
            return;
        }
        for (let element in freqMap) {
            if (freqMap[element] === 0) continue;
            path.push(parseInt(element));
            freqMap[element]--;
            explore(path, length);
            freqMap[element]++;
            path.pop();
        }
    }
    explore([], elements.length);
    return output;
};

This tutorial covers how to solve the problem of generating all unique permutations of a list of numbers that may include duplicates, using JavaScript. The approach used involves backtracking to ensure each permutation is unique by using a frequency map to control element inclusion.

• Initialization:

  • Start by declaring a function findUniquePermutations which takes elements as its input.
  • Inside this function, declare an empty array output to store the unique permutations and an object freqMap to count the frequency of each element in the elements array.

• Frequency Map Construction:

  • Iterate over the elements array and populate freqMap. For each element, check if it already exists in the map. If it exists, increment its count; otherwise, add it with a count of 1.

• Backtracking Function (explore):

  • Define a function explore which will be used recursively. This function takes path (to store the current permutation) and length (the desired length of the permutation, which is the same as the length of elements).
  • Check if the current path.length is equal to length. If true, it means a complete permutation has been formed:
    • Push a copy of path to output.
    • Return to exit the current recursive call.
  • Iterate over each element in freqMap:
    • If the current element’s frequency is zero, continue to the next element (it means this element has been fully used in this branch of recursion).
    • Add the element to the path and decrement its frequency in freqMap.
    • Recursively call explore.
    • Backtrack by incrementing the frequency of the current element and removing it from path.

• Execution and Return:

  • Call the explore function initially with an empty path and the length of elements.
  • Return the output array, which now contains all unique permutations.

By the end of this guide, you efficiently solve the problem using the concepts of backtracking combined with a frequency map, ensuring that you can handle permutations of arrays with duplicate elements effectively in JavaScript.

class Solution:
    def uniquePermutations(self, numbers: List[int]) -> List[List[int]]:
        result_set = []
    
        def dfs(current_state, count_map):
            if len(current_state) == len(numbers):
                result_set.append(list(current_state))
                return
    
            for value in count_map:
                if count_map[value] > 0:
                    current_state.append(value)
                    count_map[value] -= 1
                    dfs(current_state, count_map)
                    current_state.pop()
                    count_map[value] += 1
    
        dfs([], Counter(numbers))
    
        return result_set

The provided Python solution focuses on generating all unique permutations of a given list of numbers. Here is the approach detailed in the solution:

• The uniquePermutations method takes a list numbers as input and initializes an empty list result_set to hold the resultant permutations.

• A recursive function dfs (Depth-First Search) is defined within uniquePermutations. It operates by building permutations one element at a time:

  • It checks if the length of the current permutation under construction (current_state) is equal to the length of numbers. If true, it adds this permutation to result_set and returns to explore other possibilities.
  • The function iterates over a frequency count (count_map) of the numbers. If a number's count is above zero, the number is added to current_state, and its count is decreased by one. After the recursive call to dfs, the number is removed from current_state (backtracking), and its count is restored.

• The recursive process starts by calling dfs with an empty list and a counter of the numbers (generated using Counter(numbers) from Python's collections module), which keeps track of the frequency of each number in the input list.

• The completed result_set, containing all unique permutations, is then returned.

Overall, this approach ensures that all permutations of the numbers are considered, while the use of backtracking prevents duplicates and ensures all permutations are unique. The frequency map (counter) aids in efficiently tracking and managing the elements during permutation generation.