# Set-Intersection Iteration

Suppose I have two sets with integral elements $A$ = {$a_1, a_2, ... , a_n$} and $B$ = {$b_1, b_2, ... , b_m$}, the cardinalities of which are arbitrarily large, and $a_n > a_{n - 1} > a_{n - 2} > ... > a_1$ and $b_m > b_{m - 1} > b_{m - 2} > ... > b_1$ with $n$ ≠ $m$. Suppose, also, that the intersection of sets $A$ and $B$ is the singleton set {$c$}, and there exists an index $i$ such that $b_{i + 1} > a_n > b_i > b_{i - 1} > ... > b_1$ where $a_n = \sup(A)$.

I want to create a for-loop iteration (or whatever the best approach might be!) that finds the set intersection without generating all the elements of both sets and then determining the set {$c$}. (This is possible because the generating functions I've created yield explicit formulas I can use to calculate specific elements of both sets.)

I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long. I'm thinking the following approach might be faster, but I don't know how to write the program using for-/while-loops and if/else constructions (or even if I should do so):

(1) Check if $a_{n - 1}$ ≤ $b_i$. If $a_{n - 1} > b_i$, keep checking conterminous decreasing indices for elements of $A$ (i.e., $a_{n - 2}$, $a_{n - 3}$, etc.) until $a_j$ ≤ $b_i$ for some index $j < n - 1$. If $a_j = b_i$, break and print($a_j$). If not, go to step (2).

(2) When $a_j < b_i$, check conterminous decreasing indices for elements of $B$ (i.e., $b_{i - 1}$, $b_{i - 2}$, etc.) until $a_j$ ≥ $b_k$ for some index $k < i$. If $a_j = b_k$, break and print($b_k$). If not, go to step (3).

(3) Repeat the process in steps (1) and (2) until $a_r = b_s$ for some indices $r$ ≠ $s$; then, break and print($b_s$).

edit retag close merge delete

Yes, you could do that using "iterators" that produce elements in increasing order one by one.

( 2020-09-01 16:14:24 +0200 )edit

Great. Could you point me to a site/book that will show me how to write this kind of iterative code? The tutorials I've read only show basic for- or while-loop constructions with one or two nested if-then conditions.

( 2020-09-01 23:39:18 +0200 )edit

In the question you write:

I wrote some basic code in Sage to calculate elementary set intersection, but for even moderately large cardinalities, the halt time was incredibly long.

Please provide the code you wrote so far and we can help build from that.

( 2020-09-02 23:32:16 +0200 )edit

To display blocks of code or error messages in Ask Sage, skip a line above and below, and do one of the following (all give the same result):

• indent all code lines with 4 spaces
• select all code lines and click the "code" button (the icon with '101 010')
• select all code lines and hit ctrl-K

For instance, typing

If we define f by

def f(x, y, z):
return x * y * z

then f(2, 3, 5) returns 30 but f(2*3*5) gives:

TypeError: f() takes exactly 3 arguments (1 given)


produces:

If we define f by

def f(x, y, z):
return x * y * z


then f(2, 3, 5) returns 30 but f(2*3*5) gives:

TypeError: f() takes exactly 3 arguments (1 given)


( 2020-09-02 23:33:31 +0200 )edit

Here's the code. The most basic set intersection based on my research/reading:

sage: n=[some integer]; L=[f_1(x) for x in sxrange(1,(n+1)/2)]; M=[f_2(x) for x \
....:  in sxrange(1,(n+1)/2)]; [x for x in L if x in M]


For arbitrarily large $n$, this is too expensive from a time-complexity standpoint.

( 2020-09-03 00:52:56 +0200 )edit

Sort by » oldest newest most voted

On the "Thematic tutorials" page of the SageMath documentation:

check out this tutorial:

To recap, we start from

• two integers n and m
• two increasing functions
• $f : [1, ..., n] \to mathbb{R}$
• $g : [1, ..., m] \to mathbb{R}$

and we define

• $A$ = {$f(i),\ i = 1 .. n$}
• $B$ = {$g(i),\ i = 1 .. m$}

We know these sets have a single common point and we want to find it.

Our choice is between:

• go upwards

• start from the lowest elements of $A$ and $B$
• check if they are equal
• if so we're done
• if not take the next element from the set which had given us the lowest number
• go upwards

• start from the highest elements of $A$ and $B$
• check if they are equal
• if so we're done
• if not take the next element down from the set which had given us the highest number

Here is the upwards version:

def common_element_upwards(f, g, n, m):
r"""
Return the common element between A = \{ f(i): i = 1 .. n \}
and B = \{ g(i): i = 1 .. m \}.

Assumptions:

- f and g are increasing functions
- A and B have a common element
"""
A = (f(i) for i in (1 .. n))
B = (g(i) for i in (1 .. m))
a = next(A)
b = next(B)
while a != b:
if a < b:
a = next(A)
else:
b = next(B)
return a


Here is the downwards version:

def common_element_downwards(f, g, n, m):
r"""
Return a common element between the sets
A = \{ f(i): i = 1 .. n \}
and B = \{ g(i): i = 1 .. m \}.

Assumptions:

- f and g are increasing functions
- A and B have a common element
"""
A = (f(i) for i in (n, n - 1 .. 1))
B = (g(i) for i in (m, m - 1 .. 1))
a = next(A)
b = next(B)
while a != b:
if a > b:
a = next(A)
else:
b = next(B)
return a


Example:

sage: f = lambda x: x^3 + 1
sage: g = lambda x: x^2
sage: n = 20
sage: m = 30
sage: common_element_upwards(f, g, n, m)
9
sage: common_element_downwards(f, g, n, m)
9

more

Thanks. I've been through those tutorials, but I'll check them again in case I missed something. I've found "Computational Mathematics with SageMath" to be an excellent resource, but I'm still having trouble with the syntax of indices as they relate to iterative commands.

( 2020-09-02 22:34:42 +0200 )edit

Fantastic...and not anything I've seen in the tutorials/literature, which means I would have been looking forever! I can't wait to try it and let you know how it goes. Thanks again.

( 2020-09-03 02:24:04 +0200 )edit

Success! Now, I just need to find a way to program the index $i$ to make it less expensive.

( 2020-09-03 23:02:39 +0200 )edit

The "upwards" code works for very small $n$, but I keep getting a "StopIteration" error when using numbers even as small as four digits:

---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-259-34dce5deec42> in <module>()
----> 1 n=(Integer(5335)+Integer(1))/Integer(2); common_element_upwards(f, g, n, m)

<ipython-input-252-4f212b87ce54> in common_element_upwards(f, g, n, m)
17           a = next(A)
18         else:
---> 19           b = next(B)
20     return a

StopIteration:

( 2020-09-04 00:20:05 +0200 )edit

The StopIteration error happens when one of the sets runs out and no common element was found.

One could use a try/except to catch that and return a more meaningful error message in that case.

( 2020-09-04 01:24:42 +0200 )edit