Expand Messages
• ... To clarify on this: You have a _fixed_ set A and want to construct a set B, such that the differences span the interval [0,mn-1], with all members of A and
Message 1 of 3 , Nov 14, 2006
> In the real life of computation, my B set is flexible. I should
> generate k*m numbers is B until the [0,nm] range is covered. So
> actully the real problem is to find optimal k such that the range of
> question is covered. But checking the coverage in O(nm) is way too
> slow. So I need to resolve this before I can worry about k.

To clarify on this: You have a _fixed_ set A and want to construct a set B,
such that the differences span the
interval [0,mn-1], with all members of A and B are in [0,mn-1]?

"Here is a set B that satifies the constraints" or "I have proven that no
such B exists".

Well, i think that unless you construct B, testing abitrarily generated sets
will take you a _long_ time.

Example: Take |A| = 3, |B| = 2. There are (6 choose 3) times (6 choose 2) =
20*15 = 300 possible set combinations.

The only working ones are: A = {1,3,5}, B = {0,1} and A = {3,4,5} and
B={0,3}.

That is 2 out of 300. (m,n are tiny! here)

> Ronny, I guess your test will take O(nm) again to guarantee that the
> entire range is covered, right?

Yes, if you keep track of the numbers you already tested.

Ronny
• No Ronny. A and B are both fixed sets of n and km positive integers, and their elements are not arbitrary. The problem is not to construct A and B, but to
Message 2 of 3 , Nov 14, 2006
No Ronny. A and B are both "fixed" sets of n and km positive integers,
and their elements are not arbitrary. The problem is not to construct
A and B, but to check if their differences cover the range [0,nm].

Best wishes.

Kaveh

--- In primenumbers@yahoogroups.com, "Ronny Edler" <ronny.e@...> wrote:
>
> > In the real life of computation, my B set is flexible. I should
> > generate k*m numbers is B until the [0,nm] range is covered. So
> > actully the real problem is to find optimal k such that the range of
> > question is covered. But checking the coverage in O(nm) is way too
> > slow. So I need to resolve this before I can worry about k.
>
> To clarify on this: You have a _fixed_ set A and want to construct a
set B,
> such that the differences span the
> interval [0,mn-1], with all members of A and B are in [0,mn-1]?
>
> Furthermore, as an answer of your algorithm you need something like:
> "Here is a set B that satifies the constraints" or "I have proven
that no
> such B exists".
>
> Well, i think that unless you construct B, testing abitrarily
generated sets
> will take you a _long_ time.
>
> Example: Take |A| = 3, |B| = 2. There are (6 choose 3) times (6
choose 2) =
> 20*15 = 300 possible set combinations.
>
> The only working ones are: A = {1,3,5}, B = {0,1} and A = {3,4,5} and
> B={0,3}.
>
> That is 2 out of 300. (m,n are tiny! here)
>
> > Ronny, I guess your test will take O(nm) again to guarantee that the
> > entire range is covered, right?
>
> Yes, if you keep track of the numbers you already tested.
>
> Ronny
>
Your message has been successfully submitted and would be delivered to recipients shortly.