Строковые перестановки rank + структура данных

Ответ 1

Существует алгоритм O (n | Σ |), чтобы найти ранг строки длины n в списке ее перестановок. Здесь Σ - алфавит.

Алгоритм

Каждая перестановка, которая находится ниже s, может быть записана однозначно в виде pcx; где:

• p является правильным префиксом s
• c - персонаж, расположенный ниже символа, появляющегося сразу после p в s. И c также является символом, встречающимся в части s, не включенной в p.
• x - любая перестановка остальных символов, встречающихся в s; то есть не включается в p или c.

Мы можем подсчитать перестановки, включенные в каждый из этих классов, итерируя через каждый префикс s в порядке возрастания длины, сохраняя частоту символов, появляющихся в оставшейся части s, а также число перестановок x. Подробности оставляют читателю.

Это предполагает, что при выполнении арифметических операций требуется постоянное время; который он не будет; так как число задействованных может иметь nlog | Σ | цифры. С учетом этого алгоритм будет работать в O (n ² log | Σ | log (nlog | Σ |)). Поскольку мы можем добавлять, вычитать, умножать и делить два d-цифры в O (dlogd).

Реализация С++

typedef long long int lli;

lli rank(string s){
    int n = s.length();

    vector<lli> factorial(n+1,1);
    for(int i = 1; i <= n; i++)
        factorial[i] = i * factorial[i-1];

    vector<int> freq(26);
    lli den = 1;
    lli ret = 0;
    for(int i = n-1; i >= 0; i--){
        int si = s[i]-'a';
        freq[si]++;
        den *= freq[si];
        for(int c = 0; c < si; c++) 
            if(freq[c] > 0) 
                ret += factorial[n-i-1] / (den / freq[c]);
    }
    return ret + 1;
}

Ответ 2

Это похоже на алгоритм quickselect. В несортированном массиве целых чисел найдите индекс некоторого определенного элемента массива. Элементом раздела будет заданная строка.

Edit:

На самом деле он похож на метод partition, выполненный в QuickSort. Данная строка является элементом раздела. Когда все перестановки сгенерированы, сложность поиска ранга для строк с длиной k будет O (nk). Вы можете сгенерировать перестановки строк с помощью рекурсии и сохранить их в связанном списке. Вы можете передать этот связанный список в метод раздела.

Здесь java-код для генерации всех перестановок String:

 private static int generateStringPermutations(String name,int currIndex) {

        int sum = 0;

        for(int j=name.length()-1;j>=0;j--) {
            for(int i=j-1;((i<j) && (i>currIndex));i--) {

                String swappedString = swapCharsInString(name,i,j);
                list.add(swappedString);
                //System.out.println(swappedString);
                sum++;
                sum = sum + generateStringPermutations(swappedString,i);
            }
        }
        return sum;


    }

Edit:

Генерация всех перестановок является дорогостоящей. Если строка содержит различные символы, ранг может быть определен без генерации всех перестановок. Здесь ссылка.

Это может быть расширено для случаев, когда есть повторяющиеся символы.

Вместо x * (n-1)! который относится к отдельным случаям, указанным в ссылке,

Для повторения символов это будет:

если есть один символ, который повторяется дважды,

x * (n-1)!/2!

Возьмем пример. Для строки abca следующие комбинации:

aabc, aacb, abac, abca, acab, acba, baac, baca, bcaa, caab, caba, cbaa (в отсортированном порядке)

Всего комбинаций = 4!/2!= 12

если мы хотим найти ранг 'bcaa', тогда мы знаем, что все строки, начинающиеся с 'a', перед ними составляют 3!= 6.

Обратите внимание, что поскольку "a" является стартовым символом, остальные символы: a, b, c, а повторений нет, поэтому он равен 3!. Мы также знаем, что строки, начинающиеся с 'ba', будут до 2-го!= 2, поэтому ранг равен 9.

Другой пример. Если мы хотим найти ранг 'caba':

Все строки, начинающиеся с а, равны до = 6. Все строки, начинающиеся с b, перед = 3!/2!= 3 (Поскольку, как только мы выберем b, мы остаемся с a, a, c и потому, что есть повторения, это 3!/2!. Все строки, начинающиеся с caa, будут до 1

Итак, окончательный ранг равен 11.

Ответ 3

Из GeeksforGeeks:

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

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

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

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

R X X X X X X X X X X X X X X X X X 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! +...

Теперь исправьте я и повторите тот же процесс для 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