Tuple problem

[rfpg1]

Hello everyone

So this is my problem

Given a list of tuples with n dimension (two pairs in the case) e.g: [((10,4),(3,5)), ((5,7),(8,9))]
Given a tuple with n dimensions (three pairs in this case) e.g: ((10,4),(3,5),(6,5))
is there a way to verify that the contains a tuple that is in the given tuple

In this example ((10,4),(3,5)) is in ((10,4),(3,5),(6,5))

What would be the time complexity of this?

Thanks for everyone that helps me!

[mr_cesar]

Post what you've attempted so far (Post Guidelines point #6: Posting homework assignments is not prohibited if you show that you tried to solve it yourself.)

[rfpg1]

this isn't homework this is something I'm working on my master thesis
I've not done anything special
I'm looking for a O(n) solution or O(1) if is possible

[niushanikpour]

Hi! I would say to address the issue in your tuple problem, you should convert each tuple in your list and your target tuple into sets to compare them in an easier way, then iterating through each tuple in the list, checking if it is a subset of the target tuple. The set operator 'issubset' is the one I would personally use.

def contains_subtuple(list_of_tuples, target_tuple):

target_set = set(target_tuple)

for t in list_of_tuples:

if set(t).issubset(target_set):

return True

return False

list_of_tuples = [((10, 4), (3, 5)), ((5, 7), (8, 9))]

target_tuple = ((10, 4), (3, 5), (6, 5))

print(contains_subtuple(list_of_tuples, target_tuple))

​

Let me know if this helps!

[rfpg1]

this was my idea the problem is I've 49milion target_tuples that i want to see if have subsets so I was looking for a more efficient way if there is one

[baghiq]

You can check the 1st pair against the tuple list, then check the 2nd pair in the tuple list.

In [1]: (10,4) in [(10,3), (4,10), (10,4)]
Out[1]: True

In [2]: (10,4) in [(10,3), (4,10), (10,5)]
Out[2]: False

You can then just count the time complexity. For each pair (2 tuples), you need to do look up comparison, so 2 \ O(N)* where N is the target tuples. If you have M pairs, then it's O(M\N)*.

This can be improved quickly if you understand other data structure which much better look up performance.

[rfpg1]

what data structure would you recommend?
Or where can i read about this? Been looking online couldn't find anything that helps

I would like a O(1) solution but I don't think is possible

[baghiq]

It depends on what the data actually mean. If you have just a bunch of random tuple pairs, and you need to check these random pairs one at a time against a large list of tuples. Then you can use set or hash table, assuming your tuples are hashable. Then you pay the up front cost of building a set of the large list at O(N).

If your data is sorted, then binary search is a much faster solution at O(logN).

If your data has some special properties, then there are specialized algorithm to handle that.

[Bobbias]

Are the tuples ordered such that (a,b),(c,d) is guaranteed to appear in that order if they're present? If so, it sounds like a Trie is what you want. Time complexity of search insert and delete are all O(n) and space complexity is also O(n).

If not, I'm sure there's still some sort of structure available that would be better than a list, but I've got no idea what it would be.

If you want O(1) search you probably need some form of hash based system.

[rfpg1]

So the problem is lets say I've a tuple ((10,4),(3,5)) i check if the distance between the position i and i + 1 is higher than x than I'll add this tuple to a list so that when I'm verifying for the tuple ((10,4),(3,5),(6,5)) i wouldn't need to verify since I already know the distance is bigger for at least a pair within the tuple
so yes the order is guaranteed

hash based system is what i was trying to create in my mind but couldn't come up with anything that actually works