Given an integer N, the task is to print all distinct permutations of the number N.
Examples:
Input: N = 133
Output: 133 313 331
Explanation:
There are a total of 6 permutations, which are [133, 313, 331, 133, 313, 331].
Out of all these permutations, distinct permutations are [133, 313, 331].Input: N = 7668
Output: 7668 7686 7866 6768 6786 6678 6687 6876 6867 8766 8676 8667
Approach: Follow the steps below to solve the problem:
- Initialize an empty string to store the equivalent string representation of N.
- Initialize a Map to convert each character of the string to an integer and store it as a list.
- Permute this list using built-in python functions itertools. permutations().
- Initialize another list, say newList.
- Traverse the permutations of the list and if the permutation(list) is not in newList then append this list to newList.
- Initialize an empty string, s = “” and another empty list say permuteList.
- Traverse the list newlist and for each list, perform the following operations:
- Traverse the list and add each element to the string s.
- After traversing, convert the string to an integer.
- Append this integer to permuteList.
- Print the values of permuteList as the possible distinct permutations.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;// Utility function to print all distinct permutationsvoid uniquePermutationsUtil(vector<string> permute){ vector<string> p; // Traverse the list permute[] for (string i : permute) { // Convert this permutation to list p.push_back(i); } // Stores unique permutations vector<string> newlist; // Traverse list p[] for (string i : p) { // If permutation is // not in newlist if (find(newlist.begin(), newlist.end(), i) == newlist.end()) { newlist.push_back(i); } } // Initialize empty list vector<int> permutelist; // Traverse the list newlist[] for (string i : newlist) { // Convert string to integer int s = stoi(i); // Append the unique // permutation to permutelist permutelist.push_back(s); } // Print all distinct permutations for (int i : permutelist) { cout << i << " "; }}// Function to print all distinct permutationsvoid uniquePermutations(int N){ // Stores equivalent string // representation of N string num = to_string(N); vector<char> lis(num.begin(), num.end()); vector<string> permute; sort(lis.begin(), lis.end()); do { permute.push_back(string(lis.begin(), lis.end())); } while (next_permutation(lis.begin(), lis.end())); // Print unique permutations uniquePermutationsUtil(permute);}// Driver Codeint main(){ // Given value of N int N = 7668; // Function call to find all distinct permutations of N uniquePermutations(N); return 0;}// This code is contributed by phasing17 |
Python3
# Python3 program for the above approachfrom itertools import permutations# Utility function to print# all distinct permutationsdef uniquePermutationsUtil(permute): p = [] # Traverse the list permute[] for i in permute: # Convert this permutation to list permutelist = list(i) # Append this list to p p.append(permutelist) # Stores unique permutations newlist = [] # Traverse list p[] for i in p: # If permutation is # not in newlist if i not in newlist: newlist.append(i) # Initialize empty list permutelist = [] # Traverse the list newlist[] for i in newlist: # Initialize empty string s = "" # Traversing in element list for j in i: # Convert each # element to string s = s + str(j) # Convert string to integer s = int(s) # Append the unique # permutation to permutelist permutelist.append(s) # Print all distinct permutations print(*permutelist) # Function to print all # distinct permutationsdef uniquePermutations(N): # Stores equivalent string # representation of N num = str(N) # Convert each character to # integer and store in the list lis = list(map(int, num)) # Built in method to store all # permutations of the list permute = permutations(lis) # Print unique permutations uniquePermutationsUtil(permute)# Driver Code# Given value of NN = 7668# Function call to find all# distinct permutations of NuniquePermutations(N) |
Javascript
// JavaScript program for the above approach// This function generates all the permutations of arrfunction permutations(arr) { var results = []; var permute = function(arr, memo) { var curr, memo = memo || []; for (var i = 0; i < arr.length; i++) { curr = arr.splice(i, 1); if (arr.length === 0) { results.push(memo.concat(curr)); } permute(arr.slice(), memo.concat(curr)); arr.splice(i, 0, curr[0]); } return results; } return permute(arr);}// Utility function to print all distinct permutationsfunction uniquePermutationsUtil(permute) { var p = []; // Traverse the list permute[] for (var i of permute) { // Convert this permutation to array var permutelist = [...i]; // Append this array to p p.push(permutelist); } // Stores unique permutations var newlist = []; // Traverse array p[] for (var i of p) { // If permutation is not in newlist if (!newlist.some(function(v) { return v.toString() === i.toString(); })) { newlist.push(i); } } // Initialize empty array var permutelist = []; // Traverse the array newlist[] for (var i of newlist) { // Initialize empty string var s = ""; // Traversing in element array for (var j of i) { // Append each element to string s += j.toString(); } // Convert string to integer s = parseInt(s); // Append the unique // permutation to permutelist permutelist.push(s); } // Print all distinct permutations console.log(...permutelist);}// Function to print all distinct permutationsfunction uniquePermutations(N) { // Stores equivalent string // representation of N var num = N.toString(); // Convert each character to integer and store in the array var lis = num.split('').map(Number); // Built in method to store all permutations of the array var permute = permutations(lis); // Print unique permutations uniquePermutationsUtil(permute);}// Driver Code// Given value of Nvar N = 7668;// Function call to find all distinct permutations of NuniquePermutations(N); |
Output:
7668 7686 7866 6768 6786 6678 6687 6876 6867 8766 8676 8667
Time Complexity: O(N * N!)
Auxiliary Space: O(N * N!)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
