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

1// C++ program to find lexicographic rank 
2// of a string 
3#include <bits/stdc++.h> 
4#include <string.h> 
5  
6using namespace std; 
7// A utility function to find factorial of n 
8int fact(int n) 
9{ 
10    return (n <= 1) ? 1 : n * fact(n - 1); 
11} 
12  
13// A utility function to count smaller characters on right 
14// of arr[low] 
15int findSmallerInRight(char* str, int low, int high) 
16{ 
17    int countRight = 0, i; 
18  
19    for (i = low + 1; i <= high; ++i) 
20        if (str[i] < str[low]) 
21            ++countRight; 
22  
23    return countRight; 
24} 
25  
26// A function to find rank of a string in all permutations 
27// of characters 
28int findRank(char* str) 
29{ 
30    int len = strlen(str); 
31    int mul = fact(len); 
32    int rank = 1; 
33    int countRight; 
34  
35    int i; 
36    for (i = 0; i < len; ++i) { 
37        mul /= len - i; 
38  
39        // count number of chars smaller than str[i] 
40        // fron str[i+1] to str[len-1] 
41        countRight = findSmallerInRight(str, i, len - 1); 
42  
43        rank += countRight * mul; 
44    } 
45  
46    return rank; 
47} 
48  
49// Driver program to test above function 
50int main() 
51{ 
52    char str[] = "string"; 
53    cout << findRank(str); 
54    return 0; 
55} 
56  
57// This code is contributed 
58// by Akanksha Rai

1// C program to find lexicographic rank 
2// of a string 
3#include <stdio.h> 
4#include <string.h> 
5  
6// A utility function to find factorial of n 
7int fact(int n) 
8{ 
9    return (n <= 1) ? 1 : n * fact(n - 1); 
10} 
11  
12// A utility function to count smaller characters on right 
13// of arr[low] 
14int findSmallerInRight(char* str, int low, int high) 
15{ 
16    int countRight = 0, i; 
17  
18    for (i = low + 1; i <= high; ++i) 
19        if (str[i] < str[low]) 
20            ++countRight; 
21  
22    return countRight; 
23} 
24  
25// A function to find rank of a string in all permutations 
26// of characters 
27int findRank(char* str) 
28{ 
29    int len = strlen(str); 
30    int mul = fact(len); 
31    int rank = 1; 
32    int countRight; 
33  
34    int i; 
35    for (i = 0; i < len; ++i) { 
36        mul /= len - i; 
37  
38        // count number of chars smaller than str[i] 
39        // fron str[i+1] to str[len-1] 
40        countRight = findSmallerInRight(str, i, len - 1); 
41  
42        rank += countRight * mul; 
43    } 
44  
45    return rank; 
46} 
47  
48// Driver program to test above function 
49int main() 
50{ 
51    char str[] = "string"; 
52    printf("%d", findRank(str)); 
53    return 0; 
54} 

1// Java program to find lexicographic rank 
2// of a string 
3import java.io.*; 
4import java.util.*; 
5  
6class GFG { 
7  
8    // A utility function to find factorial of n 
9    static int fact(int n) 
10    { 
11        return (n <= 1) ? 1 : n * fact(n - 1); 
12    } 
13  
14    // A utility function to count smaller 
15    // characters on right of arr[low] 
16    static int findSmallerInRight(String str, int low, 
17                                  int high) 
18    { 
19        int countRight = 0, i; 
20  
21        for (i = low + 1; i <= high; ++i) 
22            if (str.charAt(i) < str.charAt(low)) 
23                ++countRight; 
24  
25        return countRight; 
26    } 
27  
28    // A function to find rank of a string in 
29    // all permutations of characters 
30    static int findRank(String str) 
31    { 
32        int len = str.length(); 
33        int mul = fact(len); 
34        int rank = 1; 
35        int countRight; 
36  
37        for (int i = 0; i < len; ++i) { 
38            mul /= len - i; 
39  
40            // count number of chars smaller 
41            // than str[i] from str[i+1] to 
42            // str[len-1] 
43            countRight = findSmallerInRight(str, i, len - 1); 
44  
45            rank += countRight * mul; 
46        } 
47  
48        return rank; 
49    } 
50  
51    // Driver program to test above function 
52    public static void main(String[] args) 
53    { 
54        String str = "string"; 
55        System.out.println(findRank(str)); 
56    } 
57} 
58  
59// This code is contributed by Nikita Tiwari. 

1# Python program to find lexicographic  
2# rank of a string 
3  
4# A utility function to find factorial 
5# of n 
6def fact(n) : 
7    f = 1
8    while n >= 1 : 
9        f = f * n 
10        n = n - 1
11    return f 
12      
13# A utility function to count smaller  
14# characters on right of arr[low] 
15def findSmallerInRight(st, low, high) : 
16      
17    countRight = 0
18    i = low + 1
19    while i <= high : 
20        if st[i] < st[low] : 
21            countRight = countRight + 1
22        i = i + 1
23   
24    return countRight 
25      
26# A function to find rank of a string 
27# in all permutations of characters 
28def findRank (st) : 
29    ln = len(st) 
30    mul = fact(ln) 
31    rank = 1
32    i = 0 
33   
34    while i < ln : 
35          
36        mul = mul / (ln - i) 
37          
38        # count number of chars smaller  
39        # than str[i] fron str[i + 1] to 
40        # str[len-1] 
41        countRight = findSmallerInRight(st, i, ln-1) 
42   
43        rank = rank + countRight * mul 
44        i = i + 1
45          
46    return rank 
47      
48      
49# Driver program to test above function 
50st = "string"
51print (findRank(st)) 
52  
53# This code is contributed by Nikita Tiwari. 

1// C# program to find lexicographic rank 
2// of a string 
3using System; 
4  
5class GFG { 
6  
7    // A utility function to find factorial of n 
8    static int fact(int n) 
9    { 
10        return (n <= 1) ? 1 : n * fact(n - 1); 
11    } 
12  
13    // A utility function to count smaller 
14    // characters on right of arr[low] 
15    static int findSmallerInRight(string str, 
16                                  int low, int high) 
17    { 
18        int countRight = 0, i; 
19  
20        for (i = low + 1; i <= high; ++i) 
21            if (str[i] < str[low]) 
22                ++countRight; 
23  
24        return countRight; 
25    } 
26  
27    // A function to find rank of a string in 
28    // all permutations of characters 
29    static int findRank(string str) 
30    { 
31        int len = str.Length; 
32        int mul = fact(len); 
33        int rank = 1; 
34        int countRight; 
35  
36        for (int i = 0; i < len; ++i) { 
37            mul /= len - i; 
38  
39            // count number of chars smaller 
40            // than str[i] from str[i+1] to 
41            // str[len-1] 
42            countRight = findSmallerInRight(str, 
43                                            i, len - 1); 
44  
45            rank += countRight * mul; 
46        } 
47  
48        return rank; 
49    } 
50  
51    // Driver program to test above function 
52    public static void Main() 
53    { 
54        string str = "string"; 
55        Console.Write(findRank(str)); 
56    } 
57} 
58  
59// This code is contributed nitin mittal. 

1<?php  
2// A utility function to find factorial of n 
3function fact($n) 
4{ 
5    return ($n <= 1) ? 1 :$n * fact($n - 1); 
6} 
7  
8// A utility function to count smaller  
9// characters on right of arr[low] 
10function findSmallerInRight($str, $low, $high) 
11{ 
12    $countRight = 0; 
13  
14    for ($i = $low + 1; $i <= $high; ++$i) 
15        if ($str[$i] < $str[$low]) 
16            ++$countRight; 
17  
18    return $countRight; 
19} 
20  
21// A function to find rank of a string  
22// in all permutations of characters 
23function findRank ($str) 
24{ 
25    $len = strlen($str); 
26    $mul = fact($len); 
27    $rank = 1; 
28  
29    for ($i = 0; $i < $len; ++$i) 
30    { 
31        $mul /= $len - $i; 
32  
33        // count number of chars smaller than  
34        // str[i] fron str[i+1] to str[len-1] 
35        $countRight = findSmallerInRight($str, $i,  
36                                         $len - 1); 
37  
38        $rank += $countRight * $mul ; 
39    } 
40  
41    return $rank; 
42} 
43  
44// Driver Code 
45$str = "string"; 
46echo findRank($str); 
47  
48// This code is contributed by ChitraNayal 
49?> 

1// A O(n) solution for finding rank of string 
2#include <bits/stdc++.h> 
3using namespace std; 
4#define MAX_CHAR 256 
5  
6// A utility function to find factorial of n 
7int fact(int n) 
8{ 
9    return (n <= 1) ? 1 : n * fact(n - 1); 
10} 
11  
12// Construct a count array where value at every index 
13// contains count of smaller characters in whole string 
14void populateAndIncreaseCount(int* count, char* str) 
15{ 
16    int i; 
17  
18    for (i = 0; str[i]; ++i) 
19        ++count[str[i]]; 
20  
21    for (i = 1; i < MAX_CHAR; ++i) 
22        count[i] += count[i - 1]; 
23} 
24  
25// Removes a character ch from count[] array 
26// constructed by populateAndIncreaseCount() 
27void updatecount(int* count, char ch) 
28{ 
29    int i; 
30    for (i = ch; i < MAX_CHAR; ++i) 
31        --count[i]; 
32} 
33  
34// A function to find rank of a string in all permutations 
35// of characters 
36int findRank(char* str) 
37{ 
38    int len = strlen(str); 
39    int mul = fact(len); 
40    int rank = 1, i; 
41  
42    // all elements of count[] are initialized with 0 
43    int count[MAX_CHAR] = { 0 }; 
44  
45    // Populate the count array such that count[i] 
46    // contains count of characters which are present 
47    // in str and are smaller than i 
48    populateAndIncreaseCount(count, str); 
49  
50    for (i = 0; i < len; ++i) { 
51        mul /= len - i; 
52  
53        // count number of chars smaller than str[i] 
54        // fron str[i+1] to str[len-1] 
55        rank += count[str[i] - 1] * mul; 
56  
57        // Reduce count of characters greater than str[i] 
58        updatecount(count, str[i]); 
59    } 
60  
61    return rank; 
62} 
63  
64// Driver program to test above function 
65int main() 
66{ 
67    char str[] = "string"; 
68    cout << findRank(str); 
69    return 0; 
70} 
71  
72// This is code is contributed by rathbhupendra 

1// A O(n) solution for finding rank of string 
2#include <stdio.h> 
3#include <string.h> 
4#define MAX_CHAR 256 
5  
6// A utility function to find factorial of n 
7int fact(int n) 
8{ 
9    return (n <= 1) ? 1 : n * fact(n - 1); 
10} 
11  
12// Construct a count array where value at every index 
13// contains count of smaller characters in whole string 
14void populateAndIncreaseCount(int* count, char* str) 
15{ 
16    int i; 
17  
18    for (i = 0; str[i]; ++i) 
19        ++count[str[i]]; 
20  
21    for (i = 1; i < MAX_CHAR; ++i) 
22        count[i] += count[i - 1]; 
23} 
24  
25// Removes a character ch from count[] array 
26// constructed by populateAndIncreaseCount() 
27void updatecount(int* count, char ch) 
28{ 
29    int i; 
30    for (i = ch; i < MAX_CHAR; ++i) 
31        --count[i]; 
32} 
33  
34// A function to find rank of a string in all permutations 
35// of characters 
36int findRank(char* str) 
37{ 
38    int len = strlen(str); 
39    int mul = fact(len); 
40    int rank = 1, i; 
41  
42    // all elements of count[] are initialized with 0 
43    int count[MAX_CHAR] = { 0 }; 
44  
45    // Populate the count array such that count[i] 
46    // contains count of characters which are present 
47    // in str and are smaller than i 
48    populateAndIncreaseCount(count, str); 
49  
50    for (i = 0; i < len; ++i) { 
51        mul /= len - i; 
52  
53        // count number of chars smaller than str[i] 
54        // fron str[i+1] to str[len-1] 
55        rank += count[str[i] - 1] * mul; 
56  
57        // Reduce count of characters greater than str[i] 
58        updatecount(count, str[i]); 
59    } 
60  
61    return rank; 
62} 
63  
64// Driver program to test above function 
65int main() 
66{ 
67    char str[] = "string"; 
68    printf("%d", findRank(str)); 
69    return 0; 
70}

1// A O(n) solution for finding rank of string 
2  
3class GFG { 
4  
5    static int MAX_CHAR = 256; 
6  
7    // A utility function to find factorial of n 
8    static int fact(int n) 
9    { 
10        return (n <= 1) ? 1 : n * fact(n - 1); 
11    } 
12  
13    // Construct a count array where value at every index 
14    // contains count of smaller characters in whole string 
15    static void populateAndIncreaseCount(int[] count, char[] str) 
16    { 
17        int i; 
18  
19        for (i = 0; i < str.length; ++i) 
20            ++count[str[i]]; 
21  
22        for (i = 1; i < MAX_CHAR; ++i) 
23            count[i] += count[i - 1]; 
24    } 
25  
26    // Removes a character ch from count[] array 
27    // constructed by populateAndIncreaseCount() 
28    static void updatecount(int[] count, char ch) 
29    { 
30        int i; 
31        for (i = ch; i < MAX_CHAR; ++i) 
32            --count[i]; 
33    } 
34  
35    // A function to find rank of a string in all permutations 
36    // of characters 
37    static int findRank(char[] str) 
38    { 
39        int len = str.length; 
40        int mul = fact(len); 
41        int rank = 1, i; 
42  
43        // all elements of count[] are initialized with 0 
44        int count[] = new int[MAX_CHAR]; 
45  
46        // Populate the count array such that count[i] 
47        // contains count of characters which are present 
48        // in str and are smaller than i 
49        populateAndIncreaseCount(count, str); 
50  
51        for (i = 0; i < len; ++i) { 
52            mul /= len - i; 
53  
54            // count number of chars smaller than str[i] 
55            // fron str[i+1] to str[len-1] 
56            rank += count[str[i] - 1] * mul; 
57  
58            // Reduce count of characters greater than str[i] 
59            updatecount(count, str[i]); 
60        } 
61  
62        return rank; 
63    } 
64  
65    // Driver code 
66    public static void main(String args[]) 
67    { 
68        char str[] = "string".toCharArray(); 
69        System.out.println(findRank(str)); 
70    } 
71} 
72  
73// This code has been contributed by 29AjayKumar

1# A O(n) solution for finding rank of string 
2MAX_CHAR=256; 
3  
4# all elements of count[] are initialized with 0 
5count=[0]*(MAX_CHAR + 1); 
6  
7# A utility function to find factorial of n 
8def fact(n): 
9    return 1 if(n <= 1) else (n * fact(n - 1)); 
10  
11# Construct a count array where value at every index 
12# contains count of smaller characters in whole string 
13def populateAndIncreaseCount(str): 
14    for i in range(len(str)): 
15        count[ord(str[i])]+=1; 
16  
17    for i in range(1,MAX_CHAR): 
18        count[i] += count[i - 1]; 
19  
20# Removes a character ch from count[] array 
21# constructed by populateAndIncreaseCount() 
22def updatecount(ch): 
23  
24    for i in range(ord(ch),MAX_CHAR): 
25        count[i]-=1; 
26  
27# A function to find rank of a string in all permutations 
28# of characters 
29def findRank(str): 
30    len1 = len(str); 
31    mul = fact(len1); 
32    rank = 1; 
33  
34  
35    # Populate the count array such that count[i] 
36    # contains count of characters which are present 
37    # in str and are smaller than i 
38    populateAndIncreaseCount(str); 
39  
40    for i in range(len1): 
41        mul = mul//(len1 - i); 
42  
43        # count number of chars smaller than str[i] 
44        # fron str[i+1] to str[len-1] 
45        rank += count[ord(str[i]) - 1] * mul; 
46  
47        # Reduce count of characters greater than str[i] 
48        updatecount(str[i]); 
49  
50    return rank; 
51  
52# Driver code 
53str = "string"; 
54print(findRank(str)); 
55  
56# This is code is contributed by chandan_jnu 

1// A O(n) solution for finding rank of string 
2using System; 
3  
4class GFG { 
5  
6    static int MAX_CHAR = 256; 
7  
8    // A utility function to find factorial of n 
9    static int fact(int n) 
10    { 
11        return (n <= 1) ? 1 : n * fact(n - 1); 
12    } 
13  
14    // Construct a count array where value at every index 
15    // contains count of smaller characters in whole string 
16    static void populateAndIncreaseCount(int[] count, char[] str) 
17    { 
18        int i; 
19  
20        for (i = 0; i < str.Length; ++i) 
21            ++count[str[i]]; 
22  
23        for (i = 1; i < MAX_CHAR; ++i) 
24            count[i] += count[i - 1]; 
25    } 
26  
27    // Removes a character ch from count[] array 
28    // constructed by populateAndIncreaseCount() 
29    static void updatecount(int[] count, char ch) 
30    { 
31        int i; 
32        for (i = ch; i < MAX_CHAR; ++i) 
33            --count[i]; 
34    } 
35  
36    // A function to find rank of a string in all permutations 
37    // of characters 
38    static int findRank(char[] str) 
39    { 
40        int len = str.Length; 
41        int mul = fact(len); 
42        int rank = 1, i; 
43  
44        // all elements of count[] are initialized with 0 
45        int[] count = new int[MAX_CHAR]; 
46  
47        // Populate the count array such that count[i] 
48        // contains count of characters which are present 
49        // in str and are smaller than i 
50        populateAndIncreaseCount(count, str); 
51  
52        for (i = 0; i < len; ++i) { 
53            mul /= len - i; 
54  
55            // count number of chars smaller than str[i] 
56            // fron str[i+1] to str[len-1] 
57            rank += count[str[i] - 1] * mul; 
58  
59            // Reduce count of characters greater than str[i] 
60            updatecount(count, str[i]); 
61        } 
62  
63        return rank; 
64    } 
65  
66    // Driver code 
67    public static void Main(String[] args) 
68    { 
69        char[] str = "string".ToCharArray(); 
70        Console.WriteLine(findRank(str)); 
71    } 
72} 
73  
74/* This code contributed by PrinciRaj1992 */

1<?php 
2// A O(n) solution for finding rank of string 
3$MAX_CHAR=256; 
4  
5// A utility function to find factorial of n 
6function fact($n) 
7{ 
8    return ($n <= 1) ? 1 : $n * fact($n - 1); 
9} 
10  
11// Construct a count array where value at every index 
12// contains count of smaller characters in whole string 
13function populateAndIncreaseCount(&$count, $str) 
14{ 
15global $MAX_CHAR; 
16    for ($i = 0; $i < strlen($str); ++$i) 
17        ++$count[ord($str[$i])]; 
18  
19    for ($i = 1; $i < $MAX_CHAR; ++$i) 
20        $count[$i] += $count[$i - 1]; 
21} 
22  
23// Removes a character ch from count[] array 
24// constructed by populateAndIncreaseCount() 
25function updatecount(&$count, $ch) 
26{ 
27    global $MAX_CHAR; 
28    for ($i = ord($ch); $i < $MAX_CHAR; ++$i) 
29        --$count[$i]; 
30} 
31  
32// A function to find rank of a string in all permutations 
33// of characters 
34function findRank($str) 
35{ 
36    global $MAX_CHAR; 
37    $len = strlen($str); 
38    $mul = fact($len); 
39    $rank = 1; 
40  
41    // all elements of count[] are initialized with 0 
42    $count=array_fill(0, $MAX_CHAR + 1, 0); 
43  
44    // Populate the count array such that count[i] 
45    // contains count of characters which are present 
46    // in str and are smaller than i 
47    populateAndIncreaseCount($count, $str); 
48  
49    for ($i = 0; $i < $len; ++$i)  
50    { 
51        $mul = (int)($mul/($len - $i)); 
52  
53        // count number of chars smaller than str[i] 
54        // fron str[i+1] to str[len-1] 
55        $rank += $count[ord($str[$i]) - 1] * $mul; 
56  
57        // Reduce count of characters greater than str[i] 
58        updatecount($count, $str[$i]); 
59    } 
60  
61    return $rank; 
62} 
63  
64    // Driver code 
65    $str = "string"; 
66    echo findRank($str); 
67  
68// This is code is contributed by chandan_jnu 
69?>