Unique Permutations Using Sets [Complete Guide]

Filed Under: C++
Unique Permutations Using Sets

In this article, we will learn to find all the unique permutations using sets. There are N factorial unique permutations for a sequence of length N, given that all the digits are distinct. If repeating entries are present in the sequence, the total number of permutations becomes factorial(N)/(factorial(a1) x factorial(a2) x .... x factorial(am)).We will find all the permutations using the set data structure. So without wasting any time, let’s quickly jump to the problem statement.

Problem Statement

Given a string of finite length, determine all the unique permutations of the string. The string can have repeating characters as well. Print these permutations in a lexicographically sorted order.

Example 2
Example

What is a Set Data Structure?

The set data structure is very unique in itself, the two most important properties of a set data structure are

  1. It stores only unique elements.(Multiset is an entirely different case)
  2. It stores the elements in a lexicographically order

Set is very efficient in the CRUD operations. Most of the operations like insertions, searching, and deletion are of logarithmic time complexity i.e. O(log2N). Below is a brief explanation of each of these functions.

Note: Update operations are not allowed for sets. Thus, if you want to update the value of any element, first you have to remove the old value from the set and then insert the new value into the set.

  • insert(): First it checks if the element is already present in the set or not, then if the check returns true, it inserts the element else skip it.
  • erase(): Similar to the insert function, first it search for the element in the set, then if the search is success it removes the element from the set.

Note: Set is an associative container, unlike arrays and vectors, a set doesn’t provide random access. This is because the set elements are not stored in a contiguous memory location. Thus, to access the elements of a set, you need to use the respective iterators.

Creating Unique Permutations Using Sets

Alright enough of sets, let’s now move to the concept that we will use to solve this problem.

  • Our function will take a string as the input, it can either be a numerical string or an alphabetical string.
  • The total number of unique permutations possible for a string of length N is
    • factorial(N): If all the characters are unique.
    • factorial(N)/(factorial(a1) x factorial(a2) x factorial(a3) x .... x factorial(am)): If ‘m’ characters are repeating.
  • Now we will use an inbuilt function to generate the next permutation of the string.
    • next_permutation(s, s + s.length());
    • This function will return true if the next lexicographically greater permutation is possible.
    • Otherwise, it will return false.
  • We will keep on permuting as long as it returns true, i.e. until we get all the permutations.
  • Then we will insert each permutation into the set, so that only unique values are present.

That’s all about the procedure that we will follow, let’s work out the code using C++.

Unique Permutations Using Sets C++ Program

Let’s now create unique permutations using sets in C++. This program puts into use the steps that we’ve outlined earlier. Let’s get started!

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

// function to evaluate the permutations
void unique_permutations(set <string> &s, string str)
{
	// insert current string into the set
	s.insert(str);

	// now start the while loop
	while(next_permutation(str.begin(), str.end()))
		// insert this permutation into
		// the set
		s.insert(str);

	// return from the function once the
	// while loop in over
	return;
}

void print_set(set <string> s)
{
	cout << "The set is:" << endl;
	for(string ele : s)
		cout << ele << endl;
	cout << endl;
}

int main()
{
	// initialize the set
	set <string> s;

	// take the input
	cout << "Enter a string" << endl;
	string str;
	cin >> str;

	// call the function
	unique_permutations(s, str);

	// print the set
	print_set(s);
}
Algorithm Code 1
Algorithm Code

Output

Unique Permutations Output
Unique Permutations Output

Conclusion

In this tutorial, we learned the concept of unique permutations using sets. Initially, we looked at the problem statement, then we learned some properties of sets. In the end, we looked at the approach and wrote a C++ program to demonstrate the algorithm. That’s all for today, thanks for reading.

Futher Readings

To learn more about data structures, you can refer to the following websites.

https://www.journaldev.com/56360/vector-class-in-cpp

https://www.journaldev.com/56477/stack-class-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content