Re: Orientation of rotationally invariant bit vectors
- From: David Kinny <dnk@xxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Mon, 15 Oct 2007 14:15:01 GMT
In <1192450432.920269.91130@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> acd <acd4usenet@xxxxxxxx> writes:
I am searching for two functions when characterizing equvalence
classes of n-bit bit vectors.
The equivalence classes are defined such that each class contains all
copies of a bit vector obtained by
rotation (cyclic shif).
For example, for n=6, we would have a class containing
010111, 101011, 110101, 111010, 011101, and 101110
I now apply also reflection, e.g.
010111 turns into 111010 (swap highest with lowest digit, second
highest with second lowest digit, ...)
For the example before, we reach the same equivalence class.
But for the class containing
010011 and its rotational equivalences, the reflection leads to a
different class.
I am investigating now two functions, one is unambiguous,
which tells for a given bit vector, whether the two equivalence
classes are equivalent.
Since applying a rotation and a reflection in sequence is equivalend
to a different reflection,
we can just check all reflections.
These are just the involutions of the dihedral group on n points,.
The second function will give an orientation bit in those cases where
the two equivalence classes are different.
In case they are equal the result does not matter.
So the function has the following properties:
it is a n-bit to 1-bit function.
It is rotationally invariant, i.e. for all k: f(v) = f(rot(v,k))
(rot(v,k) denotes the cyclic shift of v by k digits).
(f(v) = not f(reflect(v)) if there is no k, such that reflect(v) =
rot(v,k)
As a simple software implementation, I
calculated
h1 = min(v,rot(v,1),rot(v,2), ...) and
h2 = min(reflect(v),reflect(rot(v,1)),...)
the minimum was taken by interpreting the n-bit string as binary
encoded natural number.
However, this is quite expensive as a cicuit and I am wondering,
whether there are
cheaper ways to implement a function which gives the "orientation".
The problem is related to the "Necklace Problem", interpreted as the
action of a cyclic or dihedral group on words of length n.
It can be understood as considering regular polygons of n points,
where the points are colored,
and I want to know from which side I am looking at it.
I am interested in moderatly sizes of n, say up to 20.
Andreas
Hi. By coincidence I've recently been looking at something similar
to this, except with coarser rotations, i.e. > 1 bit. For example,
h1 = min(v,rot(v,6),rot(v,12),rot(v,18)) and
h2 = min(reflect(v),reflect(rot(v,6)),...) where n = 24.
This is effectively D4 with vertices labelled by a 6 bit number.
In my case I needed a canonical representative of each class,
for which I could simply use min(h1,h2).
The most efficient implementation I could craft for this computed
reflect(v) as a side effect while computing h1, using table lookup
on 6 bits at at time, and then computed h2 as
h2 = min(reflect(v),rot(reflect(v),6),...)
It seems you could certainly use the trick of a k-bit lookup table
for computing reflect(v), and rotating the reflection rather than
reflecting the rotations. Since your n is small you can fit the
vector in a machine integer and do rotations very efficiently.
If all you care about is whether reflect(v) is in the same class
as v, you don't need to do so much work as this. Just generate
reflect(v) once, and compare for equality with v, rot(v,1), ...
You can terminate the loop early if you do find a match.
In fact, you could implement your orientation function as pure table
lookup for n up to say 12, e.g. precompute h1 and h2 for all n.
For larger non-prime n, you could still make use of precomputed
tables to make the computation reasonably efficient.
I suspect for your particular problem there may be a much cleverer
way to do it, something to do with gray codes or similar, but it
doesn't spring to mind at this time of night :-)
HTH,
David
.
- Follow-Ups:
- Re: Orientation of rotationally invariant bit vectors
- From: David Kinny
- Re: Orientation of rotationally invariant bit vectors
- References:
- Prev by Date: Orientation of rotationally invariant bit vectors
- Next by Date: Re: Orientation of rotationally invariant bit vectors
- Previous by thread: Orientation of rotationally invariant bit vectors
- Next by thread: Re: Orientation of rotationally invariant bit vectors
- Index(es):
Relevant Pages
|
