如何找到連續的空白點？

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 
    } 
} 

最後現在有塊。

如果允許people_num爲1的邊緣的情況下，你必須在僞代碼所示的位置，以檢查是否有完整的塊

Answer 3

我將使用數學代碼，但我相信你可以遵循的邏輯。

與開始：

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

首先找到列表fill的隨機排列（這是很容易找到的StackOverflow的算法）：

randomfill = RandomSample @ fill 

{ 「三角洲」，「 Echo「，」Alpha「，」Bravo「，」Charlie「，」Foxtrot「}

然後」映射「一個函數到spots列表中的每個元素，如果該元素open從randomfill列表返回一個值，否則返回元素不變：

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

點[佔據，「三角洲」，「回聲」，佔用，佔用，佔用，「阿爾法」，「布拉沃」，「查理」，「狐步舞」]