Mapping ordered combinations from two lists in Python

user_1505259 0
Viewed 103

I have two lists. The first list holds the names of points on a line. The second list holds the ordered distances between those points.

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

Examples

  1. Segment lengths for the point group (A, B) is (10). Segment lengths for the point group (B,C) is (20). Segment lengths for the point group (C, D) is (30)
  2. Segment lengths for the point group (A, C) is (10, 20)
  3. Segment lengths for the point group (A, D) is (10, 20, 30)
  4. Segment lengths for the point group (A, B, C) is (10, 20)
  5. Segment lengths for the point group (A, B, C, D) is (10, 20, 30)

Problem

I need to do two things:

  1. Extract all possible ordered combinations of point groups from list points
  2. Create matching segment length combinations from list segment_lengths

Desired Output

So, the desired output from list a is:

('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')

desired matching output from list b:

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

Trials so far

I was able to create the first output using itertools as follows:

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

However, I am unable find a good way to create the matching output from the second list.

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

creates the following:

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

which are the correct possibilities, but obviously this is not mapped to the first output.

I was wondering if there is an elegant and clean way creating the second output using itertools or some other built-in library. If not I think I would probably need to go the route of for loops and indices (which I would like to avoid if I can).

Thank you for the help!

EDIT: Made some corrections to the code where I was using inconsistent list names.

combinations itertools python
2 Answers

You can create a mapping from points with their indices as keys. Then you iterate over the combination of points, get their indices from the dict, and extract the required distances using slicing.

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}')

Output:

('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)

The benefit of using this approach is, you can use duplicates in your points, and it will give 0:

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

NOTE: Here I have used itertools.pairwise which was introduced in Python 3.10. If that is not available to you, you can make a pairwise function yourself.

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)
user_54317910

There's a popular quote that says that you can solve a lot of hard CS problems by "introducing a layer of indirection".

So instead of directly taking combinations of points or segment lengths, you can "indirectly" take combinations of indexes of points/segment lengths:

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)
user_114611200
Related