将展平的一维索引转换为二维索引

Question

假设我有一个列表列表，例如：

x = [[0,1,2,3],[4,5],[6,7,8,9,10]]

而且我有我希望定位的元素的 'flat' 索引，即如果列表被展平为一维列表，我想从列表中 select 的元素的索引：

flattened_indices = [0,1,4,9]

                  # #     #         #
flattened_list = [0,1,2,3,4,5,6,7,8,9,10]

如何转换 1.d。索引到 2.d。允许我从原始嵌套列表中恢复元素的索引？ IE。在这个例子中：

2d_indices = [(0,0), (0,1), (1,0), (2,3)]

Answer 1

这是一种方法：

from bisect import bisect
import itertools

# Accumulated sum of list lengths
def len_cumsum(x):
    return list(itertools.accumulate(map(len, x)))

# Find 2D index from accumulated list of lengths
def find_2d_idx(c, idx):
    i1 = bisect(c, idx)
    i2 = (idx - c[i1 - 1]) if i1 > 0 else idx
    return (i1, i2)

# Test
x = [[0, 1, 2, 3], [4, 5], [6, 7, 8, 9, 10]]
indices = [0, 4, 9]
flattened_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
c = len_cumsum(x)
idx_2d = [find_2d_idx(c, i) for i in indices]

print(idx_2d)
>>> [(0, 0), (1, 0), (2, 3)]

print([x[i1][i2] for i1, i2 in idx_2d])
>>> [0, 4, 9]

如果您有许多“扁平”索引，这比为每个索引迭代嵌套列表更有效。

Answer 2

我想你可以把这些索引对放在一个字典中，然后在最后引用 indices 中的字典并创建一个新列表：

x = [[0,1,2,3],[4,5],[6,7,8,9,10]]

indices = [0,4,9]

idx_map = {x: (i, j) for i, l in enumerate(x) for j, x in enumerate(l)}

result = [idx_map[x] for x in indices]
print(result)

这导致：

[(0, 0), (1, 0), (2, 3)]

但这不是最优的，因为它的二次运行时间创建 idx_map。使用二分法的解决方案要优化得多。

将展平的一维索引转换为二维索引

Convert flattened 1 dimensional indices to 2 dimensional indices

python

python-3.x

nested-lists

indices