NxN网格上基于物品ID的可复现随机放置功能实现咨询

这类通用算法实现问题完全符合Stack Overflow的发布规范，无需跳转其他板块。如果后续涉及纯理论算法复杂度分析、可计算性等偏学术属性的问题，可转向Computer Science板块，你当前的需求属于工程实现范畴，直接在本站发布即可。

你的需求核心是实现ID绑定的确定性伪随机映射，保证相同ID每次生成的坐标一致，同时避免不同ID的坐标冲突，以下提供两种适配不同场景的可落地方案：

方案1：轻量哈希映射（适合 M << N² 的场景） #

适用于物品数量远小于网格总容量的场景，实现简单、性能损耗极低：

• 预定义固定全局盐值，避免哈希碰撞概率过高或分布不均
• 对单个物品ID做加盐哈希，将哈希结果映射为0 ~ N²-1之间的整数索引
• 将索引转换为网格坐标：x = 索引 % N，y = 索引 // N
• 若出现不同ID映射到同一坐标的碰撞问题，用线性探测法顺延寻找下一个空位，探测步长可直接固定为1，也可以用ID哈希生成，保证每次探测路径完全固定
• 若要求输入ID数组的顺序变化时，单个ID的位置也保持不变，可提前将所有ID排序后再生成位置，最终按原始输入顺序返回即可

示例代码（Python）：

def batch_get_positions(item_ids: list[int], N: int, salt: int = 0x5f3759df) -> list[tuple[int, int]]:
    used_pos = set()
    result = []
    # 先排序ID，保证输入顺序不影响单个ID的最终位置
    sorted_ids = sorted(item_ids)
    pos_map = {}
    for item_id in sorted_ids:
        hash_val = (item_id ^ salt) % (N * N)
        # 线性探测解决碰撞
        while hash_val in used_pos:
            hash_val = (hash_val + 1) % (N * N)
        used_pos.add(hash_val)
        pos_map[item_id] = (hash_val % N, hash_val // N)
    # 按原始输入顺序返回坐标
    for item_id in item_ids:
        result.append(pos_map[item_id])
    return result

方案2：确定性洗牌映射（适合 M 接近 N² 或要求严格无碰撞的场景） #

如果物品数量较多、碰撞概率高，或完全不能接受坐标冲突，可采用固定种子的费雪耶茨洗牌方案：

• 将所有物品ID的异或和作为伪随机数生成器（PRNG）的固定种子，保证同一组ID的洗牌结果完全一致
• 生成0 ~ N²-1的全量网格索引数组，用上述种子对数组做费雪耶茨洗牌
• 将排序后的ID按顺序匹配洗牌后的索引，再转换为网格坐标即可

示例代码（Python）：

import random

def batch_get_positions_shuffle(item_ids: list[int], N: int) -> list[tuple[int, int]]:
    # 生成固定种子，同一组ID种子完全一致
    seed = 0
    for item_id in item_ids:
        seed ^= item_id
    rng = random.Random(seed)
    # 生成全量网格索引并做确定性洗牌
    indices = list(range(N * N))
    rng.shuffle(indices)
    # 排序ID保证分配规则不受输入顺序影响
    sorted_ids = sorted(item_ids)
    pos_map = {}
    for idx, item_id in enumerate(sorted_ids):
        grid_idx = indices[idx]
        pos_map[item_id] = (grid_idx % N, grid_idx // N)
    # 按原始输入顺序返回
    return [pos_map[item_id] for item_id in item_ids]

注意：该方案缺点是当N非常大（比如N>1e4，总网格数超过1e8）时，全量索引数组会占用过多内存，这种场景下优先选择方案1。

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