Find the rank of a given combination from an Array of String – GeeksforGeeks

Given an array of string and a string K, the task is to find the rank of the given string if we generate all the combinations of the given array of strings.

Examples:

Input: string = [‘ab’, ‘pq’, ‘nm’], K = ‘pqnm’
Output: 7
Explanation: All combination generated are :-
”   ——————-> rank 1
‘ab’  —————–> rank 2
‘pq’  —————–> rank 3
‘nm’  —————-> rank 4
‘abpq’  ————–> rank 5
‘abnm’  ————–> rank 6
‘pqnm’  ————–> rank 7
‘abpqnm’ ————> rank 8

‘pqnm’ is at rank is generated at rank 7

Input: string = [‘a’, ‘b’], K = ‘aa’
Output: -1
Explanation: ‘aa’ cannot be generated by any combination of given element.

Approach: To solve the problem follow the below idea:

Generates the powerset of a given list of strings using the combinations function from the itertools module and a nested loop. It then calculates the rank of a target string in that powerset using the index function and returns -1 if the target string is not in the powerset. The code defines a list of strings and a target string, calls the get_rank function, and prints the rank.

Below are the steps for the above approach:

• Import the combinations function from the itertools module.
• Define a function to generate the powerset of a given list of strings.
  • Initialize the powerset with an empty string.
  • Loop over all possible lengths of subsets from 1 to the length of the input list.
  • Use the combinations function to generate all possible subsets of the current length.
  • Join the elements of each combination into a single string and append it to the powerset.
  • Return the final powerset.
• Define a function to get the rank of a given string in the powerset of a list of strings.
  • Generate the powerset of the input string list using the get_powerset function.
  • If the target string is not in the powerset, return -1.
  • Otherwise, return the index of the target string in the sorted powerset, plus 1.
• Get the rank of the target string in the powerset of the input string list using the get_rank function.
• Print the rank.

Below is the code for the above approach:

Time complexity: O(n * 2ⁿ * log(n))  to generate the power set O(2ⁿ), sorting the power set  O(n * 2ⁿ * log(n)) and finding the index O(n * 2ⁿ). 
Auxiliary space: O(2ⁿ) to store all generated combinations.