C# 中的排列算法

Question

我正在努力解决我需要编写的算法。我正在使用 C#。

假设我有一个 List 和一个 List。 我需要编写一个算法来枚举所有袋子中午餐的所有排列。

例如，假设有 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

这两个排列 Bag 1 Lunch 1 和 Bag 2 Lunch 2 和 Bag 1 Lunch 2 和 Bag 2 Lunch 1 是不同的由于袋子的容量不同，因此需要对它们进行枚举。

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

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

谢谢。

Answer 1

在 LINQ 中使用交叉联接：

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

编辑：
您需要修改 select 子句来处理 BagLunch 类的结构。

Answer 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()

Answer 3

那么您想在保留订单的同时从 n 个（k = 袋子，n = 午餐）中检查 k 个吗？我希望你能假设 k<=n，否则你会被空袋子困住......

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

编辑：

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

Answer 4

我有一个方法可以重新创建上面的示例。该方法实际上是将袋子视为数字的位置......因为如果您查看示例，您可以将其读作 11、12、13、21、22、23。然后就是转换为基本 Lunch.Count 的问题。我还从这里偷了一个方法： https://stackoverflow.com/a/95331/483179 转换为任何基数有人提到它未经测试，因此您可能必须构建更强大的东西。最后我没有做任何边缘条件测试，所以喂入 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