برنامه محاسبه رتبه الفبایی یک رشته — راهنمای کاربردی

در این مطلب، روش محاسبه رتبه الفبایی یک رشته (Lexicographic Rank of a String) آموزش داده شده است. فرض می‌شود که یک رشته داده شده است. هدف پیدا کردن امتیاز رشته در میان همه جایگشت‌های آن است که به صورت الفبایی مرتب شده‌اند. برای مثال، امتیاز رشته «abc» برابر با ۱، «acb» برابر با ۲ و «cba» برابر با ۶ است. مثال زیر در این راستا قابل توجه است.

Input : str[] = "acb"
Output : Rank = 2

Input : str[] = "string"
Output : Rank = 598

Input : str[] = "cba"
Output : Rank = 6

برای ساده‌تر شدن مسأله، فرض می‌شود که رشته هیچ کاراکتر تکراری ندارد. یک راهکار ساده مقداردهی اولیه به امتیاز است. در ابتدا، مقدار ۱ به امتیاز (Rank) داده می‌شود. سپس، همه جایگشت‌ها به ترتیب الفبایی تولید می‌شوند. پس از تولید جایگشت‌ها، اگر جایگشت تولید شده مشابه با رشته داده شده باشد، امتیاز بازگردانده می‌شود. در غیر این صورت، امتیاز، یکی افزایش پیدا می‌کند.

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

پیچیدگی زمانی این روش در بدترین حالت از درجه نمایی است. در ادامه، راهکار کارآمد برای حل این مساله بیان شده است. فرض می‌شود که رشته داده شده «STRING» است. در رشته ورودی، «S» اولین کاراکتر است. به طور کلی، ۶ کاراکتر در رشته وجود دارد و ۴ تای آن‌ها کوچک‌تر از S هستند. بنابراین، این امکان وجود دارد که !۵*۴ رشته کوچک‌تر وجود داشته باشد که در آن‌ها، اولین کاراکتر کوچک‌تر از S کوچک‌تر است. مثال‌هایی از این مورد، در ادامه آمده‌اند.

R X X X X X
I X X X X X
N X X X X X
G X X X X X

اکنون، S ثابت نگه داشته می‌شود و کوچک‌ترین رشته‌ها با شروع از S پیدا می‌شوند. فرایند مشابهی برای T انجام می‌شود. امتیاز این بار برابر با $$4*5! + 4*4! +…$$ است. اکنون T ثابت می‌شود و فرایند مشابهی برای R انجام می‌شود. امتیاز برابر با $$4*5! + 4*4! + 3*3! +…$$ است. پس از این گام، R ثابت می‌شود و فرایند برای I تکرار خواهد شد. امتیاز برابر با $$4*5! + 4*4! + 3*3! + 1*2! +…$$ است.

اکنون، I ثابت و فرایند برای N تکرار می‌شود. امتیاز برابر با $$4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…$$ است. در این مرحله، N ثابت و فرایند مشابهی برای G انجام می‌شود. امتیاز برابر با $$4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0!$$ است.

فیلم آموزش برنامه نویسی پایتون + مثال های عملی در Python در فرادرس

کلیک کنید

امتیاز کامل برابر با $$4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597$$ است. باید توجه داشت که محاسبات بالا، تعداد رشته‌های کوچک‌تر را پیدا می‌کند. بنابراین، امتیاز رشته داده شده برابر با تعداد رشته‌های کوچک‌تر به علاوه ۱ است. امتیاز نهایی برابر با $$1 + 597 = 598$$ است.

در ادامه، پیاده‌سازی رویکرد بالا در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

کد محاسبه رتبه الفبایی یک رشته در C++‎

// C++ program to find lexicographic rank 
// of a string 
#include <bits/stdc++.h> 
#include <string.h> 
  
using namespace std; 
// A utility function to find factorial of n 
int fact(int n) 
{ 
    return (n <= 1) ? 1 : n * fact(n - 1); 
} 
  
// A utility function to count smaller characters on right 
// of arr[low] 
int findSmallerInRight(char* str, int low, int high) 
{ 
    int countRight = 0, i; 
  
    for (i = low + 1; i <= high; ++i) 
        if (str[i] < str[low]) 
            ++countRight; 
  
    return countRight; 
} 
  
// A function to find rank of a string in all permutations 
// of characters 
int findRank(char* str) 
{ 
    int len = strlen(str); 
    int mul = fact(len); 
    int rank = 1; 
    int countRight; 
  
    int i; 
    for (i = 0; i < len; ++i) { 
        mul /= len - i; 
  
        // count number of chars smaller than str[i] 
        // fron str[i+1] to str[len-1] 
        countRight = findSmallerInRight(str, i, len - 1); 
  
        rank += countRight * mul; 
    } 
  
    return rank; 
} 
  
// Driver program to test above function 
int main() 
{ 
    char str[] = "string"; 
    cout << findRank(str); 
    return 0; 
} 
  
// This code is contributed 
// by Akanksha Rai

کد محاسبه رتبه الفبایی یک رشته در C

// C program to find lexicographic rank 
// of a string 
#include <stdio.h> 
#include <string.h> 
  
// A utility function to find factorial of n 
int fact(int n) 
{ 
    return (n <= 1) ? 1 : n * fact(n - 1); 
} 
  
// A utility function to count smaller characters on right 
// of arr[low] 
int findSmallerInRight(char* str, int low, int high) 
{ 
    int countRight = 0, i; 
  
    for (i = low + 1; i <= high; ++i) 
        if (str[i] < str[low]) 
            ++countRight; 
  
    return countRight; 
} 
  
// A function to find rank of a string in all permutations 
// of characters 
int findRank(char* str) 
{ 
    int len = strlen(str); 
    int mul = fact(len); 
    int rank = 1; 
    int countRight; 
  
    int i; 
    for (i = 0; i < len; ++i) { 
        mul /= len - i; 
  
        // count number of chars smaller than str[i] 
        // fron str[i+1] to str[len-1] 
        countRight = findSmallerInRight(str, i, len - 1); 
  
        rank += countRight * mul; 
    } 
  
    return rank; 
} 
  
// Driver program to test above function 
int main() 
{ 
    char str[] = "string"; 
    printf("%d", findRank(str)); 
    return 0; 
} 

کد محاسبه رتبه الفبایی یک رشته در جاوا

// Java program to find lexicographic rank 
// of a string 
import java.io.*; 
import java.util.*; 
  
class GFG { 
  
    // A utility function to find factorial of n 
    static int fact(int n) 
    { 
        return (n <= 1) ? 1 : n * fact(n - 1); 
    } 
  
    // A utility function to count smaller 
    // characters on right of arr[low] 
    static int findSmallerInRight(String str, int low, 
                                  int high) 
    { 
        int countRight = 0, i; 
  
        for (i = low + 1; i <= high; ++i) 
            if (str.charAt(i) < str.charAt(low)) 
                ++countRight; 
  
        return countRight; 
    } 
  
    // A function to find rank of a string in 
    // all permutations of characters 
    static int findRank(String str) 
    { 
        int len = str.length(); 
        int mul = fact(len); 
        int rank = 1; 
        int countRight; 
  
        for (int i = 0; i < len; ++i) { 
            mul /= len - i; 
  
            // count number of chars smaller 
            // than str[i] from str[i+1] to 
            // str[len-1] 
            countRight = findSmallerInRight(str, i, len - 1); 
  
            rank += countRight * mul; 
        } 
  
        return rank; 
    } 
  
    // Driver program to test above function 
    public static void main(String[] args) 
    { 
        String str = "string"; 
        System.out.println(findRank(str)); 
    } 
} 
  
// This code is contributed by Nikita Tiwari. 

کد محاسبه رتبه الفبایی یک رشته در پایتون

# Python program to find lexicographic  
# rank of a string 
  
# A utility function to find factorial 
# of n 
def fact(n) : 
    f = 1
    while n >= 1 : 
        f = f * n 
        n = n - 1
    return f 
      
# A utility function to count smaller  
# characters on right of arr[low] 
def findSmallerInRight(st, low, high) : 
      
    countRight = 0
    i = low + 1
    while i <= high : 
        if st[i] < st[low] : 
            countRight = countRight + 1
        i = i + 1
   
    return countRight 
      
# A function to find rank of a string 
# in all permutations of characters 
def findRank (st) : 
    ln = len(st) 
    mul = fact(ln) 
    rank = 1
    i = 0 
   
    while i < ln : 
          
        mul = mul / (ln - i) 
          
        # count number of chars smaller  
        # than str[i] fron str[i + 1] to 
        # str[len-1] 
        countRight = findSmallerInRight(st, i, ln-1) 
   
        rank = rank + countRight * mul 
        i = i + 1
          
    return rank 
      
      
# Driver program to test above function 
st = "string"
print (findRank(st)) 
  
# This code is contributed by Nikita Tiwari. 

کد محاسبه رتبه الفبایی یک رشته در #C

// C# program to find lexicographic rank 
// of a string 
using System; 
  
class GFG { 
  
    // A utility function to find factorial of n 
    static int fact(int n) 
    { 
        return (n <= 1) ? 1 : n * fact(n - 1); 
    } 
  
    // A utility function to count smaller 
    // characters on right of arr[low] 
    static int findSmallerInRight(string str, 
                                  int low, int high) 
    { 
        int countRight = 0, i; 
  
        for (i = low + 1; i <= high; ++i) 
            if (str[i] < str[low]) 
                ++countRight; 
  
        return countRight; 
    } 
  
    // A function to find rank of a string in 
    // all permutations of characters 
    static int findRank(string str) 
    { 
        int len = str.Length; 
        int mul = fact(len); 
        int rank = 1; 
        int countRight; 
  
        for (int i = 0; i < len; ++i) { 
            mul /= len - i; 
  
            // count number of chars smaller 
            // than str[i] from str[i+1] to 
            // str[len-1] 
            countRight = findSmallerInRight(str, 
                                            i, len - 1); 
  
            rank += countRight * mul; 
        } 
  
        return rank; 
    } 
  
    // Driver program to test above function 
    public static void Main() 
    { 
        string str = "string"; 
        Console.Write(findRank(str)); 
    } 
} 
  
// This code is contributed nitin mittal. 

کد محاسبه رتبه الفبایی یک رشته در PHP

<?php  
// A utility function to find factorial of n 
function fact($n) 
{ 
    return ($n <= 1) ? 1 :$n * fact($n - 1); 
} 
  
// A utility function to count smaller  
// characters on right of arr[low] 
function findSmallerInRight($str, $low, $high) 
{ 
    $countRight = 0; 
  
    for ($i = $low + 1; $i <= $high; ++$i) 
        if ($str[$i] < $str[$low]) 
            ++$countRight; 
  
    return $countRight; 
} 
  
// A function to find rank of a string  
// in all permutations of characters 
function findRank ($str) 
{ 
    $len = strlen($str); 
    $mul = fact($len); 
    $rank = 1; 
  
    for ($i = 0; $i < $len; ++$i) 
    { 
        $mul /= $len - $i; 
  
        // count number of chars smaller than  
        // str[i] fron str[i+1] to str[len-1] 
        $countRight = findSmallerInRight($str, $i,  
                                         $len - 1); 
  
        $rank += $countRight * $mul ; 
    } 
  
    return $rank; 
} 
  
// Driver Code 
$str = "string"; 
echo findRank($str); 
  
// This code is contributed by ChitraNayal 
?> 

خروجی قطعه کدهای بالا به صورت زیر است.

598

پیچیدگی زمانی راهکار بالا از درجه O(n²)‎ است. می‌توان پیچیدگی زمانی را با ساخت یک آرایه کمکی با سایز ۲۵۶ به O(n)‎ کاهش داد. قطعه کدهای زیر، با استفاده از این فضای کمکی پیاده‌سازی شده‌اند.

فیلم آموزش رشته و متن در برنامه نویسی پایتون (رایگان) در فرادرس

کلیک کنید

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در C++‎

// A O(n) solution for finding rank of string 
#include <bits/stdc++.h> 
using namespace std; 
#define MAX_CHAR 256 
  
// A utility function to find factorial of n 
int fact(int n) 
{ 
    return (n <= 1) ? 1 : n * fact(n - 1); 
} 
  
// Construct a count array where value at every index 
// contains count of smaller characters in whole string 
void populateAndIncreaseCount(int* count, char* str) 
{ 
    int i; 
  
    for (i = 0; str[i]; ++i) 
        ++count[str[i]]; 
  
    for (i = 1; i < MAX_CHAR; ++i) 
        count[i] += count[i - 1]; 
} 
  
// Removes a character ch from count[] array 
// constructed by populateAndIncreaseCount() 
void updatecount(int* count, char ch) 
{ 
    int i; 
    for (i = ch; i < MAX_CHAR; ++i) 
        --count[i]; 
} 
  
// A function to find rank of a string in all permutations 
// of characters 
int findRank(char* str) 
{ 
    int len = strlen(str); 
    int mul = fact(len); 
    int rank = 1, i; 
  
    // all elements of count[] are initialized with 0 
    int count[MAX_CHAR] = { 0 }; 
  
    // Populate the count array such that count[i] 
    // contains count of characters which are present 
    // in str and are smaller than i 
    populateAndIncreaseCount(count, str); 
  
    for (i = 0; i < len; ++i) { 
        mul /= len - i; 
  
        // count number of chars smaller than str[i] 
        // fron str[i+1] to str[len-1] 
        rank += count[str[i] - 1] * mul; 
  
        // Reduce count of characters greater than str[i] 
        updatecount(count, str[i]); 
    } 
  
    return rank; 
} 
  
// Driver program to test above function 
int main() 
{ 
    char str[] = "string"; 
    cout << findRank(str); 
    return 0; 
} 
  
// This is code is contributed by rathbhupendra 

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در C

// A O(n) solution for finding rank of string 
#include <stdio.h> 
#include <string.h> 
#define MAX_CHAR 256 
  
// A utility function to find factorial of n 
int fact(int n) 
{ 
    return (n <= 1) ? 1 : n * fact(n - 1); 
} 
  
// Construct a count array where value at every index 
// contains count of smaller characters in whole string 
void populateAndIncreaseCount(int* count, char* str) 
{ 
    int i; 
  
    for (i = 0; str[i]; ++i) 
        ++count[str[i]]; 
  
    for (i = 1; i < MAX_CHAR; ++i) 
        count[i] += count[i - 1]; 
} 
  
// Removes a character ch from count[] array 
// constructed by populateAndIncreaseCount() 
void updatecount(int* count, char ch) 
{ 
    int i; 
    for (i = ch; i < MAX_CHAR; ++i) 
        --count[i]; 
} 
  
// A function to find rank of a string in all permutations 
// of characters 
int findRank(char* str) 
{ 
    int len = strlen(str); 
    int mul = fact(len); 
    int rank = 1, i; 
  
    // all elements of count[] are initialized with 0 
    int count[MAX_CHAR] = { 0 }; 
  
    // Populate the count array such that count[i] 
    // contains count of characters which are present 
    // in str and are smaller than i 
    populateAndIncreaseCount(count, str); 
  
    for (i = 0; i < len; ++i) { 
        mul /= len - i; 
  
        // count number of chars smaller than str[i] 
        // fron str[i+1] to str[len-1] 
        rank += count[str[i] - 1] * mul; 
  
        // Reduce count of characters greater than str[i] 
        updatecount(count, str[i]); 
    } 
  
    return rank; 
} 
  
// Driver program to test above function 
int main() 
{ 
    char str[] = "string"; 
    printf("%d", findRank(str)); 
    return 0; 
}

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در جاوا

// A O(n) solution for finding rank of string 
  
class GFG { 
  
    static int MAX_CHAR = 256; 
  
    // A utility function to find factorial of n 
    static int fact(int n) 
    { 
        return (n <= 1) ? 1 : n * fact(n - 1); 
    } 
  
    // Construct a count array where value at every index 
    // contains count of smaller characters in whole string 
    static void populateAndIncreaseCount(int[] count, char[] str) 
    { 
        int i; 
  
        for (i = 0; i < str.length; ++i) 
            ++count[str[i]]; 
  
        for (i = 1; i < MAX_CHAR; ++i) 
            count[i] += count[i - 1]; 
    } 
  
    // Removes a character ch from count[] array 
    // constructed by populateAndIncreaseCount() 
    static void updatecount(int[] count, char ch) 
    { 
        int i; 
        for (i = ch; i < MAX_CHAR; ++i) 
            --count[i]; 
    } 
  
    // A function to find rank of a string in all permutations 
    // of characters 
    static int findRank(char[] str) 
    { 
        int len = str.length; 
        int mul = fact(len); 
        int rank = 1, i; 
  
        // all elements of count[] are initialized with 0 
        int count[] = new int[MAX_CHAR]; 
  
        // Populate the count array such that count[i] 
        // contains count of characters which are present 
        // in str and are smaller than i 
        populateAndIncreaseCount(count, str); 
  
        for (i = 0; i < len; ++i) { 
            mul /= len - i; 
  
            // count number of chars smaller than str[i] 
            // fron str[i+1] to str[len-1] 
            rank += count[str[i] - 1] * mul; 
  
            // Reduce count of characters greater than str[i] 
            updatecount(count, str[i]); 
        } 
  
        return rank; 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        char str[] = "string".toCharArray(); 
        System.out.println(findRank(str)); 
    } 
} 
  
// This code has been contributed by 29AjayKumar

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در پایتون ۳

# A O(n) solution for finding rank of string 
MAX_CHAR=256; 
  
# all elements of count[] are initialized with 0 
count=[0]*(MAX_CHAR + 1); 
  
# A utility function to find factorial of n 
def fact(n): 
    return 1 if(n <= 1) else (n * fact(n - 1)); 
  
# Construct a count array where value at every index 
# contains count of smaller characters in whole string 
def populateAndIncreaseCount(str): 
    for i in range(len(str)): 
        count[ord(str[i])]+=1; 
  
    for i in range(1,MAX_CHAR): 
        count[i] += count[i - 1]; 
  
# Removes a character ch from count[] array 
# constructed by populateAndIncreaseCount() 
def updatecount(ch): 
  
    for i in range(ord(ch),MAX_CHAR): 
        count[i]-=1; 
  
# A function to find rank of a string in all permutations 
# of characters 
def findRank(str): 
    len1 = len(str); 
    mul = fact(len1); 
    rank = 1; 
  
  
    # Populate the count array such that count[i] 
    # contains count of characters which are present 
    # in str and are smaller than i 
    populateAndIncreaseCount(str); 
  
    for i in range(len1): 
        mul = mul//(len1 - i); 
  
        # count number of chars smaller than str[i] 
        # fron str[i+1] to str[len-1] 
        rank += count[ord(str[i]) - 1] * mul; 
  
        # Reduce count of characters greater than str[i] 
        updatecount(str[i]); 
  
    return rank; 
  
# Driver code 
str = "string"; 
print(findRank(str)); 
  
# This is code is contributed by chandan_jnu 

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در C#‎

// A O(n) solution for finding rank of string 
using System; 
  
class GFG { 
  
    static int MAX_CHAR = 256; 
  
    // A utility function to find factorial of n 
    static int fact(int n) 
    { 
        return (n <= 1) ? 1 : n * fact(n - 1); 
    } 
  
    // Construct a count array where value at every index 
    // contains count of smaller characters in whole string 
    static void populateAndIncreaseCount(int[] count, char[] str) 
    { 
        int i; 
  
        for (i = 0; i < str.Length; ++i) 
            ++count[str[i]]; 
  
        for (i = 1; i < MAX_CHAR; ++i) 
            count[i] += count[i - 1]; 
    } 
  
    // Removes a character ch from count[] array 
    // constructed by populateAndIncreaseCount() 
    static void updatecount(int[] count, char ch) 
    { 
        int i; 
        for (i = ch; i < MAX_CHAR; ++i) 
            --count[i]; 
    } 
  
    // A function to find rank of a string in all permutations 
    // of characters 
    static int findRank(char[] str) 
    { 
        int len = str.Length; 
        int mul = fact(len); 
        int rank = 1, i; 
  
        // all elements of count[] are initialized with 0 
        int[] count = new int[MAX_CHAR]; 
  
        // Populate the count array such that count[i] 
        // contains count of characters which are present 
        // in str and are smaller than i 
        populateAndIncreaseCount(count, str); 
  
        for (i = 0; i < len; ++i) { 
            mul /= len - i; 
  
            // count number of chars smaller than str[i] 
            // fron str[i+1] to str[len-1] 
            rank += count[str[i] - 1] * mul; 
  
            // Reduce count of characters greater than str[i] 
            updatecount(count, str[i]); 
        } 
  
        return rank; 
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
        char[] str = "string".ToCharArray(); 
        Console.WriteLine(findRank(str)); 
    } 
} 
  
/* This code contributed by PrinciRaj1992 */

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در PHP

<?php 
// A O(n) solution for finding rank of string 
$MAX_CHAR=256; 
  
// A utility function to find factorial of n 
function fact($n) 
{ 
    return ($n <= 1) ? 1 : $n * fact($n - 1); 
} 
  
// Construct a count array where value at every index 
// contains count of smaller characters in whole string 
function populateAndIncreaseCount(&$count, $str) 
{ 
global $MAX_CHAR; 
    for ($i = 0; $i < strlen($str); ++$i) 
        ++$count[ord($str[$i])]; 
  
    for ($i = 1; $i < $MAX_CHAR; ++$i) 
        $count[$i] += $count[$i - 1]; 
} 
  
// Removes a character ch from count[] array 
// constructed by populateAndIncreaseCount() 
function updatecount(&$count, $ch) 
{ 
    global $MAX_CHAR; 
    for ($i = ord($ch); $i < $MAX_CHAR; ++$i) 
        --$count[$i]; 
} 
  
// A function to find rank of a string in all permutations 
// of characters 
function findRank($str) 
{ 
    global $MAX_CHAR; 
    $len = strlen($str); 
    $mul = fact($len); 
    $rank = 1; 
  
    // all elements of count[] are initialized with 0 
    $count=array_fill(0, $MAX_CHAR + 1, 0); 
  
    // Populate the count array such that count[i] 
    // contains count of characters which are present 
    // in str and are smaller than i 
    populateAndIncreaseCount($count, $str); 
  
    for ($i = 0; $i < $len; ++$i)  
    { 
        $mul = (int)($mul/($len - $i)); 
  
        // count number of chars smaller than str[i] 
        // fron str[i+1] to str[len-1] 
        $rank += $count[ord($str[$i]) - 1] * $mul; 
  
        // Reduce count of characters greater than str[i] 
        updatecount($count, $str[$i]); 
    } 
  
    return $rank; 
} 
  
    // Driver code 
    $str = "string"; 
    echo findRank($str); 
  
// This is code is contributed by chandan_jnu 
?> 

خروجی قطعه کدهای بالا به صورت زیر است.

598

برنامه‌های بالا برای رشته‌های حاوی کاراکتر تکراری کار نمی‌کنند. برای اینکه برنامه برای کاراکترهای تکراری نیز کار کند، باید همه کاراکترهایی که کوچک‌تر و مساوی هستند پیدا و عملیات بیان شده در بالا، در اینجا نیز انجام شود.

فیلم مجموعه آموزش برنامه نویسی پایتون (Python) در فرادرس

کلیک کنید

این بار، امتیاز محاسبه شده باید بر !p تقسیم شود. P تعداد وقوع کاراکترهای تکراری است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^