Pairs from Single List

Pairs from single list

My favorite way to do it:

def pairwise(t):
    it = iter(t)
    return zip(it,it)

# for "pairs" of any length
def chunkwise(t, size=2):
    it = iter(t)
    return zip(*[it]*size)

When you want to pair all elements you obviously might need a fillvalue:

from itertools import izip_longest
def blockwise(t, size=2, fillvalue=None):
    it = iter(t)
    return izip_longest(*[it]*size, fillvalue=fillvalue)

With Python 3, itertools.izip is now simply zip .. to work with an older Python, use

from itertools import izip as zip

How to pair a list of lists in various ways based on the first element

Your question is a lot harder than it seems with a quick read!

That said, I have tried few things (cause it made me stubborn...) and I will present: (1) observations/questions, (2) a potential answer and (3) some comments on your original solution

Starting with a recap of requirements:

You have a list of lists
The sub-lists are ordered based on their first element
You have a map, SUB_NOUNS, which tells us which lists can be followed by which others based on each list's first element
You are looking for potential combinations

Observations (and maybe open questions):

In the OP you are showing a SUB_NOUNS example with 2 entries. I am assuming that more than two entries are also possible
In the example of [[3, 2, 0], [10, 3, 0], [22, 12, 0]] we see that you are looking for the longest possible combo, therefore:
- Combinations can have 2+ levels (unbounded). This smells like "recursion" to me and that's how the proposed solution is
- Altho [10, 3, 0], [22, 12, 0] (without the [3, 2, 0]) is a valid combination, you do not list it in the example output. This makes me assume that you do not want to reuse lists that you have already used in a longer combo as a starting point of another combo
In the example of [[3, 1, 0], [3, 2, 0], [18, 0, 0]], based on the desired output we see that the same list can participate in multiple combos, as long as the "prefix" (the lists before it) are different

Proposed Solution

As mentioned earlier, this is recursive and has two parts:

get_all_combos which gathers all the potential combinations for all the lists that can act as a starting point. This also controls list reuse (see later)
get_combos: The recursive part of the solution that forms all the combinations for a given starting list

(You can ignore or remove the logging, but is usually needed in recursion for debugging purposes...)

def get_all_combos(data, allow_reuse=False):
    """ For each element in the data list, find its combinations recursively"""
    all_combos = []
    all_used_lists = set()
    for item_num, item in enumerate(data):
        # Do not start new combinations from lists
        # that appear somewhere inside another combination
        if item_num in all_used_lists and not allow_reuse:
            continue

        combos, used = get_combos(data, item_num)
        if combos:
            all_combos.extend(combos)
            all_used_lists.update(used)

    return all_combos or data

def get_combos(data, list_num=0):
    """
    Return all combinations from list_num onwards and also the indexes
    of the lists that were used to form those combos
    """
    lg.debug(f"{list_num * 4 * ' '} list num: {list_num}")
    combos = []
    used_lists = set()
    current_list = data[list_num]
    current_first = current_list[0]

    # Filter all allowed pairs
    for pair_num, pair in enumerate(data[list_num + 1:], list_num + 1):
        # Skip elements that cannot be combined (we could also use filter())
        if pair[0] not in SUB_NOUNS[current_first]:
            continue

        lg.debug(f"{list_num * 4 * ' '} Pair_num {pair_num}")

        # Get combos of this pair
        subcombos, used = get_combos(data, pair_num)
        lg.debug(f"{list_num * 4 * ' '} Subcombos {subcombos}")

        # If there are no subcombinations, just combine the current list
        # with its child one (pair)
        if not subcombos:
            combos.append(current_list + pair)
            used_lists.update({list_num, pair_num})
            lg.debug(f"{list_num * 4 * ' '} Inserting {combos[0]}")
            continue

        # Here we have sub-combos. For each one of them, merge it to the
        # current combos
        for combo in subcombos:
            combos.append(current_list + combo)
            used_lists.update(used | {list_num})
            lg.debug(f"{list_num * 4 * ' '} Extending appends {combos[0]}")

    lg.debug(f"{list_num * 4 * ' '} Combos {combos}")
    lg.debug(f"{list_num * 4 * ' '} Used {used_lists}")
    return combos, used_lists

Now, before we go to look at some output of the above code, lets take a quick look at your solution (inline comments):

def pair_lists(data):
    pairs = []
    # > Reversal can be potentially avoided here
    for noun in reversed(data):
        try:
            # > Instead of itertool+filter false, you could just use filter() 
            # > with the reverse condition right?
            result = itertools.filterfalse(lambda x: x[0] not in SUB_NOUNS[noun[0]], data)
            for each in result:
                paired = []
                # > ^--- The following if is always false since paired is always [] 
                if each not in paired:
                    paired.insert(0, each)
                # > insert vs append depends on the reversal in the outer loop
                paired.insert(0, noun)
                pairs.append(list(itertools.chain(*paired)))
        except KeyError:
            pass
    return pairs if pairs else data

A more compact version which should be 100% the same logic is the following:

def pair_lists_urban(data):
    pairs = []
    for noun in data:
        try:
            result = filter(lambda x: x[0] in SUB_NOUNS[noun[0]], data)
            for each in result:
                pairs.append(noun + each)
        except KeyError:
            pass
    return pairs if pairs else data

Note that both the above versions have a contraint/issue: They look at only two levels of lists to form a combo (ie N and N+1). This will become apparent in the next section

Tests

So, lets run all the solutions so far with the example lists that you provided. The main script is:

import itertools
import logging as lg
import sys

SUB_NOUNS = {
    3: [10, 11, 18, 19, 20],
    10: [22],
}

# ... funcs for each solution

test_lists = [
    [[3, 1, 0]],
    [[3, 1, 0], [10, 2, 0]],
    [[3, 2, 0], [10, 3, 0], [10, 4, 0]],
    [[3, 1, 0], [3, 2, 0], [3, 3, 0]],
    [[3, 2, 0], [10, 3, 0], [22, 12, 0]],
    [[3, 1, 0], [3, 2, 0], [18, 0, 0]],
]

for l in test_lists:
    print(f"\nIn: {l}")
    print(f"Recur Out: {get_all_combos(l)}")
    print(f"Iter. Out: {pair_lists(l)}")
    print(f"Iter2 Out: {pair_lists_urban(l)}")

Looking at the output, we have (with comments):

# All good 
In: [[3, 1, 0]]
Recur Out: [[3, 1, 0]]
Iter. Out: [[3, 1, 0]]
Iter2 Out: [[3, 1, 0]]

# All good 
In: [[3, 1, 0], [10, 2, 0]]
Recur Out: [[3, 1, 0, 10, 2, 0]]
Iter. Out: [[3, 1, 0, 10, 2, 0]]
Iter2 Out: [[3, 1, 0, 10, 2, 0]]

# All good 
In: [[3, 2, 0], [10, 3, 0], [10, 4, 0]]
Recur Out: [[3, 2, 0, 10, 3, 0], [3, 2, 0, 10, 4, 0]]
Iter. Out: [[3, 2, 0, 10, 3, 0], [3, 2, 0, 10, 4, 0]]
Iter2 Out: [[3, 2, 0, 10, 3, 0], [3, 2, 0, 10, 4, 0]]

# All good 
In: [[3, 1, 0], [3, 2, 0], [3, 3, 0]]
Recur Out: [[3, 1, 0], [3, 2, 0], [3, 3, 0]]
Iter. Out: [[3, 1, 0], [3, 2, 0], [3, 3, 0]]
Iter2 Out: [[3, 1, 0], [3, 2, 0], [3, 3, 0]]

# ! some issues: Recursion outputs the desired result while the other 
# two solutions do not. This is because as mentioned earlier, these 
# are only looking at two levels for each pair and that is also why
# resulting combos have only 6 elements
In: [[3, 2, 0], [10, 3, 0], [22, 12, 0]]
Recur Out: [[3, 2, 0, 10, 3, 0, 22, 12, 0]]
Iter. Out: [[10, 3, 0, 22, 12, 0], [3, 2, 0, 10, 3, 0]]
Iter2 Out: [[3, 2, 0, 10, 3, 0], [10, 3, 0, 22, 12, 0]]

# Results look ok, one nit: combos are coming out in different order
# (some append/insert issue somewhere i 'd say)
In: [[3, 1, 0], [3, 2, 0], [18, 0, 0]]
Recur Out: [[3, 1, 0, 18, 0, 0], [3, 2, 0, 18, 0, 0]]
Iter. Out: [[3, 2, 0, 18, 0, 0], [3, 1, 0, 18, 0, 0]]
Iter2 Out: [[3, 1, 0, 18, 0, 0], [3, 2, 0, 18, 0, 0]]

Considerations

Focusing on the recursive solution, I am looking into few further cases:

What if "loops" appear in the SUB_NOUNS
What if we have some more SUB_NOUNS
How can we control list reuse in the proposed solution

For this I am using the following test:

SUB_NOUNS = {
    3: [10, 11, 18, 19, 20],
    10: [22, 30],
    # Third level. Note that we can have 10->22->30 and 10->30
    22: [30, 42],
    # Unhandled case where a larger number can be followed by a smaller number
    30: [1, 22],
}

test_list = [[3, 2, 0], [10, 3, 0], [22, 12, 0], [30, 0, 6], [42, 8, 9]]

print(f"\nIn: {test_list}")
print(f"Recur No Reuse: {get_all_combos(test_list)}")
print(f"Recur Reuse   : {get_all_combos(test_list, True)}")

Starting with the easy one: loops are avoided in the recursive solution by always processing lists from left to right and only after the current list (data[list_num + 1:]). This way we never go back and avoid infinite recursion. However, this is also a limitation to be kept in mind and the reason that the SUB_NOUNS[30] above will have no effect (since 1 or 22 will never appear in the input after 30)

With more SUB_NOUNS you have more "branches" and potential combinations. The output is:

In: [[3, 2, 0], [10, 3, 0], [22, 12, 0], [30, 0, 6], [42, 8, 9]]
Recur No Reuse: [
    [3, 2, 0, 10, 3, 0, 22, 12, 0, 30, 0, 6], 
    [3, 2, 0, 10, 3, 0, 22, 12, 0, 42, 8, 9], 
    [3, 2, 0, 10, 3, 0, 30, 0, 6],
]
Recur Reuse   : [
    [3, 2, 0, 10, 3, 0, 22, 12, 0, 30, 0, 6], 
    [3, 2, 0, 10, 3, 0, 22, 12, 0, 42, 8, 9], 
    [3, 2, 0, 10, 3, 0, 30, 0, 6], 
    [10, 3, 0, 22, 12, 0, 30, 0, 6], 
    [10, 3, 0, 22, 12, 0, 42, 8, 9], 
    [10, 3, 0, 30, 0, 6], 
    [22, 12, 0, 30, 0, 6], 
    [22, 12, 0, 42, 8, 9],
]

Notes - open-ended points:

You can see in the above example how things can branch out and how both 10->30 and 10->22->30 combinations are considered
You can also see double-branching: on the 10->22 path we have 10->22->30 and 10->22->42
Notice that in the second invocation we set allow_reuse=True in get_all_combos. This allows the code to return combos whose first element/list has already participated in another combination. Altho in your [[3, 2, 0], [10, 3, 0], [22, 12, 0]] example you do not seem to look for such combos, they are all "correct" and follow the rules of SUB_NOUNS

As you said in the post, this might not be the best or a perfect solution but I believe recursion allows you to do all sorts of things which would be really hard otherwise in this particular case. I found this problem fairly complex due to the numerous possibilities of input data, constraining it a bit and narrowing down the scope if possible (ex. input always has up to 3 sub-lists) would help simplify the solution.

How to create list of pairs from an even-length list in python?

How about a simple list comprehension?

paired_list = [(straight_list[i], straight_list[i+1]) for i in range(0, len(straight_list), 2)]

Collect every pair of elements from a list into tuples in Python

Well there is one very easy, but somewhat fragile way, zip it with sliced versions of itself.

zipped = zip(mylist[0::2], mylist[1::2])

In case you didn't know, the last slice parameter is the "step". So we select every second item in the list starting from zero (1, 3, 5). Then we do the same but starting from one (2, 4, 6) and make tuples out of them with zip.

Efficient way to find all the pairs in a list without using nested loop

You can use a dictionary to keep track of the indices for each point.

Then, you can iterate over the items in the dictionary, printing out the indices corresponding to points that appear more than once. The runtime of this procedure is linear, rather than quadratic, in the number of points in A:

points = {}

for index, point in enumerate(A):
    point_tuple = tuple(point)
    if point_tuple not in points:
        points[point_tuple] = []
    points[point_tuple].append(index)

for point, indices in points.items():
    if len(indices) > 1:
        print(indices)

This prints out:

[0, 3, 7]
[1, 6]

If you only want the first two indices where a point appears, you can use print(indices[:2]) rather than print(indices).

Iterate through pairs of items in a Python list

From the itertools recipes:

from itertools import tee

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

for v, w in pairwise(a):
    ...

Pairs from Single List