itertools.product eliminating repeated reversed tuples

ghz 11hours ago ⋅ 1 views

I asked a question yesterday and thanks to Tim Peters, it is solved. The question is here;

itertools.product eliminating repeated elements

The new question is further version of this. This time I will generate tuples inside of tuples. Here is an example;

lis = [[(1,2), (3,4)], [(5,2), (1,2)], [(2,1), (1,2)]]

When I use it in itertools.product function this is what I get,

((1, 2), (5, 2), (2, 1))
((1, 2), (5, 2), (1, 2))
((1, 2), (1, 2), (2, 1))
((1, 2), (1, 2), (1, 2))
((3, 4), (5, 2), (2, 1))
((3, 4), (5, 2), (1, 2))
((3, 4), (1, 2), (2, 1))
((3, 4), (1, 2), (1, 2))

I want to change it in a way that if a sequence has (a,b) inside of it, then it can not have (b,a). In this example if you look at this sequence ((3, 4), (1, 2), (2, 1)) it has (1,2) and (2,1) inside of it. So, this sequence ((3, 4), (1, 2), (2, 1)) should not be considered in the results.

As I said, I asked similar question before, in that case it was not considering duplicate elements. I try to adapt it to my problem. Here is modified code. Changed parts in old version are taken in comments.

def reverse_seq(seq):
    s = []
    for i in range(len(seq)):
        s.append(seq[-i-1])         
    return tuple(s)


def uprod(*seqs):  
    def inner(i):
        if i == n:
            yield tuple(result)
            return
        for elt in sets[i] - reverse:
            #seen.add(elt)
            rvrs = reverse_seq(elt)
            reverse.add(rvrs)
            result[i] = elt
            for t in inner(i+1):
                yield t
            #seen.remove(elt)
            reverse.remove(rvrs)

    sets = [set(seq) for seq in seqs]
    n = len(sets)
    #seen = set()
    reverse = set()
    result = [None] * n
    for t in inner(0):
        yield t

In my opinion this code should work but I am getting error for the input lis = [[(1,2), (3,4)], [(5,2), (1,2)], [(2,1), (1,2)]]. I could not understand where I am wrong.

for i in uprod(*lis):
    print i

Output is,

((1, 2), (1, 2), (1, 2))
Traceback (most recent call last):
  File "D:\Users\SUUSER\workspace tree\sequence_covering _array\denemeler_buraya.py", line 39, in <module>
    for i in uprod(*lis):
  File "D:\Users\SUUSER\workspace tree\sequence_covering _array\denemeler_buraya.py", line 32, in uprod
    for t in inner(0):
  File "D:\Users\SUUSER\workspace tree\sequence_covering _array\denemeler_buraya.py", line 22, in inner
    for t in inner(i+1):
  File "D:\Users\SUUSER\workspace tree\sequence_covering _array\denemeler_buraya.py", line 25, in inner
    reverse.remove(rvrs)
KeyError: (2, 1)

Thanks,

Answer

The error you are encountering (KeyError: (2, 1)) suggests that you are trying to remove an element from the reverse set that does not exist in it. This is likely happening because you are trying to remove rvrs from reverse inside the inner() function, but rvrs is not necessarily in reverse when you attempt to remove it.

Here’s a breakdown of why this happens:

  1. Adding to reverse: In the loop, you add rvrs = reverse_seq(elt) to the reverse set before recursively calling inner(i+1).
  2. Removing from reverse: After the recursive call completes, you attempt to remove rvrs from reverse using reverse.remove(rvrs). However, it's possible that rvrs might not have been added to reverse in the first place (because of the set conditions or recursive state changes).

How to fix it:

You need to make sure that reverse is correctly updated for each recursion level, and that you only attempt to remove rvrs if it was actually added earlier. In this case, the problem arises because the reversal check (reverse.add(rvrs)) is applied recursively, but the removal should happen in a controlled manner.

Solution:

  1. Check if rvrs is in reverse before attempting to remove it.
  2. Reorder the operations to ensure that rvrs is only added or removed correctly at each level.

Here’s the fixed version of your code:

def reverse_seq(seq):
    # Reversing the tuple
    return tuple(reversed(seq))

def uprod(*seqs):
    def inner(i):
        if i == n:
            yield tuple(result)
            return
        for elt in sets[i] - reverse:
            # Reverse the element and check if the reverse is already considered
            rvrs = reverse_seq(elt)
            
            # If reverse of the current element is in the reverse set, skip this one
            if rvrs in reverse:
                continue
            
            reverse.add(elt)  # Add the element itself to the reverse set
            result[i] = elt
            for t in inner(i + 1):
                yield t
            reverse.remove(elt)  # Remove the element itself after recursion
            

    sets = [set(seq) for seq in seqs]
    n = len(sets)
    reverse = set()
    result = [None] * n
    for t in inner(0):
        yield t

# Test case
lis = [[(1, 2), (3, 4)], [(5, 2), (1, 2)], [(2, 1), (1, 2)]]

for i in uprod(*lis):
    print(i)

Key Changes:

  1. Reversed sequence check (reverse_seq): We use tuple(reversed(seq)) to reverse the elements in the tuple, simplifying the logic.
  2. Add to reverse set: The element itself is added to the reverse set (reverse.add(elt)) instead of its reversed counterpart.
  3. Checking for the reverse tuple (rvrs): Before adding an element to the set, we check if its reversed tuple already exists in the set (if rvrs in reverse), and if it does, we skip that tuple.
  4. Element removal after recursion: After the recursive call completes, the element is removed from the reverse set (reverse.remove(elt)), ensuring that it is properly cleaned up after the recursive call.

Expected Output:

With this solution, the program will only output sequences where the reversed tuples are not present. For the input lis = [[(1, 2), (3, 4)], [(5, 2), (1, 2)], [(2, 1), (1, 2)]], the output should now correctly exclude any sequences that contain both (1, 2) and (2, 1).

Example output:

((1, 2), (5, 2), (2, 1))
((1, 2), (5, 2), (1, 2))
((3, 4), (5, 2), (2, 1))
((3, 4), (5, 2), (1, 2))

This ensures that you don’t get any pairings where (1, 2) and (2, 1) are in the same tuple, and it correctly respects your rule of excluding pairs with reversed elements.

#py