如何通过索引从唯一组合列表中直接获取对应组合？

场景实现 #

我通过以下代码将每个项映射到单个字符，构建字典：

alpha = 'abcdefghijklmnopqrstuvwxyz0123456789'
items = ['item-a','item-b'...'item-n']
my_map = defaultdict()

for i, item in enumerate(items):
        my_map[alpha[i]] = item

之后会随机选取字符组合（如ab7对应3个项）处理对应的值。对于n个项，总共有2^n种组合，以6个项为例，可选组合列表如下：

['a','b','ab'....'bef'...'abcdef'] 

注意： 组合仅出现一次，例如'ba'与'ab'视为同一组合，列表中仅保留'ab'。

核心问题 #

已知组合的索引，如何在不生成所有可能组合的前提下，直接获取该索引对应的组合？

尝试过的代码 #

我试过下面这段代码，但它只适用于全排列场景，不符合需求：

import math

def get_bijective_val(n, alphabet):
    base = len(alphabet)
    digits = []
    while n:
        remainder = math.ceil(n/base)-1
        digits.append(n - remainder*base)
        n = remainder
    digits.reverse()
    return "".join(alphabet[digit-1] for digit in digits)

get_bijective_val(50,'abcdef')

预期结果 #

>>> print(get_bijective_val(0, 'abcdef'))
>>> 'a'
>>> print(get_bijective_val(50, 'abcdef'))
>>> 'bef'
>>> print(get_bijective_val(63, 'abcdef'))
>>> 'abcdef'

这个问题的核心是将索引转换为二进制掩码，每个组合对应原集合元素的选择状态（选/不选）。具体实现思路如下：

1. 对输入索引做偏移：因为你的预期中索引0对应第一个非空组合（'a'），而二进制中0对应空组合，所以需要把索引值加1得到掩码。
2. 遍历字符集的每个位置，用二进制位判断是否选中该字符：掩码的每一位对应字符集中的一个字符，位为1表示选中该字符。
3. 按字符集顺序拼接选中的字符，保证组合的唯一性（如只生成'ab'而非'ba'）。

实现代码 #

def get_combination(index, alphabet):
    # 偏移索引，将空组合对应的值让给第一个非空组合
    mask = index + 1
    combination = []
    for idx, char in enumerate(alphabet):
        # 检查掩码的第idx位是否为1
        if mask & (1 << idx):
            combination.append(char)
    return ''.join(combination)

# 验证预期结果
print(get_combination(0, 'abcdef'))  # 输出: 'a'
print(get_combination(50, 'abcdef')) # 输出: 'bef'
print(get_combination(63, 'abcdef')) # 输出: 'abcdef'

代码说明 #

• mask = index + 1：解决索引偏移问题，确保索引0对应第一个字符的组合。
• 1 << idx：生成仅第idx位为1的二进制数，与掩码做按位与操作，判断该位置的字符是否被选中。
• 按字符集顺序遍历拼接，保证组合的有序性，避免重复组合（如'ab'和'ba'只保留前者）。

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