Wednesday, November 20, 2024
Google search engine
HomeData Modelling & AIFind the rank of a given combination from an Array of String

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

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:

C++




#include <bits/stdc++.h>
using namespace std;
 
// Define a function to generate the
// powerset of a given list of strings
vector<string> get_powerset(vector<string> string_list)
{
 
    // Initialize the powerset with
    // the empty string
    vector<string> powerset = { "" };
 
    // Loop over all possible
    // lengths of subsets
    for (int i = 1; i <= string_list.size(); i++) {
 
        // Generate all combinations
        // of subsets of length i
        vector<bool> bitmask(i, true);
        bitmask.resize(string_list.size(), false);
 
        do {
            string subset = "";
            for (int j = 0; j < string_list.size(); j++) {
                if (bitmask[j]) {
                    subset += string_list[j];
                }
            }
 
            // Add the generated subset to the powerset
            powerset.push_back(subset);
        } while (prev_permutation(bitmask.begin(),
                                  bitmask.end()));
    }
 
    // Return the final powerset
    return powerset;
}
 
// Define a function to get the rank
// of a given string in the powerset
// of a list of strings
int get_rank(vector<string> string_list, string k)
{
 
    // Generate the powerset of
    // the input string list
    vector<string> powerset = get_powerset(string_list);
 
    // If the target string is not
    // in the powerset, return -1
    if (find(powerset.begin(), powerset.end(), k)
        == powerset.end()) {
        return -1;
    }
 
    // Otherwise, return the index of
    // the target string in the
    // sorted powerset, plus 1
    return distance(powerset.begin(),
                    lower_bound(powerset.begin(),
                                powerset.end(), k))
           + 1;
}
 
int main()
{
    vector<string> string_list = { "ab", "pq", "nm" };
    string k = "pqnm";
 
    // Get the rank of the target string
    // in the powerset of the
    // input string list
    int rank = get_rank(string_list, k);
 
    // Print the rank
    cout << rank << endl;
 
    return 0;
}


Java




// Java code for the approach
 
import java.util.*;
 
public class GFG {
      // Define a function to generate the
    // powerset of a given list of strings
    public static List<String> get_powerset(List<String> string_list) {
          // Initialize the powerset with
        // the empty string
        List<String> powerset = new ArrayList<>();
        powerset.add("");
           
          // Loop over all possible
        // lengths of subsets
        for (int i = 1; i <= string_list.size(); i++) {
            for (List<String> combination : combinations(string_list, i)) {
                String subset = String.join("", combination);
                powerset.add(subset);
            }
        }
       
          // Return the final powerset
        return powerset;
    }
     
      // Define a function to get the rank
    // of a given string in the powerset
    // of a list of strings
    public static int get_rank(List<String> string_list, String k) {
          // Generate the powerset of
        // the input string list
        List<String> powerset = get_powerset(string_list);
           
          // If the target string is not
        // in the powerset, return -1
        if (!powerset.contains(k)) {
            return -1;
        }
       
          // Otherwise, return the index of
        // the target string in the
        // sorted powerset, plus 1
        return powerset.indexOf(k) + 1;
    }
 
    public static <T> Iterable<List<T>> combinations(List<T> items, int n) {
        if (n == 0) {
            return Collections.singletonList(Collections.emptyList());
        } else {
            List<List<T>> result = new ArrayList<>();
            for (int i = 0; i <= items.size() - n; i++) {
                T item = items.get(i);
                for (List<T> combination : combinations(items.subList(i+1, items.size()), n-1)) {
                    List<T> list = new ArrayList<>();
                    list.add(item);
                    list.addAll(combination);
                    result.add(list);
                }
            }
            return result;
        }
    }
 
    public static void main(String[] args) {
        List<String> string_list = Arrays.asList("ab", "pq", "nm");
        String k = "pqnm";
           
        // Get the rank of the target string
        // in the powerset of the
        // input string list
        int rank = get_rank(string_list, k);
       
        System.out.println(rank); // Output: 7
    }
}


Python




# Import the combinations function
# from the itertools module
from itertools import combinations
 
# Define a function to generate the
# powerset of a given list of strings
 
 
def get_powerset(string_list):
 
    # Initialize the powerset with
    # the empty string
    powerset = ['']
 
    # Loop over all possible
    # lengths of subsets
    for i in range(1, len(string_list)+1):
 
        # Generate all combinations
        # of subsets of length i
        for combination in combinations(string_list, i):
 
            # Join the elements of each
            # combination into a single string
            powerset.append(''.join(combination))
 
    # Return the final powerset
    return powerset
 
# Define a function to get the rank
# of a given string in the powerset
# of a list of strings
 
 
def get_rank(string_list, k):
 
    # Generate the powerset of
    # the input string list
    powerset = get_powerset(string_list)
    # If the target string is not
    # in the powerset, return -1
    if k not in powerset:
        return -1
    # Otherwise, return the index of
    # the target string in the
    # sorted powerset, plus 1
    return powerset.index(k) + 1
 
 
# Define a list of strings
# and a target string
string_list = ['ab', 'pq', 'nm']
k = 'pqnm'
 
# Get the rank of the target string
# in the powerset of the
# input string list
rank = get_rank(string_list, k)
 
# Print the rank
print(rank)


C#




// C# code for the approach
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG
{
 
  // Define a function to generate the
  // powerset of a given list of strings
  public static List<string>
    get_powerset(List<string> string_list)
  {
 
    // Initialize the powerset with
    // the empty string
    List<string> powerset = new List<string>();
    powerset.Add("");
 
    // Loop over all possible
    // lengths of subsets
    for (int i = 1; i <= string_list.Count; i++) {
      foreach(List<string> combination in
              combinations(string_list, i))
      {
        string subset
          = string.Join("", combination);
        powerset.Add(subset);
      }
    }
 
    // Return the final powerset
    return powerset;
  }
 
  // Define a function to get the rank
  // of a given string in the powerset
  // of a list of strings
  public static int get_rank(List<string> string_list,
                             string k)
  {
 
    // Generate the powerset of
    // the input string list
    List<string> powerset = get_powerset(string_list);
 
    // If the target string is not
    // in the powerset, return -1
    if (!powerset.Contains(k)) {
      return -1;
    }
 
    // Otherwise, return the index of
    // the target string in the
    // sorted powerset, plus 1
    return powerset.IndexOf(k) + 1;
  }
 
  public static IEnumerable<IEnumerable<T> >
    combinations<T>(IEnumerable<T> items, int n)
  {
    if (n == 0) {
      return new[] { Enumerable.Empty<T>() };
    }
    else {
      List<List<T> > result = new List<List<T> >();
      for (int i = 0; i <= items.Count() - n; i++) {
        T item = items.ElementAt(i);
        foreach(IEnumerable<T> combination in
                combinations(items.Skip(i + 1),
                             n - 1))
        {
          List<T> list = new List<T>();
          list.Add(item);
          list.AddRange(combination);
          result.Add(list);
        }
      }
      return result;
    }
  }
 
  public static void Main()
  {
    List<string> string_list
      = new List<string>() { "ab", "pq", "nm" };
    string k = "pqnm";
 
    // Get the rank of the target string
    // in the powerset of the
    // input string list
    int rank = get_rank(string_list, k);
 
    Console.WriteLine(rank); // Output: 7
  }
}
 
// This code is contributed by user_dtewbxkn77n


Javascript




// Define a function to generate the
// powerset of a given list of strings
function getPowerset(stringList) {
  // Initialize the powerset with
  //the empty string
  let powerset = [""];
 
  // Loop over all possible
  //lengths of subsets
  for (let i = 1; i <= stringList.length; i++) {
    // Generate all combinations
    // of subsets of length i
    let bitmask = new Array(i).fill(true);
    bitmask = bitmask.concat(new Array(stringList.length - i).fill(false));
 
    do {
      let subset = "";
      for (let j = 0; j < stringList.length; j++) {
        if (bitmask[j]) {
          subset += stringList[j];
        }
      }
 
      // Add the generated subset to the powerset
      powerset.push(subset);
    } while (prevPermutation(bitmask));
  }
 
  // Return the final powerset
  return powerset;
}
 
// Helper function to generate
// the previous permutation
function prevPermutation(array) {
  let i = array.length - 1;
  while (i > 0 && array[i - 1] <= array[i]) {
    i--;
  }
  if (i <= 0) {
    return false;
  }
 
  let j = array.length - 1;
  while (array[j] >= array[i - 1]) {
    j--;
  }
 
  let temp = array[i - 1];
  array[i - 1] = array[j];
  array[j] = temp;
 
  j = array.length - 1;
  while (i < j) {
    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    i++;
    j--;
  }
 
  return true;
}
 
// Define a function to get the rank
// of a given string in the powerset
// of a list of strings
function getRank(stringList, k) {
  // Generate the powerset of
  // the input string list
  let powerset = getPowerset(stringList);
 
  // If the target string is not
  // in the powerset, return -1
  if (!powerset.includes(k)) {
    return -1;
  }
 
  // Otherwise, return the index of
  // the target string in the
  // sorted powerset, plus 1
  return powerset.indexOf(k) + 1;
}
 
// Main
let stringList = ["ab", "pq", "nm"];
let k = "pqnm";
 
// Get the rank of the target string
// in the powerset of the
// input string list
let rank = getRank(stringList, k);
 
// Print the rank
console.log(rank);


Output

7


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

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!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
07 Jul, 2023
Like Article
Save Article


Previous

<!–

8 Min Read | Java

–>


Next


<!–

8 Min Read | Java

–>

Share your thoughts in the comments

RELATED ARTICLES

Most Popular

Recent Comments