как найти элемент во вложенной структуре и вернуть индекс

Question

У меня есть квадратная сетка, представленная списком списков списков - например:

grid = [[[9,3], [], [4]], 
        [[10, 1, 2], [], [11,5]],
        [[8], [7, 6], []]]

Нет ограничений на длину самых внутренних списков (ячеек). Сетка должна содержать все целые числа от 1 до n, где n - это заданное число (в данном случае 11), и каждое число может появляться только один раз.

Мне нужно выбрать случайное число от 1 до n с одинаковой вероятностью и возвращаем местоположение числа (т.е. для '3' мне понадобится сетка [0] [0] [1]). Поскольку вероятность должна быть одинаковой, я не могу просто выбрать случайную ячейку, а затем выбрать случайное число в ячейке, потому что это сместило бы выбор в сторону чисел в ячейках с меньшим числом в них.

Мой первоначальный подход состоял в том, чтобы сгенерировать случайное число в диапазоне от 1 до n, а затем просмотреть номер в сетке. Однако сетка может стать довольно большой. Что является более оптимальным подходом к этой проблеме?

Answer 1

Если вам нужно найти несколько элементов в сетке, вы можете создать карту массива, а затем просто найти случайное число в словаре местоположений. Но если вам когда-нибудь понадобится найти единственное число в сетке, вы можете просто включить его, пока не найдете.

grid = [[[9,3], [], [4]], 
        [[10, 1, 2], [], [11,5]],
        [[8], [7, 6], []]]

locations = {n: (i, j, k)
    for i in range(len(grid))
    for j in range(len(grid[0]))
    for k, n in enumerate(grid[i][j])
}

print(locations)
# {
#   1: (1, 0, 1), 
#   2: (1, 0, 2), 
#   3: (0, 0, 1), 
#   4: (0, 2, 0), 
#   5: (1, 2, 1), 
#   6: (2, 1, 1), 
#   7: (2, 1, 0), 
#   8: (2, 0, 0), 
#   9: (0, 0, 0), 
#   10: (1, 0, 0), 
#   11: (1, 2, 0)
# }

rand_int = random.choice(locations.keys())
print(rand_int, locations[rand_int])
# (10, (1, 0, 0))

Answer 2

Если я хорошо понимаю вопрос, я предлагаю использовать рекурсию для поиска различных измерений и длин в списке, а также для определения числа и его позиции:

import random

grid = [[[9,3], [], [4]], 
        [[10, 1, 2], [], [11,5]],
        [[8], [7, 6], []]]

def lookfor(num, grid, pos=[]):

    for i in range(len(grid)):

        if isinstance(grid[i], list):
            pos.append(i)
            pos2 = lookfor(num, grid[i], pos[:])
            if pos2 != pos:
                return pos2
            else:
                pos.pop()

        elif grid[i] == num:
            pos.append(i)
            return pos

    return pos

num = random.randint(1, 11)

print(num, '>', lookfor(num, grid))

Answer 3

Если у вас есть переменная глубина вложенного списка чисел, вы можете сделать следующее, код не идеален, просто чтобы продемонстрировать идею

import random

grid = [[[9,3], [], [4]], 
        [[10, 1, 2], [], [11,5]],
        [[8], [7, 6], []]]


number_index_map = dict()
def create_map(grid, index_string): # you could other useful datastructure like list or tuple for storing the index_string
    for i, val in enumerate(grid):
        if isinstance(grid[i], list):
            next_index_string = "%s,%d"%(index_string, i) if len(index_string) else "%d"%(i)
            create_map(grid[i], next_index_string)
        else:
            key = "%s,%d"%(index_string, i) if len(index_string) else "%d"%(i)
            number_index_map[val] = key

create_map(grid, "")
print(number_index_map)


#test
n = 11
random_number = random.randint(1, n)
print("random number %d " % random_number)
random_number_index = number_index_map[random_number]
print("random number index %s"%random_number_index)

# to get back the number from the index string
temp = grid
list_index = random_number_index.split(",")
print("list index ", list_index)
for i in list_index:
    temp=temp[int(i)]
print(temp)

Answer 4

Вы можете создать dict, который будет отображать ваш массив массивов следующим образом

arrays_map = {9:'1,1,1', 3: '1,1,2'...}
n = len(arrays_map.values())
random_number = arrays_map[radom.randint(0, n)]