构建组合矩阵

本文关键字：组合 构建 | 更新日期: 2023-09-27 18:01:13

我相信这个问题已经被问了一百万次了，但当我搜索时，所有的例子都不太合适，所以我想我无论如何都应该问它。

我有两个数组，每个数组总是包含6个项目。例如：

string[] Colors=
    new string[] { "red", "orange", "yellow", "green", "blue", "purple" };
string[] Foods=
    new string[] { "fruit", "grain", "dairy", "meat", "sweet", "vegetable" };

在这两个数组之间，有36种可能的组合（例如"红色水果"、"红色谷物"）。

现在，我需要将这些值进一步分组为六个唯一值。

例如：

meal[0]=
    new Pair[] { 
        new Pair { One="red", Two="fruit" }, 
        new Pair { One="orange", Two="grain" }, 
        new Pair { One="yellow", Two="dairy" }, 
        new Pair { One="green", Two="meat" }, 
        new Pair { One="blue", Two="sweet" }, 
        new Pair { One="purple", Two="vegetable" } 
    };

在哪

Pair[][] meal;

在我的"膳食"列表中，任何元素都不能重复。因此，只有一个"红色"项目，和一个"肉类"项目，等等。

我可以很容易地根据前两个数组创建对，但我对如何最好地将它们分组为独特的组合一无所知。

构建组合矩阵

好的，您想要一个包含所有720个可能序列的序列。这有点棘手，但它是可以做到的。

基本思路与我之前的回答相同。在这个答案中，我们：

  • 随机生成一个排列
  • 用未静音的第一阵列压缩已排列的第二阵列
  • 从查询中生成了一个数组

现在我们将做同样的事情，只是我们将产生所有的排列，而不是随机产生排列。

从获取此库开始：

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

好的，我们需要对六个项目进行所有排列：

Permutations<string> permutations = new Permutations<string>(foods);

我们想对每个排列做什么？我们已经知道了。我们想首先用颜色数组压缩它，把它变成一个成对的序列，然后把它变成数组。相反，让我们把它变成List<Pair>，因为，相信我，它会更容易。

IEnumerable<List<Pair>> query = 
    from permutation in permutations
    select colors.Zip(permutation, (color, food)=>new Pair(color, food)).ToList();

现在我们可以将该查询转换为结果列表；

List<List<Pair>> results = query.ToList();

我们完了。我们有一个包含720个项目的列表。每个项目都是一个包含6对的列表。

显然，繁重的工作是由库代码完成的；它上面的查询非常简单。

（一段时间以来，我一直想写一篇关于如何在LINQ中生成排列的博客文章；我可能会以这个为例！）

有720种可能的组合可以满足您的需求。从您的问题中还不清楚您是想枚举所有720还是随机选择一个或什么。我假设是后者。

更新：根据评论，这种假设是不正确的。我将开始一个新的答案。

首先，生成第二个数组的排列。你可以用菲舍尔-耶茨-克努思洗牌在原地完成；在StackOverflow上有很多这样做的例子。或者，您可以使用LINQ通过使用随机密钥进行排序来生成排列。

前一种技术即使项目数量很大也很快，但会对现有数组进行变异。第二种技术较慢，尤其是当项目数量非常大时，情况并非如此。

人们在使用第二种技术时最常见的错误是根据guid进行排序。Guid保证是唯一的，而不保证是随机的

无论如何，生成一个查询，当执行时，它会排列第二个数组：

Random random = new Random();
IEnumerable<string> shuffled = from food in foods 
                               orderby random.NextDouble() 
                               select food;

其他一些注意事项：

  • 请记住，查询表达式的结果是查询，而不是结果集。直到你真正把它变成另一端的数组，排列才会发生
  • 如果在同一毫秒内创建两个Random实例，则从这两个实例中获得相同的序列
  • 随机是伪随机的，而不是真正的随机
  • 随机不是线程安全的

现在你可以将你的排列序列压缩到第一个数组：

IEnumerable<Pair> results = colors.Zip(shuffled, (color, food)=>new Pair(color, food));

同样，这仍然是一个表示将两个序列压缩在一起的操作的查询。除了构建一些查询之外，什么都没有发生。

最后，把它变成一个数组。这实际上执行了查询。

Pair[] finalResults = results.ToArray();

很简单。

根据请求，我将具体说明如何看待排序方面的问题。我知道，由于C#是一种更高级别的语言，因此有大量快速简单的库和对象可以用来将其简化为最少的代码。这个答案实际上是试图通过实现排序逻辑来解决问题。

最初读这个问题时，我想起了整理一副卡片。这两个数组非常类似于西装数组和面值数组。由于解决洗牌的一种方法是随机化数组，然后选择一张两者结合的牌，因此可以在这里应用相同的逻辑。

排序是一种可能的解决方案

Fisher Yates排序算法基本上循环遍历数组的所有索引，用随机索引交换当前索引。这创建了一个相当有效的排序方法。那么，这如何适用于手头的问题呢？一种可能的实现方式是…

    static Random rdm = new Random();
    public string[] Shuffle(string[] c)
    {
        var random = rdm;
        for (int i = c.Length; i > 1; i--)
        {
            int iRdm = rdm.Next(i);
            string cTemp = c[iRdm];
            c[iRdm] = c[i - 1];
            c[i - 1] = cTemp;
        }
        return c;
    }

来源：Fisher Yates Shuffle

上面的代码对字符串数组中的值的位置进行随机化。如果您将Colors和Food数组传递到此函数中，您将通过引用这两个数组的特定索引来获得Pairs的唯一配对。

由于数组是混洗的，索引0,1,2等处的两个数组的配对是唯一的。然而，这个问题要求创建Pairs。然后，应该创建一个Pair类，该类在Colors和Foods的特定索引处接受一个值。即…颜色[3]和食品[3]

 public class Pair
{
     public string One;
     public string Two;
     public Pair(string m1, string m2)
     {
         One = m1;
         Two = m2;
     }
}

由于我们已经对数组和一个包含唯一配对的类进行了排序，所以我们只需创建餐数组并用Pairs填充它。

如果我们想创造一对新的情侣，我们会。。。

Pair temp = new Pair(Colors[0],Foods[0]);

有了这些信息，我们最终可以填充膳食数组。

    Pair[] meal = new Pair[Colors.Length - 1];
    for (int i = 0; i < Colors.Length - 1; i++)
    {
        meal[i] = new Pair(Colors[i],Foods[i]);
    }

这部分代码创建膳食数组，并通过Colors的长度定义其索引数。然后，代码循环遍历Color值的总数，同时创建新的成对组合并将其放入膳食中。这种方法假设数组的长度相同，可以很容易地检查最小的数组。

完整代码

private void Form1_Load(object sender, EventArgs e)
        {
            string[] Colors = new string[] { "red", "orange", "yellow", "green", "blue", "purple" };
            string[] Foods = new string[] { "fruit", "grain", "dairy", "meat", "sweet", "vegetable" };
            Colors = Shuffle(Colors);
            Foods = Shuffle(Foods);
            Pair[] meal = new Pair[Colors.Length - 1];
            for (int i = 0; i < Colors.Length - 1; i++)
            {
                meal[i] = new Pair(Colors[i],Foods[i]);
            }
        }
        static Random rdm = new Random();
        public string[] Shuffle(string[] c)
        {
            var random = rdm;
            for (int i = c.Length; i > 1; i--)
            {
                int iRdm = rdm.Next(i);
                string cTemp = c[iRdm];
                c[iRdm] = c[i - 1];
                c[i - 1] = cTemp;
            }
            return c;
        }
    }
    public class Pair
    {
         public string One;
         public string Two;
         public Pair(string m1, string m2)
         {
             One = m1;
             Two = m2;
         }
     }

-原始帖子-

您可以简单地打乱数组。这将允许使用相同的方法来填充膳食，但结果不同。有一篇关于Fisher Yates shuffle Here 的帖子

相关文章：