c# 如何将几个数字进行搭配相加，得出全排列组合

Question

比如我这里有4个数字：2、3、4、6

我需要用随便几个数字搭配相加得出结果为全排列若干组合，请问如何写这样的代码？

2+3=5
2+4=6
2+6=12
2+3+4=9
2+3+4+6=15
2+3+6=11
2+4+6=12

3+4=7
3+6=9
3+4+6=13

4+6=10
我题目写的不太对，应该是：得到这4个数字的全排列相加

也就是得到各种排列组合之和。

（注意效率，可能数据会达到几千个）

Answer 1

 

  static int[] number;

  static int[] result;

  /// <summary>

  /// 应用程序的主入口点。

  /// </summary>

  [STAThread]

  static void Main(string[] args)

  {

   number = new int[] {2,3,4,6};

   result = new int[number.Length];

   Backtrace(0);

   System.Console.Read();

  }

  static void Backtrace(int i)

  {

   if (i >= number.Length)

   {

    //没有数字可选

    return;

   }

   result[i] = 1; //选中当前数字

   PrintResult(); //输出结果

   Backtrace(i+1); //选择下一数字

   result[i] = 0; //剔除当前数字   

   Backtrace(i+1); //选择下一数字

  }

  static void PrintResult()

  {

   int count = 0;

   int total = 0;

   string msg = "";

   for (int i = 0; i < result.Length; i++)

   {

    count += result[i];

    if (result[i] == 1)

    {

     if (count > 1)

     {

      msg += "+";

     }

     total += number[i];

     msg += number[i];

    }

   }

   if (count > 1)

   {

    System.Console.WriteLine(msg + "=" + total);

   }

  }

 

 

Answer 2

首先，你这个是组合，而不是排列
如果只求和：那么对于有n个数字的数组，2一共出现了n-1 + C 2/n-1 + C 3/n-1 + .... C n-2/n-1 + 1次，同理，其他数字在总和的算式中出现的次数和第一个数字2是一样的
你只需要计算

C 2/n-1 + C 3/n-1 + .... C n-2/n-1 + 1

将其和你输入的数组的和相乘就得到最终的值

你的例子中，和= (2+3+4+6)* (3 + C2/3+1) = 15*7 = 105

算法可能还可以简化， 不知道能不能简化成排列 A X/X的形式

至于代码就你自己写了，这道是纯算法题，和C++还是C#没什么大关系，排列组合的公式中学也都应该学到过，你自己搞定吧

追问

可能是我没说得清楚。我需要的是每一组的排列求和，而不是总的求和。不过还是要感谢你！

追答

和FIBO数列一样，如果要追求遇到较大阶数的执行速度，递归这条路就死了（FIBO数列还有巧可取）
但你的题，如果要列出每一个组合，并且要求和
那么对1000个数字来说，每个数字都有两种选择（出现和不出现）
也就说2^1000种组合，这个数量级在10^301
什么地方的题？ 这个题目如果没有描述错的话
和汉诺塔一样，阶数高了，运行到你死了也没有结果

追问

说的很对，估计无解了。必须加上其他条件（比如找到的数据就不参加运算）来减少数据量

Answer 3

/// <summary>
/// 计算该数组从第m个数开始的所有组合
/// </summary>
/// <param name="s">数组</param>
/// <param name="m">从第m个数开始计算</param>
/// <param name="k">起始数据位第k个数</param>
static void CaM(int[] s, int m, int k)
{
for (int i = m; i < s.Length; i++)
{
int sum = 0;
for (int j = k; j < m; j++)
{
sum += s[j];
//System.Console.Write(s[j] + "+");
}
System.Console.Write("第" + k + "到" + (m - 1) + "+");
sum += s[i];
System.Console.WriteLine(s[i] + "=" + sum);
}
}
static void Main(string[] args)
{
int[] aaa = new int[500];//测试数组
for (int i = 0; i < aaa.Length; i++)
{
aaa[i] = i + 1;
}

for (int i = 0; i < aaa.Length; i++)//起始数据
{
for (int j = i + 1; j < aaa.Length; j++)//组合计算开始数据
{
CaM(aaa, j, i);
}
}
}

Answer 4

路过

追问

感谢大伙的回复！特别是yangquneng！计算是出来了，可惜加大数据（2000个数据）程序就死了。还有什么提高效率的方法么？谢谢！