Ask Your Question
1

Set-Intersection Iteration

asked 2020-09-01 01:38:15 +0200

u220e gravatar image

updated 2020-09-02 22:54:02 +0200

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.

edit retag flag offensive close merge delete

Comments

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

FrédéricC gravatar imageFrédéricC ( 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.

u220e gravatar imageu220e ( 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.

slelievre gravatar imageslelievre ( 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)

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

slelievre gravatar imageslelievre ( 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.

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

1 Answer

Sort by » oldest newest most voted
1

answered 2020-09-02 14:49:41 +0200

slelievre gravatar image

updated 2020-09-03 02:06:32 +0200

Reading about iterators

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

check out this tutorial:

Answer to the question

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
edit flag offensive delete link more

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 gravatar imageu220e ( 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.

u220e gravatar imageu220e ( 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.

u220e gravatar imageu220e ( 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:
u220e gravatar imageu220e ( 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.

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

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-09-01 01:38:15 +0200

Seen: 576 times

Last updated: Sep 03 '20