固定数量重复元素的排列与索引双向转换算法求询

问题描述 #

假设你有4个red球、2个blue球和1个green球，共7个球。由于同色球无法区分，总排列数为(7!)/(4!2!1!) = 105种。

也就是说，若将red映射为0、blue映射为1、green映射为2，数组[0, 0, 0, 0, 1, 1, 2]共有105种排列方式。

更一般地，设有n个球，m种类型，第k种类型的球有nₖ个（1 ≤ k ≤ m），且n₁+n₂+…+nₖ = n，则总排列数为(n!)/(n₁!*n₂!*…*nₖ!)。

是否存在一种算法，可将给定的排列数组转换为唯一的索引值，且能从该索引值还原出对应的排列数组？

约束条件 #

• 索引值必须落在0到(n!)/(n₁!*n₂!*…*nₖ!) - 1范围内。
  上述示例中，索引范围是0到104，算法需支持任意大数范围。
• 算法不得需要计算所有（或大部分）排列。
  示例仅含105种排列，但实际需支持多达30万亿种排列的场景，因此算法复杂度至关重要。

允许条件 #

不关心排列的顺序，只需保证每个排列对应唯一索引，且索引可还原为原排列。

本问题并非重复问题： #

• 以下问题仅针对无重复元素的数组（即长度为n的数组有n!种排列），而本问题允许每种元素有固定的、大于1的数量（可显著减少相同长度数组的排列数）：
  • Fast permutation -> number -> permutation mapping algorithms
  • How can I generate all permutations of length n from a set of k elements?
  • How to find the index of a k-permutation from n elements?
  • Generate one permutation from an index
• 「Coding the mathematical approach for finding index of a permutation that has repetition」虽允许元素重复，但未限定每种元素的固定数量，导致排列数大幅增加，与本问题不符。
• 「Generate permutations of indices of identical items」要求生成所有排列，而本问题需避免枚举所有排列（大规模场景下计算量过大），且其答案使用了第三方库。
• 「Find the index of a given permutation in the sorted list of the permutations of a given string」未考虑重复元素，会出现多个索引对应同一排列的情况，且仅支持排列转索引，不支持反向转换。
• 「Algorithm for finding multiset permutation given lexicographic index」仅支持索引转排列的单向操作，而本问题需要双向转换的算法。