3

我试图弄清楚如何在给定以下信息的情况下找到所有组合：

我从一个 JSON 数据集开始：

var choices = { 1: {'Q': 100, 'R': 150, 'W' : 250, 'T', 30},
                2: {'Q': 90, 'R': 130, 'W' : 225, 'T', 28},
                3: {'Q': 80, 'R': 110, 'W' : 210, 'T', 25},
                4: {'Q': 70, 'R': 90, 'W' : 180, 'T', 22},
                5: {'Q': 60, 'R': 70, 'W' : 150, 'T', 18},
                6: {'Q': 50, 'R': 50, 'W' : 110, 'T', 15},
                7: {'Q': 40, 'R': 30, 'W' : 80, 'T', 11},
                8: {'Q': 30, 'R': 25, 'W' : 50, 'T', 8},
                9: {'Q': 20, 'R': 10, 'W' : 25, 'T', 5},
                10: {'Q': 10, 'R': 5, 'W' : 15, 'T', 3}
              };

我想弄清楚的是如何获取这个数据集，并在为每一行选择“Q”、“R”、“W”或“T”元素时生成所有可能的组合。

所以我希望我的最终结果是这样的

var allChoices = { 0: {1: {'Q': 100},
                       2: {'R': 130},
                       3: {'W' : 210},
                       4: {'W' : 180},
                       5: {'T', 18},
                       6: {'R': 50,},
                       7: {'Q': 40,},
                       8: {'T', 8},
                       9: {'R': 10},
                      10: {'W' : 15},
                     },
                 1: {...},
                 ...
                 1048576: {...}

              };

我使用 JSON 是因为我认为它是最容易可视化的，但有谁知道我如何在 c# 中实现这一点？

如果这还不够清楚，请告诉我，我很难弄清楚如何准确地问这个问题。

4

4 回答 4

3

您正在寻找的是 10 个数组的笛卡尔积（我认为它更恰当地称为 10 元笛卡尔积）。Eric Lippert 写了一篇很好的（而且非常高级的）文章，在这里为任意数量的数组执行此操作：http: //ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

它的结果是我认为以下功能会做你想要的：

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
  return sequences.Aggregate(
    emptyProduct,
    (accumulator, sequence) =>
      from accseq in accumulator
      from item in sequence
      select accseq.Concat(new[] {item}));
}

您的情况下的输入是您的 10 个数组的数组。输出将是一个 ienumerable，它将在每一步返回一个包含十个项目的 ienumerable。您基本上会遍历该函数的输出以获取所有可能的排列。

于 2012-02-16T16:51:55.573 回答
3

这是一个以 4 为基数的 10 位数字。

class Program
{
    static void Main(string[] args)
    {
        int baseN = 4;
        int maxDigits = 10;
        var max = Math.Pow(baseN, maxDigits);
        for (int i = 0; i < max; i++)
        { // each iteration of this loop is another unique permutation
            var digits = new int[maxDigits];
            int value = i;
            int place = digits.Length - 1;
            while (value > 0)
            {
                int thisdigit = value % baseN;
                value /= baseN;
                digits[place--] = thisdigit;
            }

            int choice = 0;
            foreach (var digit in digits)
            {
                choice ++;
                //Console.Write(digit);
                switch (digit)
                {
                    case 0: break; //choose Q from choice
                    case 1: break; //choose R from choice
                    case 2: break; //choose W from choice
                    case 3: break; //choose T from choice
                }
            }
            //Console.WriteLine();
            // add it to your list of all permutations here
        }
        Console.WriteLine("Done")
        Console.ReadLine();
    }
}
于 2012-02-16T16:29:38.617 回答
2

这是使用深度优先递归的方法。在我的机器上运行大约需要 3 秒。如果您有 5 列而不是 4 列，则通过将 PAIRCOUNT 更改为 5 并根据需要添加其他 Pairs，这也适用于任意大小的配对。

    void Main()
    {
        var OriginValues = new List<KeyValuePair<char, int>>();
        OriginValues.Add(new KeyValuePair<char, int>('Q', 100));
        OriginValues.Add(new KeyValuePair<char, int>('R', 150));
        OriginValues.Add(new KeyValuePair<char, int>('W', 250));
        OriginValues.Add(new KeyValuePair<char, int>('T', 30));

        OriginValues.Add(new KeyValuePair<char, int>('Q', 90));
        OriginValues.Add(new KeyValuePair<char, int>('R', 130));
        OriginValues.Add(new KeyValuePair<char, int>('W', 225));
        OriginValues.Add(new KeyValuePair<char, int>('T', 28));

        OriginValues.Add(new KeyValuePair<char, int>('Q', 80));
        OriginValues.Add(new KeyValuePair<char, int>('R', 110));
        OriginValues.Add(new KeyValuePair<char, int>('W', 210));
        OriginValues.Add(new KeyValuePair<char, int>('T', 25));

        ///... and the other 7

        var AllPermutation = new List<List<KeyValuePair<char, int>>>();
        Recurse(OriginValues, ref AllPermutation);

        //all results will be in AllPermutation now

    }

    const int PAIRCOUNT = 4;
    void Recurse(List<KeyValuePair<char, int>> OriginValues, ref List<List<KeyValuePair<char, int>>> result, List<KeyValuePair<char, int>> itemset = null)
    {
        itemset = itemset ?? new List<KeyValuePair<char, int>>();
        var temp = new List<KeyValuePair<char, int>>(itemset);
        if (itemset.Count == OriginValues.Count / PAIRCOUNT)
        {
            result.Add(temp);
            return;
        }
        for (int x = 0; x < PAIRCOUNT; x++)
        {
            temp.Add(OriginValues[itemset.Count * PAIRCOUNT + x]);
            Recurse(OriginValues, ref result,  temp);
            temp = new List<KeyValuePair<char, int>>(itemset);
        }

    }
于 2012-02-16T17:00:03.330 回答
1

看看这个：Linq 中的组合生成器

另一个没有 LINQ 的解决方案，假设你每行只做 4 件事，最简单的事情就是暴力破解它并执行嵌套的 foreach 循环。

foreach ( choice in allChoices )
{
    foreach ( choice in allChoices )
    {
        foreach ( choice in allChoices )
        {
            foreach ( choice in allChoices )
            {
                // combine and add to a collection
            }
        }
    }
}

编辑：添加对象以在 foreach 循环中循环

于 2012-02-16T16:14:57.863 回答