0
$\begingroup$

I'm looking for an algorithm to take the entire vector space of length n Boolean vectors and partition it into vectors that are the same up to a rotation of the entries. For example if n=3 the partitions would be: -{(0,0,0)} -{(0,0,1),(0,1,0),(1,0,0)} -{(0,1,1),(1,1,0),(1,0,1)} -{(1,1,1)} One (seemingly slow) way to do this would be to generate the list of all possible Boolean vectors of length n and at each entry of the list generate all vectors that are similar to the original and delete these from the list. Any ideas on a faster algorithm?

$\endgroup$
0
0
$\begingroup$

You can start by computing the sum of the boolean elements per vector. This would give you a permutation invariant metric per vector. You could then cluster the vectors, having same (or similar) sums into same buckets. You could easily use a hashtable for this. The operation is then completed in $O(N)$ time.

$\endgroup$
0
$\begingroup$

Provided the length $N$ of the vectors is large enough to merit it, this is a perfect problem for the discrete Fourier transform. The DFT of a vector $x$ is the vector $\mathcal F x$ with entries

$(\mathcal F x)_k = \sum_{n = 0}^{N - 1}x_ne^{-2\pi ikn/N}$.

If $P_nx$ is the operator which cyclically permutes the vector $x$ by $n$, i.e.

$(P_nx)_k = x_{(k + n)\mod N}$,

then the relation between cyclic permutation and Fourier transform is very simple:

$(\mathcal F P_n x)_k = e^{2\pi ikn/N}(\mathcal F x)_k$.

Once you've computed the DFT of two vectors, with this relation, you can check in $\mathcal O(N)$ time whether they are cyclic permutations of each other by checking whether their DFTs are related according to the last equation. The sum formula for the DFT suggests that it can only be computed in $\mathcal O(N^2)$ time, but by using some cleverness, the DFT can be computed in $\mathcal O(N\log N)$ time; an algorithm to do this is called a fast Fourier transform or FFT. There is probably an implementation of FFTs in whatever language you're using.

$\endgroup$

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