给定数字数组生成长度不超过数组长度的可重复数字计数问题

需求说明 #

从存储数字的int数组中生成所有可能的数字，允许数字重复使用，生成数字的长度不超过数组本身的长度。

示例验证 #

• 输入数组为new int[]{1,2}时，生成结果如下：

1
2
11
21
12
22

count =6

• 输入数组为new int[]{1,2,3}时，生成结果总数为39。

疑问 #

当前不确定元素更多的输入数组计算结果是否正确，是否有对应的数学计算公式可以直接算出总数，已知n!阶乘公式不适用于该场景。

现有C#实现代码 #

class HelloWorld {
static void Main() {
    var output =  GenerateAllCombinations(new int[] {1,2,3});
    foreach(var o in output )
    {
     Console.WriteLine(o);
    }
     Console.WriteLine(output.Count);
}

public static HashSet<string> GenerateAllCombinations(int[]  nums){
    // 将int数组转换为string数组
    var strNums=nums.Select(x =>x.ToString()).ToArray();

    var cach = new HashSet<string>(strNums);       
    var output = new HashSet<string>(strNums);

       for(int u=1;u<strNums.Length;u++)
     {
            var temp = new HashSet<string>(); 
         for(int i=0;i<strNums.Length;i++)
         {
                 foreach(var h  in cach )
                 {
                     temp.Add(h+strNums[i]);
                 }
         }
         cach=new HashSet<string>(temp);
         output.UnionWith(temp);
       }
         
    return output;
 }
}

计数公式 #

该场景属于可重复排列按长度累加计数，分两种情况：

1. 数组无重复元素：
   设数组长度为n，长度为k的可重复排列数为n^k，要求长度范围为1~n，总数为等比数列求和：

总数 = n + n² + n³ + ... + nⁿ
化简后公式为：`n*(nⁿ - 1)/(n-1)（n≠1）。
代入示例验证：

• n=2时：2+2²=6，与示例结果一致
• n=3时：3+3²+3³=39，与给出的总数完全匹配。

2. 数组有重复元素：
   先统计数组去重后的元素个数为m，将上面公式中的n替换为m即可，重复元素生成的重复字符串会被HashSet自动去重，不影响最终计数。

代码正确性说明 #

你提供的代码逻辑正确：每次迭代基于上一轮长度的所有结果，拼接每个数字生成长度+1的新结果，合并所有长度的结果后用HashSet去重，计算结果与上述公式完全匹配。

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