Distinct permutations of a number

0 0 4 minutes read

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

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)

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!)

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 zambiatek!