Browse Groups

• 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 1 of 3 , Nov 14, 2006
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.