带M限制的A-restricted compositions排序/逆排序与状态枚举优化咨询

我需要枚举n=1,2,...,N个玻色子在L个格点上的所有合法状态，其中每个格点的最大占据数为M（M<N）。从数学层面看，这等价于找出N个元素分配到L个容器中的所有A-restricted compositions，其中限制集合A={0,1,...,M}（注：原文表述为A={1,2,...,M}，结合玻色子态允许空穴的实际场景，此处应为包含0的非负整数集合）。

核心需求是同时获取每个状态的：

• 相对排名：该状态在对应n粒子层级内的序号；
• 绝对排名：累计所有n'<n的粒子层级的状态总数后，该状态的全局序号。

这一需求源于精确对角化场景：添加/移除粒子时需要在不同粒子数层级间快速跳转。

现有无限制枚举实现 #

我已实现无M限制的Python枚举算法（代码中n为粒子数，k为格点数），并包含一个计算排名的函数，但尚未实现逆排名（由排名反推状态）的功能：

import numpy as np
from scipy.special import binomial

def first_state_lex_multi(n, k):
    x = [0] * k
    x[-1] = n
    return x

def last_state_lex_multi(n, k):
    x = [0] * k 
    x[0] = n
    return x

def next_state_lex_multi(x):
    v = x[0]
    x[0] = 0
    j = 1
    while (0 == x[j]):
        j += 1
    x[j] -= 1
    x[j-1] = 1 + v
    return x

def colexRank_multi(conf):
    N = np.sum(conf)
    L = len(conf)

    previous_conf_num = 0
    for n in range(1, N):
        previous_conf_num += binomial(n + L - 1, n)

    rel_rank = 0
    for k in range(1, L):
        rel_rank += binomial(N + k - 1 - np.sum(conf[k:]), k)

    abs_rank = previous_conf_num + rel_rank
    return rel_rank, abs_rank

def generate_composition_reverse(n, k):
    x = first_state_lex_multi(n, k)    
    x_last = last_state_lex_multi(n, k)

    while x != x_last:
        print("composition:", x)  
        rel, abs_idx = colexRank_multi(x)
        print("rel index:", rel)
        print("abs index:", abs_idx)
  
        x = next_state_lex_multi(x)

    print("composition:", x)  
    rel, abs_idx = colexRank_multi(x)
    print("rel index:", rel)
    print("abs index:", abs_idx)

当前困境与疑问 #

目前有两种可行方向，但各有短板：

1. 哈希存储方案：按n递增顺序生成所有状态，过滤掉占据数超过M的非法状态，将合法状态与对应排名存入字典实现O(1)查找。但当状态数达数百万级别时，字典的哈希存储会占用大量内存，存在内存溢出风险。
2. 排序/逆排序函数方案：实现从排名反推状态的逆排序函数，无需存储所有状态，无内存限制，但时间复杂度为O(N)，比哈希查找慢。

请问针对这一需求，有哪些内存高效且性能可接受的实现思路或优化建议？

内容的提问来源于stack exchange，提问作者Paolo Molignini