如何不生成笛卡尔积数组，通过索引获取对应组合

当处理超大规模笛卡尔积时，生成完整数组会直接耗尽内存。解决思路是将索引视为可变进制数，通过进制转换逻辑直接计算出对应维度的元素，无需预生成所有组合。

核心逻辑 #

把每个维度的元素数量当作该位的“进制数”，从左到右计算每个维度的权重（即后续所有维度元素数量的乘积）。用输入索引依次除以权重得到当前维度的元素下标，再取余得到剩余索引，循环处理所有维度即可。

如果维度是通过start/end/step定义的序列（而非直接给出数组），需先计算该维度的元素总数，再根据下标计算对应元素：元素值 = start + 下标 * step。

实现代码（Python） #

def get_cartesian_element(dimensions, index):
    # dimensions: 每个元素为(start, end, step)的元组列表
    counts = []
    for s, e, step in dimensions:
        if step == 0:
            raise ValueError("Step cannot be zero")
        # 计算当前维度的元素总数
        if step > 0:
            count = max(0, (e - s + step - 1) // step) if s < e else 0
        else:
            count = max(0, (s - e + abs(step) - 1) // abs(step)) if s > e else 0
        counts.append(count)
    
    # 校验索引合法性
    total = 1
    for cnt in counts:
        total *= cnt
    if index < 0 or index >= total:
        raise IndexError(f"Index {index} out of range (0 to {total-1})")
    
    # 计算权重数组：每个维度的权重是后续所有维度的数量乘积
    weights = [1] * len(dimensions)
    for i in range(len(dimensions)-2, -1, -1):
        weights[i] = weights[i+1] * counts[i+1]
    
    # 计算每个维度的对应元素
    result = []
    remaining = index
    for i in range(len(dimensions)):
        cnt = counts[i]
        if cnt == 0:
            result.append(None)
            continue
        idx = remaining // weights[i]
        remaining = remaining % weights[i]
        s, e, step = dimensions[i]
        result.append(s + idx * step)
    
    return result

示例验证 #

假设需要得到索引11对应组合[1,0,2]，定义三个维度：

• 维度0：(0, 2, 1) → 元素为[0,1]（共2个）
• 维度1：(0, 3, 1) → 元素为[0,1,2]（共3个）
• 维度2：(0, 3, 1) → 元素为[0,1,2]（共3个）

调用get_cartesian_element([(0,2,1), (0,3,1), (0,3,1)], 11)，会直接返回[1,0,2]：

1. 权重数组为3*3=9、3、1
2. 维度0下标：11 // 9 = 1 → 元素0 + 1*1 = 1
3. 剩余索引：11 % 9 = 2
4. 维度1下标：2 // 3 = 0 → 元素0 + 0*1 = 0
5. 剩余索引：2 % 3 = 2
6. 维度2下标：2 // 1 = 2 → 元素0 + 2*1 = 2

关键优势 #

• 内存占用恒定：无需生成任何中间数组，仅存储维度信息和临时计算值
• 支持任意维度数量：不管是2维还是多维度，逻辑都能适配
• 处理超大维度：即使每个维度有百万级元素，只要总组合数的索引在整数范围内（比如Python的大整数），就能正常计算

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