как найти пустое место в ряду?

Question

Я полагаю, что нужно поместить группу людей (заданную во время выполнения) в двумерный массив точек, случайным образом сгруппировать их в ряд (выяснить все возможные позиции и выбрать случайным образом одну)

Для начала я хочу сначала попробовать в массиве

, если у меня есть массив пятен размером 10, как показано ниже

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

, чтобы поместить 2 человек

Есть конкретный алгоритм для решения этой проблемы?Спасибо за любую помощь!

Answer 1

в питоне:

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

Я буду использовать 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

пятна [занято, «Дельта», «Эхо», занято, занято, занято, «Альфа», «Браво», «Чарли», «Фокстрот»]

Answer 3

Псевдокод:

//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, вы должны проверить полный блок в позиции, указанной в псевдокоде