Processing math: 7%

First time here? Check out the FAQ!

Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

asked 4 years ago

u220e gravatar image

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 intersetion 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 Sagemath 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.

Set-Intersection Iteration

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

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

(2) When a_j $a_j < b_i, b_i$, check conterminous decreasing indices for elements of B B (i.e., b_{i - 1}, b_{i - 2}, b_{i - 1}, b_{i - 2}, etc.) until a_j a_j b_k b_k for some index k $k < i. If a_j = b_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 a_r = b_s for some indices r r s; s; then, break and print(b_s).

Thanks in advance. advance.

Set-Intersection Iteration

Suppose I have two sets with integral elements $A = {a_1, A = {$a_1, a_2, ... , a_n} and B = {b_1, a_n} and B = {b_1, b_2, ... , b_m}$, 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 nm. Suppose, also, that the intersection of sets A and B is the singleton set {c}, {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}. {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_jb_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_jb_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 rs; then, break and print(b_s).

Thanks in advance.

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 nm. 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_jb_i for some index j < n - 1. If a_j = b_i, break and print(a_j). 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_jb_k for some index k < i. If a_j = b_k, break and print(b_k). 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 rs; then, break and print(b_s).print(b_s).

Thanks in advance.