[seqfan] Re: Bad pdf file in A002369?

[Joerg Arndt]

Let me make sure I understand, using an example:

For extending http://oeis.org/A266549
I generated all "fixed" paths.
This is reasonable simple to program correctly
and gives simple, hence fast code (instead of
some "intelligent" solution that would be
slow and likely wrong).

For modding out symmetries, I computed
the word of turns (as symbols +, -, and 0
respectively for +90, -90, and 0 degrees)
for each path.

Let that word be T,
rev(T) for the reversed word,  and
neg(T) the word obtained by swapping letters + and -

Only if a turn string is
1) its own cyclic minimum
2) T <= neg(T)
3) T <= rev(T)
4) T <= neg(rev(T))
(where <= compares lexicographically, and modulo rotations)
then that enters the count.

Is this (an example of) what you suggested?


Best regards,   jj

P.S.: If one could make Duval's algorithm for Lyndon words (and
necklaces) modify for prefix conditions (here: self- avoidance) then
mighty speed-ups should be possible.  Duval's algorithm is practically
identical to the one of Fredericksen, Kessler, Maiorana (FKM algorithm
for generating necklaces).  Not sure what name(s) deserve precedence.

* Fred Lunnon <fred.lunnon at gmail.com> [Feb 25. 2018 08:44]:
>   Incidentally, when enumerating objects acted upon by a symmetry group
> --- eg. polyominoes under the group  D_4 (aka  D_8 ) of the square --- it is
> advisable to consider "fixed" counts (ignoring symmetry) rather than "free"
> (modulo symmetry), since any explicit expressions for the counts are
> generally simpler for the fixed case.
> 
>   In practice, brute-force enumeration may well be faster if symmetry
> is `broken' first; but it is generally easy to incorporate additional code
> to reconstruct the fixed contribution corresponding to each free object.
> 
>   Unfortunately many investigators remain apparently unaware of such
> considerations.
> 
> WFL
> 
> [...]