This blog was last modified 563 days before.

Question Description

Non-descending Sequence

A string is called non-descending sequence (NDS) if it satisfied all the following condition:

  • No duplicated letters in string.
  • Letters appear in the same order in the string as they do in the alphabet.

For example, these are NDS: abc, b, agjz

And these are not: aac (duplicated), bac (wrong order)

For convenience, we will use pair to refer a NDS in the rest of this passage.

Indexing

Now, we sort all pair in dictionary order, then index them starting from 1, see example below:

1 -> a
2 -> b
...
26 -> z
27 -> ab
...

Question: Given a pair, return the index of the pair.

Analysis

Beautiful Pair & Ending-Beautiful Pair

The whole question seems a little bit difficult now, so we may start with a simpler case at first.

Let's call a pair with the following properties a beautiful pair.

  • All the letters in the pair is directly adjacent in alphabet.

For example, abcde, xyz is beautiful pair.

More, we call a pair ending-beautiful pair if it's beautiful pair and it's ending with z. For example uvwxyz.

At following, we will denote beautiful pair by BP and ending-beautiful pair by EBP.

Number of pairs between BP and EBP

It's easy to calculate the number of pairs between the range [BP, EBP] (Notice the start must be BP and end must be EBP).

Here we are going to use a combinatorial formular:

$$C_m^n = \frac{\sum_{i=m-n+1}^{m} i}{\sum_{i=1}^{n} i} $$

Notice if the first letter in the start BP is N (N could be any letter), then we could determine that all letters appear in the pairs in range [BP, EBP] could only in range [N, z]

For example, if the range is [efg, xyz], then we can say all letters appear in those pairs in this range could only have alphabet from e to z, you can't find an a or c in any pair in this range.

And for the number of all pairs with length 3 and all letters from e to z (totally 22), the answer will be ${C_{22}^{2} = 231}$.

But why? Actually the NDS has some associations with combination rule. We can find that if we choose N letters from alphabet in order-insensitive way in a range of alphabet, it will be exactly a NDS.

For example, choose 3 letters from [c, x], then it could be c, d, x, e, g, u etc, all of them just happen to make up the entire NDS which's length is 3 and only with letters from c to x.

Question Partition and Calculation

Now we have already know how to calculate the numbers of pairs in range like [BP, EBP], how to calculate the number in any range just like the quetions ask [a, ???] (The number of the pairs between a and ??? is excatly the index of ???)

Here we can use the idea of Partition.

Consider a pair like bfh, how to calculte the number of pairs in range [a, cfh]? Since we can calculate pattern like [BP, EBP], we need to try divide them into lots of part with this pattern, like the process below:

First we divide different length into different part

a-z ([BP, EBP] Pattern)
ab-yz ([BP, EBP] Pattern)
abc-cfh

Since abc-bfg is not the desired pattern, we continue to divide it, we loop the first letter to get more detailed and small range.

abc-byz
bcd-byz
cde-cfh

And if the first letter is the same, we could remove them:

bc-yz ([BP, EBP] Pattern)
cd-yz ([BP, EBP] Pattern)
de-fh

Now we got de-fh, we just continue to loop the first letter to divide the range like below, until we got a [BP, EBP] pattern, or until the pairs length in the range is 1 such as [c,h] and which we could directly calculate the answer.

de-dz -> e-z (Length 1) ([BP, EBP] Pattern)
ef-ez -> f-z (Length 1) ([BP, EBP] Pattern)
fg-fh -> g-h (Length 1)

Now, we have finish the calculation.

Code Implementation

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using LL = long long;

using std::cin, std::cout, std::endl;
using std::vector, std::string;

const char endq = '\n';

// function declaration
vector<int> convertPairStringToInt(const string &stringPair);
string convertPairIntToString(vector<int> pair);
bool isBeautifulPair(vector<int> pair);
bool isEndingBeautifulPair(vector<int> pair);
vector<int> generateBeautifulPair(int leadingNum, int len);
vector<int> generateEndingBeautifulPair(int len);
LL getCombinationNumber(LL base, LL choose);
LL getPairIndex(vector<int> startPair, vector<int> endPair);

// Convert the pair storage pattern from string to vector<int>
// `a` will be converted to 1 with this function
vector<int> convertPairStringToInt(const string &stringPair)
{
    // get string len
    int len = stringPair.length();
    // create vector
    vector<int> intPair(len);
    // convert
    for (int i = 0; i < len; ++i)
    {
        intPair[i] = stringPair[i] - 'a' + 1;
    }
    // return
    return intPair;
}

// Convert the pair storage pattern from vector<int> to string
string convertPairIntToString(vector<int> pair)
{
    int len = pair.size();
    string a = "";
    for (int i = 0; i < len; ++i)
    {
        a.push_back(pair[i] + 'a' - 1);
    }
    return a;
}

// Return true if a pair is a beautiful pair
bool isBeautifulPair(vector<int> pair)
{
    int len = pair.size();
    for (int i = 0; i < len - 1; ++i)
    {
        if (pair[i + 1] - pair[i] != 1)
        {
            return false;
        }
    }
    return true;
}

// Return true if a pair is a ending-beautiful pair
bool isEndingBeautifulPair(vector<int> pair)
{
    if (isBeautifulPair(pair) == false)
    {
        return false;
    }
    if (pair.back() != 26)
    {
        return false;
    }
    return true;
}

// Generate a new beautiful pair
vector<int> generateBeautifulPair(int leadingNum, int len)
{
    vector<int> pair;
    for (int i = 0; i < len; ++i)
    {
        pair.push_back(leadingNum + i);
    }
    return pair;
}

// Generate a ending-beautiful pair
vector<int> generateEndingBeautifulPair(int len)
{
    return generateBeautifulPair(26 - len + 1, len);
}

LL getCombinationNumber(LL base, LL choose)
{
    // optimize
    if (choose * 2 > base)
    {
        choose = base - choose;
    }
    LL nume = 1;
    LL deno = 1;
    for (int i = 1; i <= choose; ++i)
    {
        nume *= base - i + 1;
        deno *= i;
    }
    return nume / deno;
}

// Return number of pairs between the startPair and endPair, including these two
LL getPairIndex(vector<int> startPair, vector<int> endPair)
{
    // cout << "[DEBUG] "
    //      << " Start: " << convertPairIntToString(startPair) << " End: " << convertPairIntToString(endPair) << endq;
    // get length of two pairs
    int startLen = startPair.size();
    int endLen = endPair.size();

    if (startPair == endPair)
    {
        return 1;
    }

    // if pair length is the same
    if (startLen == endLen)
    {
        // if pair length is both 1
        if (startLen == 1)
        {
            return endPair[0] - startPair[0] + 1;
        }
        // if the pair has same first num (char)
        if (startPair[0] == endPair[0])
        {
            startPair.erase(startPair.begin());
            endPair.erase(endPair.begin());
            return getPairIndex(startPair, endPair);
        }
        // if startPair is not beautiful
        if (isBeautifulPair(startPair) == false)
        {
            return getPairIndex(generateBeautifulPair(startPair[0], startLen), endPair) -
                   getPairIndex(generateBeautifulPair(startPair[0], startLen), startPair) +
                   1;
        }
        // if startPair is beautiful and endPair is ending-beautiful
        if (isEndingBeautifulPair(endPair) == true)
        {
            return getCombinationNumber(26 - startPair[0] + 1, startLen);
        }
        // else, loop the first num to get the total number as ans
        LL ans = 0;
        for (int firstNum = startPair[0]; firstNum < endPair[0]; ++firstNum)
        {
            ans += getPairIndex(generateBeautifulPair(firstNum + 1, startLen - 1), generateEndingBeautifulPair(startLen - 1));
        }
        // deal with the rest part
        vector<int> tmpPair = endPair;
        tmpPair.erase(tmpPair.begin());
        ans += getPairIndex(generateBeautifulPair(endPair[0] + 1, startLen - 1), tmpPair);
        return ans;
    }

    // if startLen != endLen
    vector<int> aPair;
    aPair.push_back(1);

    // if startPair is not aPair (aPair is the firstPair and which's index is 1)
    if (startPair != aPair)
    {
        return getPairIndex(aPair, endPair) - getPairIndex(aPair, startPair) + 1;
    }

    LL ans = 0;
    for (int i = 1; i < endLen; ++i)
    {
        ans += getPairIndex(generateBeautifulPair(1, i), generateEndingBeautifulPair(i));
    }
    ans += getPairIndex(generateBeautifulPair(1, endLen), endPair);
    return ans;
}

vector<int> getNextPair(vector<int> pair)
{
    int len = pair.size();
    if (pair[len - 1] < 26)
    {
        ++pair[len - 1];
        return pair;
    }
    for (int i = 0; i < len; ++i)
    {
        vector<int> subPair(pair.begin() + i, pair.end());
        bool isEnding = isEndingBeautifulPair(subPair);
        if (isEnding == true)
        {
            if (i == 0)
            {
                return generateBeautifulPair(1, len + 1);
            }
            vector<int> newPair(len);
            for (int j = 0; j < i - 1; ++j)
            {
                newPair[j] = pair[j];
            }
            newPair[i - 1] = pair[i - 1] + 1;
            for (int j = i; j < len; ++j)
            {
                newPair[j] = newPair[j - 1] + 1;
            }
            return newPair;
        }
    }
    return pair;
}

void test()
{
    vector<int> aPair;
    aPair.push_back(1);
    LL currentIndex = 1;
    vector<int> currentPair = aPair;
    LL calculated;
    bool ok;
    while (true)
    {
        calculated = getPairIndex(aPair, currentPair);
        ok = (currentIndex == calculated);
        cout << "  Correct: " << currentIndex << endq;
        cout << "Calculate: " << calculated << endq;
        cout << "   Result: " << (ok ? "OK" : "Error") << endq;
        cout << "----------------------------" << endq;
        if (ok == false)
        {
            for (auto i : currentPair)
            {
                cout << i << ",";
            }
            return;
        }
        ++currentIndex;
        currentPair = getNextPair(currentPair);
    }
}

int main()
{
    cout << getPairIndex(convertPairStringToInt("a"), convertPairStringToInt("bd"));
    vector<int> testVec = getNextPair({25, 26});
    test();
}