logo标签列表

C#中的排列算法

c#algorithmpermutationcombinatorics
4

我正在为需要编写的算法苦苦挣扎。我正在使用C＃。

假设我有一个List<Bag>和一个List<Lunch>。 我需要编写一个算法，该算法将枚举所有袋子中午餐的排列组合。

例如，假设有3个午餐和2个袋子：

// Permutation 1
Bag 1, Lunch 1
Bag 2, Lunch 1

// Permutation 2
Bag 1, Lunch 1
Bag 2, Lunch 2

// Permutation 3
Bag 1, Lunch 1
Bag 2, Lunch 3

// Permutation 4
Bag 1, Lunch 2
Bag 2, Lunch 1

// Permutation 5
Bag 1, Lunch 2
Bag 2, Lunch 2

// Permutation 6
Bag 1, Lunch 2
Bag 2, Lunch 3

// Permutation 7
Bag 1, Lunch 3
Bag 2, Lunch 1

// Permutation 8
Bag 1, Lunch 3
Bag 2, Lunch 2

// Permutation 9
Bag 1, Lunch 3
Bag 2, Lunch 3

这两个排列顺序袋子1午餐1和袋子2午餐2以及袋子1午餐2和袋子2午餐1是不同的，因为袋子的容量不同，所以它们都需要被枚举。

袋子和午餐的数量可以是任意数字。

我创建了一个名为BagLunch的类，其中包含一个袋子和午餐对。上面提到的示例列表将存储在List<BagLunch>中。

谢谢。

1
我不理解你的例子。有几行列出了“袋子1，午餐1”。排列中重复的规则是什么？ - Ted Hopp
抱歉，我添加了间距。每个组是一个排列。 - user1002358
我认为没有重复吧？你可以把午餐1放在袋子1里，午餐2放在袋子2里；或者你可以把午餐2放在袋子1里，午餐1放在袋子2里。这是两种不同的排列组合。 - user1002358
感谢你添加了作业标签zmbq，但这并不是作业。 - user1002358
@Marty 你难道不觉得这种问题在实际问题中可能真的会出现吗？ - user1002358
你能否详细说明一下... - Sam I am says Reinstate Monica
4个回答
4

在LINQ中使用交叉连接：

var qry = from bag in bags
          from lunch in lunches
          select new BagLunch 
          { Bag=bag, Lunch=lunch};
var baglunches = qry.ToList();

编辑：
您需要修改选择子句以处理BagLunch类的结构。

1
好的答案；OP将不得不按“袋子”对结果进行分组，然后交叉连接这些组。 - Kirk Broadhurst
我对LINQ还很陌生，但我刚刚运行了你的示例。它给出了与嵌套的for或foreach相同的结果：B1L1，B1L2，B1L3，B2L1，B2L2，B2L3。这不是我需要的 :( - user1002358
那样做可以，但感觉有点像作弊，即使这不是作业。 - zmbq
1
@user1002358 我猜我误解了你的需求。这会给你所有背包和午餐的排列组合。对于一个2x3的集合，只有6种排列组合。 - Randolpho
这是带重复的排列。OP中的示例输出显示了这一点。因此有9种可能性。这个想法是两个带着袋餐的人可以吃同样的午餐（例如，两个人都可以吃花生酱三明治）。如果没有重复，那么只会有6种可能性。 - Mark Wilkins
1
让k = #袋子和n = #午餐盒数。如果允许每个午餐只“分配”给一个袋子，那么有n!/(n-k)!种可能性。在这里的运算允许每个午餐可以被分配到多个袋子中，因此有k^n种可能性。 - amit
2
如果你允许重复[一个午餐可以在两个袋子里]，如示例所示，你有#bags^#lunches种可能性。
每个袋子都有自己独特的“选择”，要放哪个午餐。 要生成这些可能性-只需为一个袋子“选择”午餐，并递归调用算法。对于每个午餐重复此过程。
生成它们的伪代码：
generateAll(bags,lunches,sol):
  if (bags is empty):
      print sol
      return
  bag <- bags.first
  bags.remove(bag)
  for each lunch in lunches:
     sol.append(BagLunch(bag,lunch)
     generateAll(bags,lunches,sol)
     sol.removeLast()
0

我有一个方法可以重新创建你上面的例子。实际上，这种方法是将袋子看作数字的位置...因为如果你看一下你的例子，你可以把它读成11、12、13、21、22、23。然后就是将其转换为Lunch.Count基数。此外，我从这里偷了一个方法：https://dev59.com/vkXRa4cB1Zd3GeqPpzQi#95331，用于将任何基数转换为十进制，但据说它没有经过测试，所以你可能需要构建更强大的东西。最后，我没有进行任何边缘条件测试，因此输入0个袋子可能会产生意想不到的结果。这就是我想出来的。

class Program
{
    static List<Bag> bags = new List<Bag>();
    static List<Lunch> lunches = new List<Lunch>();

    static void Main(string[] args)
    {
        lunches.Add(new Lunch() { Num = 1 });
        lunches.Add(new Lunch() { Num = 2 });
        lunches.Add(new Lunch() { Num = 3 });
        bags.Add(new Bag() { Num = 1 });
        bags.Add(new Bag() { Num = 2 });

        int count = 0;
        while (count < Math.Pow(lunches.Count, bags.Count))
        {
            Console.WriteLine("Permutation " + count);
            string countNumber = ConvertToBase(count, lunches.Count).PadLeft(bags.Count,'0');
            for (int x = 0; x < bags.Count; x++)
            {
                Console.WriteLine(bags[x] + " " + lunches[Convert.ToInt32((""+countNumber[x]))]);

            }
            Console.WriteLine("");
            count++;
        }
        Console.ReadLine();

    }

    static string ConvertToBase(int value, int toBase)
    {
        if (toBase < 2 || toBase > 36) throw new ArgumentException("toBase");
        if (value < 0) throw new ArgumentException("value");

        if (value == 0) return "0"; //0 would skip while loop

        string AlphaCodes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        string retVal = "";

        while (value > 0)
        {
            retVal = AlphaCodes[value % toBase] + retVal;
            value /= toBase;
        }

        return retVal;
    }

}

class Lunch
{
    public int Num { get;set;}
    public override string  ToString()
    {
         return "Lunch " + Num;
    }

}
class Bag
{
    public int Num { get;set;}   

    public override string  ToString()
    {
         return "Bag " + Num;
    }
}

以及产生的输出结果：

Permutation 0
Bag 1 Lunch 1
Bag 2 Lunch 1

Permutation 1
Bag 1 Lunch 1
Bag 2 Lunch 2

Permutation 2
Bag 1 Lunch 1
Bag 2 Lunch 3

Permutation 3
Bag 1 Lunch 2
Bag 2 Lunch 1

Permutation 4
Bag 1 Lunch 2
Bag 2 Lunch 2

Permutation 5
Bag 1 Lunch 2
Bag 2 Lunch 3

Permutation 6
Bag 1 Lunch 3
Bag 2 Lunch 1

Permutation 7
Bag 1 Lunch 3
Bag 2 Lunch 2

Permutation 8
Bag 1 Lunch 3
Bag 2 Lunch 3
0

所以你想在保持顺序的情况下，从n个午餐中选择k个袋子？我希望你能假设k≤n，否则你会被空袋子困住...

我不想完全破坏你的作业，所以我只会指出正确的方向。这需要使用递归。首先选择第一个袋子的午餐，然后选择剩下的k-1个袋子的午餐。当只剩下一个袋子时，选择剩余的每个午餐，直到完成。

编辑：

哦，一个午餐可以同时存在于两个袋子中。所以是n^k。最简单的方法是使用上面建议的LINQ交叉连接，但感觉有点像作弊。相反，只需创建一个K元素的整数数组，用零填充它，并开始将一添加到最右边的元素。当它达到N时，将其重置为零并将一传递到下一个元素。您只是在N进制下计算K位数字。每次迭代后，您都可以输出袋子分配。

在这个例子中，午餐是可替换的 - 它们可以用于多个袋子。 - Kirk Broadhurst
没错。我可以有10个袋子和1个午餐盒。在这种情况下，只有一种排列方式：所有10个袋子都装有午餐盒1。 - user1002358
1
你应该真的停止称它为排列。这是一种组合。 - zmbq
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接