1

我正在编写一个程序，可以为坐在随机数量的桌子上的人计算所有可能的位置（最多可以达到 1000+）：

在此处输入图像描述

正如您在图像上看到的，黑点代表人（但在计算机中，有不同类型的人。）有两种类型的表格：蓝色和粉红色的。蓝色的可以容纳 3 人，粉红色的可以容纳 2 人。

为了让任何人坐在所有可能的位置，我可以使用 foreach 循环（其中 8 个），然后我可以运行一些额外的代码......

但是如果我添加 200 个表会怎样？那么我需要使用 200 个 foreach 循环吗？有什么方法可以更快地编码并且占用更少的空间？

我试过什么？=>

  switch(listoftables.Count)
  {
      case 1:foreach(Table table in listoftables){ //code to add people to this table}break;
      case 2: foreach(Table table1 in listoftables)
      {foreach(Table table1 in       listoftables){//code to add people to this table
   }}break;
   }

INPUT : 带有可编辑的 Table 类对象的数组（它是我自己创建的一个类） PROCESS : 上面的 List 被编辑并添加到另一个 List 对象中，在整个 foreach 过程结束后，OUTPUT 将写入所有可能的配置（谁是在另一个 List 对象中）到屏幕。

输出的示例部分：

  // List<Table> listofalltables was processed
  List<listofalltables> output

=> 在数组中包含为 [0]：首先列出 => 在数组中包含为 [0]：Table.attachedpeople（是列表）

4

3 回答 3

0

嗯，它更多的是关于数学而不是编程的问题。您正在尝试做的是创建人的排列。基本上你有 N 张桌子和 2N+2 个座位。您可以为每个座位分配一个编号。那么结果将是 2N+2 的 K-permutations 集合，其中 K 是被邀请的人数，N 是桌子的数量。

您可以使用循环来执行此操作，但您也可以递归地执行此操作。那里有可以使用的算法。例如：

生成列表所有可能排列的算法？

于 2013-09-04T12:15:12.490 回答
0

尝试递归方法。一个小例子：

public List<Table> assignToTable(List<Person> invited, List<Table> tables)
{
    if(!tables.HasRoom)
         return tables;
     else
     {
         assign(tables,invited) //code to add a person to a table
         assignToTable(invited, tables);
     }
}

如果我是你，我会创建一个对象来代表你的桌子，它有一个属性来知道是否还有一些可用的空间。这将为每个人分配一个没有任何 foreach 的表。然后在你的主目录中，你可以有一种方法可以尽可能地重新排列表格：表 1 表 2 表 3

然后

表 1 表 3 表 2 ...

表 3 表 2 表 1

并在这些列表上调用递归方法，您将拥有人们可以坐的所有可能性......

于 2013-09-04T11:51:02.587 回答
0

采用@Guigui 的回答并将其更改为我解释问题的方式。这将尝试通过递归和循环让每个人都坐在任何地方（除非人多于椅子，这是一种情况吗？我假设椅子比人多），正如您所见，复杂性将O(Math.Power(nrPeople, nrSeats))是很多形式（如果我没记错）。

Person[] peopleInvited = ....; // Avoid copying this, we are not modifying it
public void AssignToTable(int invited, SeatingArrangements tables)
{
  if(!tables.HasRoom || invited == peopleInvited.Length)
    // Do what? Print the seating?
  else
  {
    var personToSeat = peopleInvited[invited];
    foreach (var possibleSeating in tables.GetEmptyChairs()) 
    {
      // Add one person to a table somewhere, but don't modify tables
      var newArrangments = Assign(possibleSeating, personToSeat, tables) 
      AssignToTable(invited + 1, newArrangements);
    }
  }
}
于 2013-09-04T12:13:39.907 回答