[RC5] ogr percentage done - WHY impossible?

bwilson at fers.com bwilson at fers.com
Wed Mar 14 09:44:41 EST 2001


Christian Wirth said:
[quote]
Ok, I believe we have all accepted that d.net cannot calculate the number
of
nodes that have to be tested to solve OGR-25 (etc.). But, I suppose it is
possible to calculate the number of nodes that do exist - when I am rigth
this is a quite simple calculation (for OGR-3 for example, it should be
the
nodes 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1, = 6 nodes). When I am
right
with this interpretation of the OGR-description, the total number of nodes
seems to be N! for OGR-N ... (1,5e25 for OGR 25)
[end quote]

The list you gave only contains three combinations, because a Golumb Ruler
is reversible.  Ruler 1-3-2 is the same as ruler 2-3-1.  However, a
three-mark ruler could also contain 1-4-2, 1-4-3, 4-1-2, 4-1-3, 4-3-1,
4-3-2, and (throw in 5) 1-5-2, 1-5-3, 1-5-4, 2-5-3, 2-5-4...  Work out the
combinations and you can see it rises very quickly.

I have not even attempted to eliminate the rulers where a given length is
measured twice.  For instance, 1-2-3 is not a valid GR because the
distance from 1 to 2 is the same as the distance from 2 to 3.  5-3-2 is
not a valid ruler because it measures the same distance twice.  Let me
illustrate with a text picture of ruler 5-3-2:

a    b  c d
|....|..|.|

Mark A is not named because the ruler obviously has to start somewhere.
Mark B is five units along.  Mark C is 3 units beyond B, and D is 2 beyond
C.  This ruler can measure a distance of five units by measuring from A to
B, or from B to D.  Any ruler which measures the same distance twice is
not a Golumb Ruler.  For the same reason, any ruler which contains the
sequence (5-3-2) cannot be a Golumb Ruler.

The reason we don't have a count of how many nodes must be tested is that
the only way to know how many nodes there are is to count them by
calculating them all.  In other words, if we wanted to know how much work
we'd have to do, we'd have to do all the work first in order to come up
with the count!

__
Bruce Wilson, Manager, FERS Business Services
bwilson at fers.com, 312.245.1750, http://www.fers.com/
PGP KeyID: 5430B995, http://www.lasthome.net/~bwilson/
"Drink your coffee! There are poor people in Africa sleeping!"




rc5 at lists.distributed.net
03/13/2001 22:48


        To:     rc5 at lists.distributed.net
        cc:     (bcc: Bruce Wilson/Chicago/MP/RSMi)
        Subject:        [RC5] ogr percentage done - WHY impossible?



Hi,

Ok, I believe we have all accepted that d.net cannot calculate the number
of
nodes that have to be tested to solve OGR-25 (etc.). But, I suppose it is
possible to calculate the number of nodes that do exist - when I am rigth
this is a quite simple calculation (for OGR-3 for example, it should be
the
nodes 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1, = 6 nodes). When I am
right
with this interpretation of the OGR-description, the total number of nodes
seems to be N! for OGR-N ... (1,5e25 for OGR 25)

Ok, if I am wrong up to here: just ignore the rest!

Now, I know we don't have to test all the nodes (because some can easily
be
determined to be "not better" than the currently best one); so, if we know
the total number of nodes and the ones done, this would be a first step
towards a percentage done ... If someone would figure out a approximation
of
how many nodes we can leave untestested (because of optimizations), it
should be possible to calculate an approximation the percentage of "ogr
done". This would be a more or less guessed approximation, but it would be
a
number and I guess this would make many user very happy ;)

Sorry for confusing you with my bad english and my minimal knowlede about
ogr but I had to tell somebody.

Greets,
Christian Wirth



================
Christian Wirth
wirthi at gmx.at
http://wirthi.cjb.net/

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list