Given a list of permutations of any word. Find the missing permutation from the list of permutations.
Examples:
Input : Permutation_given[] = {"ABCD", "CABD", "ACDB",
"DACB", "BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA", "CBAD",
"ABDC", "ADBC", "BDCA", "DCBA", "BACD",
"BADC", "BDAC", "CBDA", "DCAB"};
Output : DBAC DBCA
Approach:
- We create a set of all given strings.
- And one more set of all permutations.
- Finally return difference between the two sets.
Implementation:
CPP
#include <bits/stdc++.h>using namespace std;void find_missing_strings(string Permutation_given[], size_t Size_Permutation_given){ // vector "permutation" containing all // the permutation of input string vector<string> permutations; // Here we can take any string // from the given list and do // the necessary permutation string input = Permutation_given[0]; permutations.push_back(input); // In the loop we will store // all the permutations of the string // in the vector "permutation". while (true) { string p = permutations.back(); // Getting next permutation of input string next_permutation(p.begin(), p.end()); if (p == permutations.front()) break; permutations.push_back(p); } // vector containing all the // missing strings in permutation vector<string> missing; // given_permutations contains the // permutation of the input string set<string> given_permutations( Permutation_given, Permutation_given + Size_Permutation_given); // Through the set difference we will get // the missing words in vector missing set_difference(permutations.begin(), permutations.end(), given_permutations.begin(), given_permutations.end(), back_inserter(missing)); // printing all the missing string for (auto i = missing.begin(); i != missing.end(); ++i) cout << *i << endl;}// Driver codeint main(){ string Permutation_given[] = { "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB" }; // size of permutation list size_t Size_Permutation_given = sizeof(Permutation_given) / sizeof(*Permutation_given); find_missing_strings(Permutation_given, Size_Permutation_given); return 0;} |
Java
import java.util.Arrays;import java.util.HashSet;import java.util.Set;public class MissingStrings { public static void findMissingStrings(String[] permutationGiven) { // set containing all the permutations of the input // string Set<String> permutations = new HashSet<String>(); char[] chars = permutationGiven[0].toCharArray(); Arrays.sort(chars); permutation(permutations, chars, 0, chars.length - 1); // set containing the permutation of the input // strings Set<String> givenPermutations = new HashSet<String>( Arrays.asList(permutationGiven)); // set difference to get the missing strings Set<String> missing = new HashSet<String>(permutations); missing.removeAll(givenPermutations); // printing all the missing strings for (String s : missing) { System.out.println(s); } } // recursive function to find permutations of a string public static void permutation(Set<String> permutations, char[] chars, int l, int r) { if (l == r) { permutations.add(new String(chars)); } else { for (int i = l; i <= r; i++) { swap(chars, l, i); permutation(permutations, chars, l + 1, r); swap(chars, l, i); } } } // function to swap two characters of a char array public static void swap(char[] chars, int i, int j) { char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; } // Driver code public static void main(String[] args) { String[] permutationGiven = { "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB" }; findMissingStrings(permutationGiven); }} |
Python3
import itertoolsdef find_missing_strings(permutation_given): # set containing all the permutations of the input string permutations = set([''.join(p) for p in itertools.permutations(permutation_given[0])]) # set containing the permutation of the input strings given_permutations = set(permutation_given) # set difference to get the missing strings missing = permutations - given_permutations # printing all the missing strings for s in missing: print(s)# Driver codeif __name__ == '__main__': permutation_given = [ "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB" ] find_missing_strings(permutation_given) |
C#
using System;using System.Collections.Generic;using System.Linq;class MissingStrings { public static void FindMissingStrings(string[] permutationGiven) { // set containing all the permutations of the input // string HashSet<string> permutations = new HashSet<string>(); char[] chars = permutationGiven[0].ToCharArray(); Array.Sort(chars); Permutation(permutations, chars, 0, chars.Length - 1); // set containing the permutation of the input // strings HashSet<string> givenPermutations = new HashSet<string>(permutationGiven); // set difference to get the missing strings HashSet<string> missing = new HashSet<string>(permutations); missing.ExceptWith(givenPermutations); // printing all the missing strings foreach(string s in missing) { Console.WriteLine(s); } } // recursive function to find permutations of a string public static void Permutation(HashSet<string> permutations, char[] chars, int l, int r) { if (l == r) { permutations.Add(new string(chars)); } else { for (int i = l; i <= r; i++) { Swap(chars, l, i); Permutation(permutations, chars, l + 1, r); Swap(chars, l, i); } } } // function to swap two characters of a char array public static void Swap(char[] chars, int i, int j) { char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; } // Driver code public static void Main(string[] args) { string[] permutationGiven = { "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB" }; FindMissingStrings(permutationGiven); }} |
Javascript
function findMissingStrings(PermutationGiven) { // Array "permutations" containing all the permutations of input string let permutations = []; // Here we can take any string from the given list and do the necessary permutation let input = PermutationGiven[0]; permutations.push(input); // In the loop, we will store all the permutations of the string in the array "permutations" while (true) { let p = permutations[permutations.length - 1]; // Getting the next permutation of the input string p = p.split(''); let nextPerm = getNextPermutation(p); if (nextPerm.join('') === permutations[0]) break; permutations.push(nextPerm.join('')); } // Array containing all the missing strings in permutations let missing = []; // Convert PermutationGiven to a Set let givenPermutations = new Set(PermutationGiven); // Find the missing words by performing set difference for (let i = 0; i < permutations.length; i++) { if (!givenPermutations.has(permutations[i])) { missing.push(permutations[i]); } } // Printing all the missing strings for (let i = 0; i < missing.length; i++) { console.log(missing[i]); }}// Function to get the next permutation of a stringfunction getNextPermutation(arr) { let i = arr.length - 2; while (i >= 0 && arr[i] >= arr[i + 1]) { i--; } if (i === -1) { return arr.reverse(); } let j = arr.length - 1; while (arr[j] <= arr[i]) { j--; } swap(arr, i, j); let left = i + 1; let right = arr.length - 1; while (left < right) { swap(arr, left, right); left++; right--; } return arr;}// Function to swap two elements in an arrayfunction swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}// Driver codeconst PermutationGiven = [ "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB"];findMissingStrings(PermutationGiven); |
Output
DBAC DBCA
Time Complexity: O(n!) where n is the length of the first string in the input
Auxiliary Space: O(n!), because we need to store all possible permutations of the input string in memory
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!
