Set-Intersection Iteration

u220e
11 ●1 ●1 ●4

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$ ).

Thanks in advance.

Comments

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

FrédéricC ( 4 years ago )

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.

u220e ( 4 years ago )

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.

slelievre ( 4 years ago )

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)

Please edit your question to add your code formatted in that way.

slelievre ( 4 years ago )

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.

u220e ( 4 years ago )

add a comment

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

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

Comments

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.

u220e ( 4 years ago )

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.

u220e ( 4 years ago )

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

u220e ( 4 years ago )

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:

u220e ( 4 years ago )

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.

slelievre ( 4 years ago )

see more comments

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Set-Intersection Iteration

Comments

1 Answer

Reading about iterators

Answer to the question

Comments

Your Answer

Question Tools

Stats

Related questions

Set-Intersection Iteration savecancel

Comments

1 Answer

Reading about iterators

Answer to the question

Comments

Your Answer

Question Tools

Stats

Related questions

Set-Intersection Iteration