时间戳

首页 > 解决方案 > 在没有递归函数的 C# 中计算组合

c# - 在没有递归函数的 C# 中计算组合

问题描述

我想计算所有可能的组合，但我不想在 C# 中使用递归函数只是一些简单的代码？

这是示例：

                     col1     col2   col3
       valueinf=      5        6      7
       valuesup=     10       20     30

我想要这个结果：

        res1 = 5+6+7
        res2 = 5+6+30
        res3 = 5+20+7
        res4 = 5+20+30
        res5 = 10+6+7
        res6 = 10+6+30
        res7 = 10+20+7
        res8 = 10+20+30

Colonne 的数量是可变的，但我总是有 2 条线，一条下线，一条上线。我不知道如何开始算法。一些帮助将不胜感激刚刚开始

标签： c#algorithmcombinations

解决方案

好吧，你必须循环：

using System.Linq;

...

private static IEnumerable<int> Sums(IEnumerable<int[]> columns) {
  if (columns is null)
    throw new ArgumentNullException(nameof(columns));

  int[][] data = columns.ToArray();
  int[] pos = new int[data.Length];

  do {
    yield return Enumerable.Range(0, data.Length).Sum(i => data[i][pos[i]]);

    for (int i = pos.Length - 1; i >= 0; --i)
      if (pos[i] == data[i].Length - 1)
        pos[i] = 0;
      else {
        pos[i] += 1;

        break;
      }
  }
  while (!pos.All(p => p == 0));
}

如果你想打印公式，同样的想法：

private static IEnumerable<string> Formulae(IEnumerable<int[]> columns) {
  if (columns is null)
    throw new ArgumentNullException(nameof(columns));

  int[][] data = columns.ToArray();
  int[] pos = new int[data.Length];

  do {
    yield return string.Join("+", Enumerable
      .Range(0, data.Length).Select(i => data[i][pos[i]]));

    for (int i = pos.Length - 1; i >= 0; --i)
      if (pos[i] == data[i].Length - 1)
        pos[i] = 0;
      else {
        pos[i] += 1;

        break;
      }
  }
  while (!pos.All(p => p == 0));
}

演示：

List<int[]> columns = new List<int[]>() {
  new int[] {5, 10},
  new int[] {6, 20},
  new int[] {7, 30}, 
};

var sums = Sums(columns);
var formulae = Formulae(columns);

Console.WriteLine(string.Join(Environment.NewLine, sums
  .Select((v, i) => $"res{i+1} = {v}")));

Console.WriteLine();

Console.WriteLine(string.Join(Environment.NewLine, formulae
  .Select((v, i) => $"res{i+1} = {v}")));

结果：

res1 = 18
res2 = 41
res3 = 32
res4 = 55
res5 = 23
res6 = 46
res7 = 37
res8 = 60

res1 = 5+6+7
res2 = 5+6+30
res3 = 5+20+7
res4 = 5+20+30
res5 = 10+6+7
res6 = 10+6+30
res7 = 10+20+7
res8 = 10+20+30

编辑：要找到最合适的，您可以利用相同的原则：

private static (int[] pos, int diff, string formula) BestFit(int target, IEnumerable<int[]> columns) {
  if (columns is null)
    throw new ArgumentNullException(nameof(columns));

  int[][] data = columns.ToArray();
  int[] pos = new int[data.Length];

  int bestDiff = -1;
  int[] bestPos = null;

  do {
    int diff = Math.Abs(target - Enumerable.Range(0, data.Length).Sum(i => data[i][pos[i]]));

    if (diff < bestDiff || bestPos == null) {
      bestPos = pos.ToArray();
      bestDiff = diff;
    }

    for (int i = pos.Length - 1; i >= 0; --i)
      if (pos[i] == data[i].Length - 1)
        pos[i] = 0;
      else {
        pos[i] += 1;

        break;
      }
  }
  while (!pos.All(p => p == 0));

  return (
    bestPos,
    bestDiff,
    string.Join("+", Enumerable.Range(0, data.Length).Select(i => data[i][bestPos[i]]))
  );  
}

演示：

  int[][] data = new int[][] {
    new int[] {5, 10},
    new int[] {6, 20},
    new int[] {7, 30},
  };

  var fit = BestFit(20, data);

  Console.Write($"delta = {fit.diff}; formula = {fit.formula}");

结果：

  delta = 2; formula = 5+6+7

推荐阅读