3
$\begingroup$

My question is a follow up on Binary sequence count of unique patterns

I understand how to count the number of periodic sequences that can be generated using a specific number of bits (as solved in the link above).

However, I would like to know if there exist some way to generate all the possible unique periodic sequences (without solving for all possible permutations). For example:

given 3 digits, the unique periodic sequences will be:

000

100 (equivalent to: 010,001)

110 (equivalent to: 011,101)

111

Thus, there are four unique periodic sequences that are possible. I have generated those using all possible permutations and reducing them to "canonical" forms. However, given 12 digits, this becomes a heavy task.

Thus, I would like to know if there exist some general representation of all possible unique periodic sequences for a given number of bits (or for a given period) such that by a change of parameter I can get them all.

So far, I have found the following result:

The defining function of periodic sequence of N bits is defined as:

$ f(k) = \sum_{j=1}^{N} a_j(e^{\frac{2\pi}{N}i})^{jk} $

where $i = \sqrt{-1}$ and $k \in [1,2,3,4,...]$.

In order to find the appropriate $a_j$ one may solve the following:

$ \mathbf{E} \mathbf{a} = \text{any combination of 1 and 0 in vector form}$

Here:

$ E_{jk} = (e^{\frac{2\pi}{N}i})^{jk}$ ($j$ and $k$ are integers in $[1,N]$) and $\mathbf{a}$ gathers $a_j$ into vector form.

The interesting thing is that: for any unique periodic binary sequence there will be a distnct $|\mathbf{a}|$ (i.e a vector with absolute values of the components of $\mathbf{a}$ and not its norm) relating to it.

It can be used on permutations but I cannot go on and define a single parameter or equation such that it will result in unique periodic sequences. (and I believe such one exists)

$\endgroup$
  • 1
    $\begingroup$ Are you allowing all permutations or just cycles? It doesn't make a difference for $n = 3$ but will matter for larger $n$. $\endgroup$ – Qudit Oct 6 '17 at 18:21
  • 1
    $\begingroup$ I am allowing just cycles. so for n = 5 for example I have: 10000 which is the unique form equivalent to 01000,00100,00010,00001. (which I do not care for and in fact want to eliminate as options) $\endgroup$ – Snifkes Oct 6 '17 at 18:28
  • 1
    $\begingroup$ What is $0011$ equivalent to? $\endgroup$ – Qudit Oct 6 '17 at 18:31
  • 1
    $\begingroup$ This: 1001,1100,0110 $\endgroup$ – Snifkes Oct 6 '17 at 18:39
1
$\begingroup$

The following provides the periodic sequences with 12 bits in 0.2 seconds (and could be much improved, using C or compiled functions). The idea is to define a canonical form by considering, among all cycles, the one corresponding to the maximal value. In the following Mathematica code, this is done by converting the bits to the decimal base (FromDigits).

can[l_] := Block[{list},  lists = NestList[RotateLeft, l, Length[l] - 1];
              Flatten@MaximalBy[lists, FromDigits[#, 2] &, 1]]

For example can[{1,0,1}] and can[{0,1,1}] both returns {1,1,0}.

Then it suffices to convert all binary numbers from $0$ to $2^{12}$ and remove the duplicates:

PadLeft[#, 12] & /@ Table[can[IntegerDigits[i, 2]], {i, 1, 2^12}] 
   // DeleteDuplicates // AbsoluteTiming

(* {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, 
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1}, 
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0} 
    ...
*)

It takes 5 seconds for 16 digits (again, it can be significantly reduced).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.