如何找到连续的空位？

Question

我假设将一群人（在运行时给出）放入一个二维点数组中，随机分组在一起（找出所有可能的位置并随机选择一个）

首先，我想尝试首先是一个数组，

如果我有一个大小为 10 的点数组，如下所示，

spots[occupied,open,open,occupied,occupied,occupied,open,open,open,open]

可以放置 2 个人

，有没有特定的算法可以解决此类问题？ 感谢您的帮助！

Answer 1

在 python 中：

seats =["occupied","open","open","occupied","occupied","occupied","open","open","open","open"]

def empty(seats,index,count):
  if count == 0:
     return True
  else:
     return (seats[index] == "open") & empty(seats,index+1,count-1)

def findEmpty(seats,count):
  result = []
  for (i=0;i<seats.size-count+1,i++)
    if empty(seats,i,count):
      result.append(<list of consecutive numbers from i to i+count>)
  return result


print findEmpty(seats,2)  

>>>[[1, 2], [6, 7], [7, 8], [8, 9]]

这是另一种方法，它更有效一些：

seats = ["occupied","open","open","occupied","occupied","occupied","open","open","open","open"]
//counts the number of consecutive free seats starting at position index
def countEmpty(seats,index):
    if index >= len(seats) or seats[index] == "occupied":
        return 0
    return 1 + countEmpty(seats,index+1)

def findEmpty(seats,count):
    result = []
    i = 0
    while i < len(seats)-count+1:
       c = countEmpty(seats,i)
          if c>=count:
             for (j=i;j<i+c-count+1;j++):
                result.append(<list of consecutive numbers from j to j+count>)
       i += 1 + c
    return result

print findEmpty(seats,2)
>>>[[1, 2], [6, 7], [7, 8], [8, 9]]

最后，如果您确实选择使用 python，您可以在一行中完成：

seats =["occupied","open","open","occupied","occupied","occupied","open","open","open","open"]
count = 2    
print [range(i,i+count) for i in range(len(seats)-count+1) if all([seats[j]=="open" for j in range(i,i+count)]) ]
>>> [[1, 2], [6, 7], [7, 8], [8, 9]]

Answer 2

伪代码：

//Create 2 lists of blocks, both empty: tmp and final
List tmp=new List;
List final=new List;

//Cycle the seats
for (int i=0;i<length(seats);i++) {
    //If the seat is occupied, start over
    if (seats[i]==occupied) tmp.empty();
    else {
        //Cycle existing block candidates, add free seat
        foreach (ref block in tmp) {
            block.add(seats[i])
            if (length(block)>=people_count) {
                //HEUREKA, got a fitting block: Move it to the final list
                tmp.remove(block)
                final.add(block)
            }
        }
        //Start a new block with this seat
        tmp.add(new block(seats[i]));
        //Read below for this edge case
    }
}

final 现在有块了。

如果允许 people_num 为 1 的边缘情况，则必须在伪代码中指示的位置检查完整的块

Answer 3

我将使用 Mathematica 代码，但我相信您可以遵循逻辑。

首先找到

dat = spots[occupied, open, open, occupied, occupied, occupied, open, open, open, open];
fill = {"Alpha", "Bravo", "Charlie", "Delta", "Echo", "Foxtrot"};

列表的随机排列fill（在StackOverflow上很容易找到算法）：

randomfill = RandomSample @ fill

{“Delta”、“Echo”、“Alpha”、“Bravo”、“Charlie”、“Foxtrot”}

然后将函数“映射”到 spots 列表的每个元素上，并且如果该元素是open返回randomfill列表中的下一个值，否则返回不变的元素：

i = 1;
If[# === open, randomfill[[i++]], #] & /@ dat

地点[已占领、“Delta”、“Echo”、已占领、已占领、已占领、“Alpha”、“Bravo”、“Charlie”、“Foxtrot”]