gakkouを並び替えた100番目がgokakuみたいやつ（ライブラリ化しました）

　こころあたたまるお話ですね。

　これを求めていきたいと思います。0-indexed の方が考えやすいので、$99$ 番目の数を求めます。

• gakkou の並べ替えの中で、辞書順 $99$ 番目の文字列を答えよ

　まず gakkou の並べ替えが何通りあるかというと、$\frac{6!}{2!}=360$ 通りとなります。全部の要素の階乗をとったあとで、重複している要素があればそれらの階乗で割ればよいです。

　もう少し細かくみていくために、gakkou をソートして agkkou とします。これら $5$ 種類の文字について、それぞれの文字を抜いたときの場合の数は以下のようになります。

　これを累積和として考えると、$99$ は $[60,120)$ の範囲に入ります。よって、g は確定して、左側のカウント分である $60$ を引きます。

• g（ここまで確定）akkou の中で、辞書順 $39$ 番目の文字列を答えよ

　同様に考えると、$[36,48)$ の範囲に入るので、o が確定……という流れを繰り返していくと、$x$ 番目（0-indexed)の文字列が得られます。

　以上の処理をプログラムで書いた途中経過が以下になります。

prefix = 0 60 120 240 300 360
remaining:99 idx:1->g
prefix = 0 12 12 36 48 60
remaining:39 idx:3->o
prefix = 0 3 3 9 9 12
remaining:3 idx:2->k
prefix = 0 2 2 4 4 6
remaining:0 idx:0->a
prefix = 0 0 0 1 1 2
remaining:0 idx:2->k
prefix = 0 0 0 0 0 1
remaining:0 idx:4->u

差分更新の取り方

　上のような処理をするためには、ある要素を抜いたときに、それを抜いた状態での順列の並べ方がどうなるかを計算したいです。

　とりあえず、要素を増やすときの方がわかりやすいです。ある $N$ 個の要素の順列の並べ方を $C_N$ とします。これに要素 $a$ を追加するとき、この $a$ がユニークならば、$N+1$ 個の「仕切り」のどこかに入れればいいので、

• $C_N \longrightarrow (N+1)C_N$

　となります。しかし、元から $1$ 個ある場合は、追加したあとの $2$ 個は等価になるので、$\div2$ をしないといけません。これを一般化すると、追加後の要素の数を $F(a)$ と定義して、

• $C_N \longrightarrow \frac{N+1}{F(a)}C_N$

　となります。ちなみにこれを漸化式っぽく考えると、全部の階乗を、重複分の階乗で割るという冒頭の考え方が導かれます。

　要素を減らすときは逆のことをすればよいです。

• $C_N \longrightarrow \frac{F(a)}{N}C_N$

逆変換

　配列から順番を求めたいときは、この逆をすればよいです。すなわち、自分の要素の直前まで累積和を足します。

prefix = 0 60 120 240 300 360
idx:g->1 +60
prefix = 0 12 12 36 48 60
idx:o->0 +36
prefix = 0 3 3 9 9 12
idx:k->2 +3
prefix = 0 2 2 4 4 6
idx:a->0 +0
prefix = 0 0 0 1 1 2
idx:k->2 +0
prefix = 0 0 0 0 0 1
idx:u->5 +0

ライブラリ化

　以上の要素をまとめてライブラリ化しました。

　なお、以下のライブラリは設計の骨子は考えましたが、生成 AI に投げたところ色々改善点や追加機能を提案されたのでそのまま追加したものです。私が心を込めて書いたものより生成 AI の方が丁寧。

template<typename T>
struct MultisetPermutation {
    int distinct_count;
    int total_count;
    vector<int> freq;
    ll perm_count;
    vector<T> elements;

    MultisetPermutation(vector<T> s) { init(s.begin(), s.end()); }
    MultisetPermutation(const basic_string<T>& s) { init(s.begin(), s.end()); }

private:
    template<typename Iter>
    void init(Iter first, Iter last) {
        vector<T> s(first, last);
        sort(s.begin(), s.end());
        perm_count = 1;
        distinct_count = 0;
        total_count = s.size();

        int l = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            perm_count = perm_count * (r + 1) / (r - l + 1);
            if (r + 1 == (int)s.size() || s[r] != s[r + 1]) {
                elements.push_back(s[r]);
                freq.push_back(r - l + 1);
                distinct_count++;
                l = r + 1;
            }
        }
    }

public:
    vector<ll> get_rank_prefix_sum() const {
        vector<ll> result(distinct_count + 1);
        for (int i = 0; i < distinct_count; i++) {
            result[i + 1] = result[i] + perm_count / total_count * freq[i];
        }
        return result;
    }

    int get_element_index(const T& target) const {
        auto itr = lower_bound(elements.begin(), elements.end(), target);
        assert(itr != elements.end() && *itr == target);
        return itr - elements.begin();
    }

    void remove_by_index(int idx) {
        assert(0 <= idx && idx < distinct_count);
        assert(freq[idx] > 0);
        perm_count = perm_count / total_count * freq[idx];
        freq[idx]--;
        total_count--;
    }

    void add_by_index(int idx) {
        assert(0 <= idx && idx < distinct_count);
        total_count++;
        freq[idx]++;
        perm_count = perm_count * total_count / freq[idx];
    }

    void remove_element(const T& target) {
        remove_by_index(get_element_index(target));
    }

    void add_element(const T& target) {
        add_by_index(get_element_index(target));
    }

    template<typename Container>
    ll container_to_rank(const Container& perm) {
        vector<int> tmp_freq = freq;
        int tmp_total = total_count;
        ll tmp_perm_count = perm_count;
        ll rank = 0;

        for (const T& c : perm) {
            int idx = get_element_index(c);
            for (int i = 0; i < idx; i++) {
                if (tmp_freq[i] > 0) {
                    rank += tmp_perm_count / tmp_total * tmp_freq[i];
                }
            }
            tmp_perm_count = tmp_perm_count / tmp_total * tmp_freq[idx];
            tmp_freq[idx]--;
            tmp_total--;
        }
        return rank;
    }

    vector<T> rank_to_permutation(ll rank) const {
        vector<int> tmp_freq = freq;
        int tmp_total = total_count;
        ll tmp_perm_count = perm_count;
        vector<T> result;

        for (int pos = 0; pos < total_count; pos++) {
            for (int i = 0; i < distinct_count; i++) {
                if (tmp_freq[i] == 0) continue;
                ll count = tmp_perm_count / tmp_total * tmp_freq[i];
                if (rank < count) {
                    result.push_back(elements[i]);
                    tmp_perm_count = tmp_perm_count / tmp_total * tmp_freq[i];
                    tmp_freq[i]--;
                    tmp_total--;
                    break;
                }
                rank -= count;
            }
        }
        return result;
    }

    // string専用（T = charの時のみ有効）
    basic_string<T> rank_to_string(ll rank) const {
        vector<T> v = rank_to_permutation(rank);
        return basic_string<T>(v.begin(), v.end());
    }

    // vector版エイリアス
    ll permutation_to_rank(const vector<T>& perm) {
        return container_to_rank(perm);
    }

    // string版エイリアス
    ll string_to_rank(const basic_string<T>& s) {
        return container_to_rank(s);
    }
};

使い方

int main(){
    string s = "gakkou";
    MultisetPermutation<char> mp(s);
    cout << mp.perm_count << endl; // 360
    cout << mp.rank_to_string(0) << endl; // agkkou
    cout << mp.rank_to_string(99) << endl; // gokaku
    cout << mp.string_to_rank("gokaku") << endl; // 99
}

注意点

　順列の組合せが $64$ bitに収まる数じゃないとオーバーフローするので注意してください。mod 数を使えば string_to_rank だけなら可能な気がしますが、rank_to_string は不可能になると思います。