Рубрики

Лексикографический ранг строки

По заданной строке найдите ее ранг среди всех перестановок, отсортированных по лексикографическому признаку. Например, ранг «abc» равен 1, ранг «acb» равен 2, а ранг «cba» равен 6.

Примеры:

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

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

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

Для простоты предположим, что строка не содержит дублированных символов.

Одним из простых решений является инициализация ранга как 1, генерация всех перестановок в лексикографическом порядке . После генерации перестановки проверьте, совпадает ли сгенерированная перестановка с заданной строкой, если она такая же, затем верните ранг, если нет, то увеличьте ранг на 1. В худшем случае сложность по времени этого решения будет экспоненциальной. Ниже приводится эффективное решение.

Пусть заданная строка будет «STRING». Во входной строке 'S' является первым символом. Всего 6 символов, и 4 из них меньше, чем «S». Так что может быть 4 * 5! меньшие строки, где первый символ меньше, чем 'S', например, следующий

RXXXXX
IXXXXX
NXXXXX
GXXXXX

Теперь давайте исправим 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!

Ранг = 4 * 5! + 4 * 4! + 3 * 3! + 1 * 2! + 1 * 1! + 0 * 0! = 597

Обратите внимание, что приведенные выше вычисления находят количество меньших строк. Следовательно, ранг данной строки равен числу меньших строк плюс 1. Окончательный ранг = 1 + 597 = 598.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска лексикографического ранга
// строки
#include <bits/stdc++.h>
#include <string.h>

  

using namespace std;

// Функция полезности для поиска факториала n

int fact(int n)

{

    return (n <= 1) ? 1 : n * fact(n - 1);

}

  
// Полезная функция для подсчета меньших символов справа
// из 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;

}

  
// Функция для нахождения ранга строки во всех перестановках
// символов

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;

  

        // считать число символов меньше чем str [i]

        // от str [i + 1] до str [len-1]

        countRight = findSmallerInRight(str, i, len - 1);

  

        rank += countRight * mul;

    }

  

    return rank;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char str[] = "string";

    cout << findRank(str);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C программа для поиска лексикографического ранга
// строки
#include <stdio.h>
#include <string.h>

  
// Функция полезности для поиска факториала n

int fact(int n)

{

    return (n <= 1) ? 1 : n * fact(n - 1);

}

  
// Полезная функция для подсчета меньших символов справа
// из 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;

}

  
// Функция для нахождения ранга строки во всех перестановках
// символов

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;

  

        // считать число символов меньше чем str [i]

        // от str [i + 1] до str [len-1]

        countRight = findSmallerInRight(str, i, len - 1);

  

        rank += countRight * mul;

    }

  

    return rank;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char str[] = "string";

    printf("%d", findRank(str));

    return 0;

}

Джава

// Java-программа для поиска лексикографического ранга
// строки

import java.io.*;

import java.util.*;

  

class GFG {

  

    // Функция полезности для поиска факториала n

    static int fact(int n)

    {

        return (n <= 1) ? 1 : n * fact(n - 1);

    }

  

    // Вспомогательная функция для подсчета меньше

    // символы справа от 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;

    }

  

    // Функция для нахождения ранга строки в

    // все перестановки символов

    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;

  

            // считать число символов меньше

            // чем str [i] из str [i + 1] в

            // str [len-1]

            countRight = findSmallerInRight(str, i, len - 1);

  

            rank += countRight * mul;

        }

  

        return rank;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        String str = "string";

        System.out.println(findRank(str));

    }

}

  
// Этот код предоставлен Никитой Тивари.

питон

# Python программа для поиска лексикографии
# ранг строки

  
# Функция полезности для поиска факториала
№ из п

def fact(n) :

    f = 1

    while n >= 1 :

        f = f * n

        n = n - 1

    return f

      
# Полезная функция для подсчета меньше
# символов справа от 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

      
# Функция для определения ранга строки
# во всех перестановках символов

def findRank (st) :

    ln = len(st)

    mul = fact(ln)

    rank = 1

    i = 0 

   

    while i < ln :

          

        mul = mul / (ln - i)

          

        # считать количество символов меньше

        # чем str [i] перед str [i + 1] до

        # str [len-1]

        countRight = findSmallerInRight(st, i, ln-1)

   

        rank = rank + countRight * mul

        i = i + 1

          

    return rank

      

      
# Программа драйвера для проверки вышеуказанной функции

st = "string"

print (findRank(st))

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для поиска лексикографического ранга
// строки

using System;

  

class GFG {

  

    // Функция полезности для поиска факториала n

    static int fact(int n)

    {

        return (n <= 1) ? 1 : n * fact(n - 1);

    }

  

    // Вспомогательная функция для подсчета меньше

    // символы справа от 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;

    }

  

    // Функция для нахождения ранга строки в

    // все перестановки символов

    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;

  

            // считать число символов меньше

            // чем str [i] из str [i + 1] в

            // str [len-1]

            countRight = findSmallerInRight(str,

                                            i, len - 1);

  

            rank += countRight * mul;

        }

  

        return rank;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        string str = "string";

        Console.Write(findRank(str));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php 
// Функция полезности для поиска факториала n

function fact($n)

{

    return ($n <= 1) ? 1 :$n * fact($n - 1);

}

  
// Вспомогательная функция для подсчета меньше
// символы справа от arr [low]

function findSmallerInRight($str, $low, $high)

{

    $countRight = 0;

  

    for ($i = $low + 1; $i <= $high; ++$i)

        if ($str[$i] < $str[$low])

            ++$countRight;

  

    return $countRight;

}

  
// Функция для поиска ранга строки
// во всех перестановках символов

function findRank ($str)

{

    $len = strlen($str);

    $mul = fact($len);

    $rank = 1;

  

    for ($i = 0; $i < $len; ++$i)

    {

        $mul /= $len - $i;

  

        // считать количество символов меньше чем

        // str [i] от str [i + 1] до str [len-1]

        $countRight = findSmallerInRight($str, $i

                                         $len - 1);

  

        $rank += $countRight * $mul ;

    }

  

    return $rank;

}

  
// Код драйвера

$str = "string";

echo findRank($str);

  
// Этот код предоставлен ChitraNayal
?>


Выход:

598

Временная сложность вышеуказанного решения составляет O (n ^ 2). Мы можем уменьшить сложность времени до O (n), создав вспомогательный массив размером 256. См. Следующий код.

C ++

// AO (n) решение для нахождения ранга строки
#include <bits/stdc++.h>

using namespace std;

#define MAX_CHAR 256

  
// Функция полезности для поиска факториала n

int fact(int n)

{

    return (n <= 1) ? 1 : n * fact(n - 1);

}

  
// Создаем массив count, где значение каждого индекса
// содержит количество меньших символов во всей строке

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];

}

  
// Удаляет символ ch из массива count []
// построено с помощью populateAndIncreaseCount ()

void updatecount(int* count, char ch)

{

    int i;

    for (i = ch; i < MAX_CHAR; ++i)

        --count[i];

}

  
// Функция для нахождения ранга строки во всех перестановках
// символов

int findRank(char* str)

{

    int len = strlen(str);

    int mul = fact(len);

    int rank = 1, i;

  

    // все элементы count [] инициализируются с 0

    int count[MAX_CHAR] = { 0 };

  

    // Заполняем массив count так, чтобы count [i]

    // содержит количество символов, которые присутствуют

    // в строке и меньше, чем я

    populateAndIncreaseCount(count, str);

  

    for (i = 0; i < len; ++i) {

        mul /= len - i;

  

        // считать число символов меньше чем str [i]

        // от str [i + 1] до str [len-1]

        rank += count[str[i] - 1] * mul;

  

        // Уменьшаем количество символов больше чем str [i]

        updatecount(count, str[i]);

    }

  

    return rank;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char str[] = "string";

    cout << findRank(str);

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// AO (n) решение для нахождения ранга строки
#include <stdio.h>
#include <string.h>
#define MAX_CHAR 256

  
// Функция полезности для поиска факториала n

int fact(int n)

{

    return (n <= 1) ? 1 : n * fact(n - 1);

}

  
// Создаем массив count, где значение каждого индекса
// содержит количество меньших символов во всей строке

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];

}

  
// Удаляет символ ch из массива count []
// построено с помощью populateAndIncreaseCount ()

void updatecount(int* count, char ch)

{

    int i;

    for (i = ch; i < MAX_CHAR; ++i)

        --count[i];

}

  
// Функция для нахождения ранга строки во всех перестановках
// символов

int findRank(char* str)

{

    int len = strlen(str);

    int mul = fact(len);

    int rank = 1, i;

  

    // все элементы count [] инициализируются с 0

    int count[MAX_CHAR] = { 0 };

  

    // Заполняем массив count так, чтобы count [i]

    // содержит количество символов, которые присутствуют

    // в строке и меньше, чем я

    populateAndIncreaseCount(count, str);

  

    for (i = 0; i < len; ++i) {

        mul /= len - i;

  

        // считать число символов меньше чем str [i]

        // от str [i + 1] до str [len-1]

        rank += count[str[i] - 1] * mul;

  

        // Уменьшаем количество символов больше чем str [i]

        updatecount(count, str[i]);

    }

  

    return rank;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char str[] = "string";

    printf("%d", findRank(str));

    return 0;

}

Джава

// AO (n) решение для нахождения ранга строки

  

class GFG {

  

    static int MAX_CHAR = 256;

  

    // Функция полезности для поиска факториала n

    static int fact(int n)

    {

        return (n <= 1) ? 1 : n * fact(n - 1);

    }

  

    // Создаем массив count, где значение каждого индекса

    // содержит количество меньших символов во всей строке

    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];

    }

  

    // Удаляет символ ch из массива count []

    // построено с помощью populateAndIncreaseCount ()

    static void updatecount(int[] count, char ch)

    {

        int i;

        for (i = ch; i < MAX_CHAR; ++i)

            --count[i];

    }

  

    // Функция для нахождения ранга строки во всех перестановках

    // символов

    static int findRank(char[] str)

    {

        int len = str.length;

        int mul = fact(len);

        int rank = 1, i;

  

        // все элементы count [] инициализируются с 0

        int count[] = new int[MAX_CHAR];

  

        // Заполняем массив count так, чтобы count [i]

        // содержит количество символов, которые присутствуют

        // в строке и меньше, чем я

        populateAndIncreaseCount(count, str);

  

        for (i = 0; i < len; ++i) {

            mul /= len - i;

  

            // считать число символов меньше чем str [i]

            // от str [i + 1] до str [len-1]

            rank += count[str[i] - 1] * mul;

  

            // Уменьшаем количество символов больше чем str [i]

            updatecount(count, str[i]);

        }

  

        return rank;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        char str[] = "string".toCharArray();

        System.out.println(findRank(str));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# AO (n) решение для нахождения ранга строки

MAX_CHAR=256;

  
# все элементы count [] инициализируются с 0

count=[0]*(MAX_CHAR + 1);

  
# Функция полезности для поиска факториала n

def fact(n):

    return 1 if(n <= 1) else (n * fact(n - 1));

  
# Построить массив count, где значение каждого индекса
# содержит количество меньших символов во всей строке

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];

  
# Удаляет символ ch из массива count []
# построено с помощью populateAndIncreaseCount ()

def updatecount(ch):

  

    for i in range(ord(ch),MAX_CHAR):

        count[i]-=1;

  
# Функция для нахождения ранга строки во всех перестановках
количество символов

def findRank(str):

    len1 = len(str);

    mul = fact(len1);

    rank = 1;

  

  

    # Заполните массив count так, чтобы count [i]

    # содержит количество символов, которые присутствуют

    # в ул и меньше, чем я

    populateAndIncreaseCount(str);

  

    for i in range(len1):

        mul = mul//(len1 - i);

  

        # считать количество символов меньше, чем str [i]

        # от str [i + 1] до str [len-1]

        rank += count[ord(str[i]) - 1] * mul;

  

        # Уменьшить количество символов больше чем str [i]

        updatecount(str[i]);

  

    return rank;

  
# Код драйвера

str = "string";

print(findRank(str));

  
# Этот код предоставлен chandan_jnu

C #

// AO (n) решение для нахождения ранга строки

using System;

  

class GFG {

  

    static int MAX_CHAR = 256;

  

    // Функция полезности для поиска факториала n

    static int fact(int n)

    {

        return (n <= 1) ? 1 : n * fact(n - 1);

    }

  

    // Создаем массив count, где значение каждого индекса

    // содержит количество меньших символов во всей строке

    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];

    }

  

    // Удаляет символ ch из массива count []

    // построено с помощью populateAndIncreaseCount ()

    static void updatecount(int[] count, char ch)

    {

        int i;

        for (i = ch; i < MAX_CHAR; ++i)

            --count[i];

    }

  

    // Функция для нахождения ранга строки во всех перестановках

    // символов

    static int findRank(char[] str)

    {

        int len = str.Length;

        int mul = fact(len);

        int rank = 1, i;

  

        // все элементы count [] инициализируются с 0

        int[] count = new int[MAX_CHAR];

  

        // Заполняем массив count так, чтобы count [i]

        // содержит количество символов, которые присутствуют

        // в строке и меньше, чем я

        populateAndIncreaseCount(count, str);

  

        for (i = 0; i < len; ++i) {

            mul /= len - i;

  

            // считать число символов меньше чем str [i]

            // от str [i + 1] до str [len-1]

            rank += count[str[i] - 1] * mul;

  

            // Уменьшаем количество символов больше чем str [i]

            updatecount(count, str[i]);

        }

  

        return rank;

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        char[] str = "string".ToCharArray();

        Console.WriteLine(findRank(str));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

PHP

<?php
// AO (n) решение для нахождения ранга строки

$MAX_CHAR=256;

  
// Функция полезности для поиска факториала n

function fact($n)

{

    return ($n <= 1) ? 1 : $n * fact($n - 1);

}

  
// Создаем массив count, где значение каждого индекса
// содержит количество меньших символов во всей строке

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];

}

  
// Удаляет символ ch из массива count []
// построено с помощью populateAndIncreaseCount ()

function updatecount(&$count, $ch)

{

    global $MAX_CHAR;

    for ($i = ord($ch); $i < $MAX_CHAR; ++$i)

        --$count[$i];

}

  
// Функция для нахождения ранга строки во всех перестановках
// символов

function findRank($str)

{

    global $MAX_CHAR;

    $len = strlen($str);

    $mul = fact($len);

    $rank = 1;

  

    // все элементы count [] инициализируются с 0

    $count=array_fill(0, $MAX_CHAR + 1, 0);

  

    // Заполняем массив count так, чтобы count [i]

    // содержит количество символов, которые присутствуют

    // в строке и меньше, чем я

    populateAndIncreaseCount($count, $str);

  

    for ($i = 0; $i < $len; ++$i

    {

        $mul = (int)($mul/($len - $i));

  

        // считать число символов меньше чем str [i]

        // от str [i + 1] до str [len-1]

        $rank += $count[ord($str[$i]) - 1] * $mul;

  

        // Уменьшаем количество символов больше чем str [i]

        updatecount($count, $str[$i]);

    }

  

    return $rank;

}

  

    // Код драйвера

    $str = "string";

    echo findRank($str);

  
// Этот код предоставлен chandan_jnu
?>

Выход:

598

Вышеуказанные программы не работают для дублирующих символов. Чтобы заставить их работать на дубликаты символов, найдите все символы меньшего размера (в том числе и равные на этот раз), сделайте то же, что и выше, но на этот раз разделите ранг, образованный p! где p — количество повторений повторяющегося символа.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Лексикографический ранг строки

0.00 (0%) 0 votes