在多维列表列表中选择随机位置，同时排除特定位置并避免重新创建整个数组

Question

我有关于数组的数据，每个数组都有不同的维度。此数据如下所示：

spatial_dimensions = {
  'x': 5,
  'y': 2,
  'z': 4
}

另一个数组可以这样描述：

table_dimensions = {
  'rows': 10,
  'columns': 5
}

我还有关于每个阵列中使用的插槽的数据。对于与spatial_dimensions数组相关的数据，它是这样表示的：

occupied_slots = [
  [1,2,3],
  [4,2,2],
  [1,1,1]
]

对于table_dimensions数组，它可以是

occupied_slots = [
  [2,3],
  [5,2],
  [6,1],
  [5,5]
]

我没有“完整”的数组，只有它们的维度和已占用插槽的列表

我想从数组中随机获取一个空插槽，并将其作为列表返回（该列表描述了数组中的位置）

在上述示例中，随机空时隙可以分别为[1, 2, 2]和[4, 3]

我想在纯Python中实现这一点。我不想使用numpy，因为它只会在这个特定问题上引入对我的项目的依赖

我一直在寻找一种方法来找到一个空插槽，而不必在内存中重新创建整个阵列并过滤掉占用的插槽，因为我担心这会太昂贵。特别是因为数组维度没有限制

PS——这不是我接到的任务；我试图把这个问题中所有的项目细节都抽象出来

更新

我目前正在使用此代码（基于How to iterate over this n-dimensional dataset?）：

import itertools
import random

dimensions = {
  'x': 2,
  'y': 4,
  'z': 3
}

occupied = [
  [2,3,1],
  [1,1,1]
  ]


loopover = [range(1, i + 1) for i in [dimensions[key] for key in dimensions.keys()]]
    
print(random.choice([i for i in itertools.product(*loopover) if list(i) not in occupied])) 

正如@ekhumaro所评论的，这会在将整个数组传递给random.choice()之前在内存中重新创建整个数组，这确实是我想要避免的

Answer 1

IIUC，你能随机选取元素，然后对照occupied_slots检查它们吗

import random

occupied_slots = [
  [1,2,3],
  [4,2,2],
  [1,1,1]
]

n_dim = 3
slots_list = occupied_slots

maxi = max(max(i) for i in slots_list)
mini = min(min(i) for i in slots_list)

empty = random.choices(range(mini, maxi+1), k=n_dim)
while empty in occupied_slots:
    empty = random.choices(range(mini, maxi+1), k=n_dim)

正如你所指出的，如果你有很多可能，但剩下的选择很少，这将是缓慢和不稳定的。在剩下10000个选项和1个选项的情况下，我的%%timeit平均有8秒，变化很大

但是在这种特定的情况下，找到所有可能的插槽阵列和占用的插槽之间的集合差异似乎是最简单的方法

要集成这两个选项，您可以定义一个函数，该函数具有一个可调整的阈值，用于确定何时选择一种方法而不是另一种方法，即，如果占用的插槽数量超过总可能性的k，则计算所有可能性并找出设置的差异。否则，请尝试随机选取数字，直到找到一个空插槽：

def get_empty_slot(occupied, k=.5):
    maxi = max(max(i) for i in occupied)
    mini = min(min(i) for i in occupied)
    n_dim = len(occupied[0])
    numbers = range(mini, maxi+1)
    total_possible = len(numbers) ** n_dim
    if len(occupied) / total_possible < k:
        empty = random.choices(numbers, k=n_dim)
        while empty in occupied:
            empty = random.choices(numbers, k=n_dim)
    else:
        occupied_tuple = [tuple(i) for i in occupied]
        all_combos = itertools.product(numbers, repeat=n_dim)
        leftover = tuple(set(all_combos) - set(occupied_tuple))
        empty = list(random.choice(leftover))
    return empty

我用以下方法测试了这一点：e应始终为[0,0,0]，因为这是唯一的可能性：

combos = [list(i) for i in list(itertools.product(range(50), repeat=3))]
combos.remove([0,0,0])

e = get_empty_slot(combos, k=.5)

集差法似乎表现良好，超过100000种可能性（剩下1种选择）；它的表现也很好，可能性要小得多。因此，随机元素选择在任何情况下都不会有明显的改善（这可以测试），这就引出了一个问题，即与所有可能的组合进行比较是否真的太昂贵，以及如果是这样的话，另一种选择会是什么样子