Distinct permutations of a number
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 permutations void 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 permutations void 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 Code int 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 |
Java
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; class GFG { // Utility function to print all distinct permutations static void uniquePermutationsUtil(List<String> permute) { List<String> p = new ArrayList<>(); // Traverse the list permute[] for (String i : permute) { // Convert this permutation to list p.add(i); } // Stores unique permutations List<String> newList = new ArrayList<>(); // Traverse list p[] for (String i : p) { // If permutation is not in newlist if (!newList.contains(i)) { newList.add(i); } } // Initialize empty list List<Integer> permuteList = new ArrayList<>(); // Traverse the list newList[] for (String i : newList) { // Convert string to integer int s = Integer.parseInt(i); // Append the unique permutation to permuteList permuteList.add(s); } // Print all distinct permutations for ( int i : permuteList) { System.out.print(i + " " ); } } // Function to print all distinct permutations static void uniquePermutations( int N) { // Stores equivalent string representation of N String num = Integer.toString(N); List<Character> lis = new ArrayList<>(); for ( char c : num.toCharArray()) { lis.add(c); } Collections.sort(lis); List<String> permute = new ArrayList<>(); do { char [] charArray = new char [lis.size()]; for ( int i = 0 ; i < lis.size(); i++) { charArray[i] = lis.get(i); } permute.add( new String(charArray)); } while (nextPermutation(lis)); // Print unique permutations uniquePermutationsUtil(permute); } // Function to find the next permutation static boolean nextPermutation(List<Character> array) { int i = array.size() - 1 ; while (i > 0 && array.get(i - 1 ) >= array.get(i)) { i--; } if (i <= 0 ) { return false ; } int j = array.size() - 1 ; while (array.get(j) <= array.get(i - 1 )) { j--; } // Swap the characters at positions i-1 and j char temp = array.get(i - 1 ); array.set(i - 1 , array.get(j)); array.set(j, temp); // Reverse the suffix starting at position i j = array.size() - 1 ; while (i < j) { temp = array.get(i); array.set(i, array.get(j)); array.set(j, temp); i++; j--; } return true ; } // Driver Code public static void main(String[] args) { // Given value of N int N = 7668 ; // Function call to find all distinct permutations // of N uniquePermutations(N); } } |
Python3
# Python3 program for the above approach from itertools import permutations # Utility function to print # all distinct permutations def 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 permutations def 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 N N = 7668 # Function call to find all # distinct permutations of N uniquePermutations(N) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Utility function to print all distinct permutations static void UniquePermutationsUtil(List< string > permute) { List< string > p = new List< string >(); // Traverse the list permute[] foreach ( string i in permute) { // Convert this permutation to list p.Add(i); } // Stores unique permutations List< string > newlist = new List< string >(); // Traverse list p[] foreach ( string i in p) { // If permutation is not in newlist if (!newlist.Contains(i)) { newlist.Add(i); } } // Initialize empty list List< int > permutelist = new List< int >(); // Traverse the list newlist[] foreach ( string i in newlist) { // Convert string to integer int s = int .Parse(i); // Append the unique permutation to permutelist permutelist.Add(s); } // Print all distinct permutations foreach ( int i in permutelist) { Console.Write(i + " " ); } } // Function to print all distinct permutations static void UniquePermutations( int N) { // Stores equivalent string representation of N string num = N.ToString(); List< char > lis = num.ToList(); List< string > permute = new List< string >(); lis.Sort(); do { permute.Add( new string (lis.ToArray())); } while (NextPermutation(lis)); // Print unique permutations UniquePermutationsUtil(permute); } // Function to find the next permutation static bool NextPermutation(List< char > array) { int i = array.Count - 1; while (i > 0 && array[i - 1] >= array[i]) { i--; } if (i <= 0) { return false ; } int j = array.Count - 1; while (array[j] <= array[i - 1]) { j--; } // Swap the characters at positions i-1 and j char temp = array[i - 1]; array[i - 1] = array[j]; array[j] = temp; // Reverse the suffix starting at position i j = array.Count - 1; while (i < j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } return true ; } // Driver Code static void Main() { // Given value of N int N = 7668; // Function call to find all distinct permutations of N UniquePermutations(N); } } |
Javascript
// JavaScript program for the above approach // This function generates all the permutations of arr function 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 permutations function 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 permutations function 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 N var N = 7668; // Function call to find all distinct permutations of N uniquePermutations(N); |
Output
7668 7686 7866 6768 6786 6678 6687 6876 6867 8766 8676 8667
Time Complexity: O(N * N!)
Auxiliary Space: O(N * N!)