在 Python 中映射两个列表中的有序组合

Question

我有两个清单。第一个列表包含线上点的名称。第二个列表保存这些点之间的有序距离。

points = ['A', 'B', 'C', 'D']
segment_lengths = [10, 20, 30]

示例

1. 点群(A,B)的线段长度为(10)。点群 (B,C) 的线段长度为 (20)。点群 (C, D) 的线段长度为 (30)
2. 点群 (A, C) 的线段长度为 (10, 20)
3. 点群 (A, D) 的线段长度为 (10, 20, 30)
4. 点群 (A, B, C) 的线段长度为 (10, 20)
5. 点群 (A, B, C, D) 的线段长度为 (10, 20, 30)

问题

我需要做两件事：

1. 从列表中提取点组的所有可能的有序组合

   points

2. 从列表中创建匹配的段长度组合

   segment_lengths

所需输出

因此，列表 a 所需的输出是：

('A', 'B')
('A', 'C')
('A', 'D')
('B', 'C')
('B', 'D')
('C', 'D')
('A', 'B', 'C')
('A', 'B', 'D')
('A', 'C', 'D')
('B', 'C', 'D')
('A', 'B', 'C', 'D')

列表 b 中所需的匹配输出：

(10)
(10, 20)
(10, 20, 30)
(20)
(20, 30)
(30)
(10, 20)
(10, 20, 30)
(10, 20, 30)
(20, 30)
(10, 20, 30)

迄今为止的试验

我能够使用

itertools

创建第一个输出，如下所示：

for i in range(2, len(points)+1):
    a = itertools.combinations(points, i)
    for elem in a:
        print(elem)

但是，我无法找到从第二个列表创建匹配输出的好方法。

for i in range(1, len(segment_lengths)+1):
    b = itertools.combinations(segment_lengths, i)
    for elem in b:
        print(elem)

创建以下内容：

(10,)
(20,)
(30,)
(10, 20)
(10, 30)
(20, 30)
(10, 20, 30)

哪些是正确的可能性，但显然这没有映射到第一个输出。

我想知道是否有一种优雅而干净的方式使用

itertools

或其他内置库创建第二个输出。如果不是，我想我可能需要走 for 循环和索引的路线（如果可以的话我想避免）。

Answer 1

有一个流行的引言说你可以通过“引入间接层”来解决很多计算机科学难题。

因此，您可以“间接”采用点/线段长度的索引的组合，而不是直接采用点或线段长度的组合：

import itertools

points = ('A', 'B', 'C', 'D')
segment_lengths = (10, 20, 30)
N = len(points)

for combo_size in range(2, N + 1):
    for index_combo in itertools.combinations(range(N), combo_size):
        A = tuple(points[i] for i in index_combo)
        first, last = index_combo[0], index_combo[-1]
        B = segment_lengths[first:last]
        print(A, B)

# ('A', 'B') (10,)
# ('A', 'C') (10, 20)
# ('A', 'D') (10, 20, 30)
# ('B', 'C') (20,)
# ('B', 'D') (20, 30)
# ('C', 'D') (30,)
# ('A', 'B', 'C') (10, 20)
# ('A', 'B', 'D') (10, 20, 30)
# ('A', 'C', 'D') (10, 20, 30)
# ('B', 'C', 'D') (20, 30)
# ('A', 'B', 'C', 'D') (10, 20, 30)

Answer 2

您可以从

points

创建映射，其索引为

keys

。然后迭代点的组合，从字典中获取它们的索引，并使用切片提取所需的距离。

from itertools import combinations, chain, pairwise
from collections import deque

points = ['A', 'B', 'C', 'D']
segment_length = [10, 20, 30]

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

# create a map of points with their indices
# takes care of duplicates in `points` list
point_map = dict()
for i, point in enumerate(points):
    point_map[point] = point_map.get(point, i)

def get_distance(point):
    result = []
    for start, end in pairwise(point):
        i_start = point_map[start]
        i_end = point_map[end]
        #    in the following line, use
        #    dist=segment_length[i_start:i_end] 
        #    if you don't want 0 for duplicates
        dist = [0] if i_start==i_end else segment_length[i_start:i_end]
        result.extend(dist)
    return tuple(result)

all_points = powerset(point_map.keys())

for point in all_points:
    result = get_distance(point)
    if result:      # filter out 0 & 1 length tuples from powerset
        print(f'{point} -> {result}')

输出：

('A', 'B') -> (10,)
('A', 'C') -> (10, 20)
('A', 'D') -> (10, 20, 30)
('B', 'C') -> (20,)
('B', 'D') -> (20, 30)
('C', 'D') -> (30,)
('A', 'B', 'C') -> (10, 20)
('A', 'B', 'D') -> (10, 20, 30)
('A', 'C', 'D') -> (10, 20, 30)
('B', 'C', 'D') -> (20, 30)
('A', 'B', 'C', 'D') -> (10, 20, 30)

使用这种方法的好处是，你可以在你的点中使用重复项，它会给出

0

:

>>> get_distance(('A', 'A', 'C'))
(0, 10)

注意：这里我使用了Python 3.10中引入的

itertools.pairwise

。如果您无法使用该功能，您可以自己制作一个

pairwise

功能。

from itertools import tee
def pairwise(iterable):
    # pairwise('ABCDEFG') --> AB BC CD DE EF FG
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)