O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B – how is this possible?

Context: I’ve been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.

If

  • s = little string and S = len(s)
  • b = big string and B = len(b)

then I believe it would be something along the lines of (pseudocode):

hs = hash(s) for every position, substring of length S in B:      h_sub = hash(substring)     if hs == h_sub:          print position 

Note that the for loop will run B-S+1 times, so whatever happens inside the loop must be O(1) in order for the whole thing to be O(B).

This assumes that there exists a O(1) hash function hash(s) that only returns the same hash when two words are permutations of each other, and never collide otherwise.

What is this hash function? It seems like you’d have to iterate through every letter in substring to calculate h_sub and I don’t see how that can happen in less than O(S) time. This answer seemed promising but then someone found a non-valid collision.

I learned about the radix-2p hash for this problem in school and we had to prove it as a homework exercise so I am convinced of its correctness.

However in the calculation $ k = \sum_{i=0}^{n-1} x_i(2^{p})^i$ , the exponent on the $ 2^p$ always changes depending on the position of the letter $ x_i$ within the substring, so I don’t see how we can avoid having to iterate anew through all S letters of the substring when we calculate $ k \text{ mod } (2^p-1)$ .

Am I missing something or is there another approach entirely? Thanks.

Formula for number of permutations less than a given permutation in weak order

Let $ w\in S_n$ be a permutation. Is there a reasonable “formula” for the number of elements of the initial interval $ [e,w]$ of weak (Bruhat) order from the identity to $ w$ ?

In terms of what such a “formula” might look like: if $ w$ is a Grassmannian permutation of shape $ \lambda$ then we have $ [e,w]\simeq[\varnothing,\lambda]$ , an initial interval of Young’s lattice, and we can use the determinantal formula of MacMahon mentioned here: Formula for number of edges in Hasse diagram of Young's lattice interval. More generally, if $ w$ is a fully commutative permutation (i.e., is 321-avoiding), then $ [e,w]\simeq [\mu,\lambda]$ for some skew shape $ \lambda/\mu$ , and we can use the linked formula of Kreweras.

Of course what a formula could look like depends on how we encode $ w$ , but I would be happy with anything reasonable (e.g., Lehmer code, co-code, etc.).

Diameter for permutations of bounded support

Let $ S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $ \sigma\in S$ moves $ O(1)$ elements of $ \{1,2,\dotsc,n\}$ . Let $ \Gamma$ be the graph whose set of vertices is the set of ordered pairs $ (i,j)$ , $ 1\leq i,j\leq n$ , $ i\ne j$ , and whose edges are $ ((i,j), (i,j)^\sigma)$ , $ \sigma\in S$ . (In other words, $ \Gamma$ is a Schreier graph.) Assume $ \Gamma$ is connected, i.e., $ S$ generates a $ 2$ -transitive group.

Must it be the case that $ \textrm{diam}(\Gamma) = O(n)$ ? Could it be the case that $ \textrm{diam}(\Gamma)\gg n^{1+\delta}$ , $ \delta>0$ , or even $ \delta=1$ ?

What are the answers to these questions if we assume that $ \langle S\rangle$ is all of $ \textrm{Alt}(n)$ or $ \textrm{Sym(n)}$ ?

How can I compute the permutations multiplication “like” table to a linear list?

I have a table that is structured like this.

table1

I would like to transform the table into the permutations of the table if we treated like a multiplication table. Into a list that looks like this.

enter image description here

Please note I am using a multiplication table as an example. The actual data I am parsing is random. The reason I choose to use a multiplication table data is the lookup method for my table data is performed by the same method. e.g where you check where two different inputs on the x-axes and y-axes and where they converge gives you the value.

Equivalence class of permutations based on cycle decomposition and their inverses

An equivalence class of permutations has come up in my research, and I’m wondering if anybody knows if it’s named or has been studied before. If so, I’d appreciate being pointed towards more information.

Specifically, two permutations are considered equivalent if they have the same cycle decomposition, up to inverses of the cycles. So, for example, the permutations:

$ (123)(456) \equiv (132)(456) \equiv (123)(465) \equiv (132)(465)$

And generally, if the $ \sigma_{i}$ are disjoint cycles, then all permutations

$ \sigma_{1}^{\pm}\sigma_{2}^{\pm} \cdots \sigma_{k}^{\pm}$

are equivalent. As I said, if anybody has seen this before and could point me towards information about it, I’d be most appreciative. Thank you!

Morphing Hypercubes and Odd Permutations

Let $ Q_n$ denote the $ n$ -dimensional hypercube graph and let $ H$ denote a subgraph of $ Q_n$ that is isomorphic to $ Q_{n’}$ , for some input parameter $ n’ \leq n$ (i.e. $ H$ is an $ n’$ -dimensional subcube of $ Q_n$ ). Next, I would like to partition $ H$ into $ 2^{n’ – d}$ vertex disjoint subgraphs $ H_1, \ldots, H_{2^{n’-d}}$ each isomorphic to $ Q_d$ where $ d \leq n’$ .

We can think of each $ H_i$ as a ternary string $ s_i \in \{0, 1, *\}^n$ such that $ s_i$ has exactly $ d$ $ *$ ‘s. These represent free coordinates. For each $ s_i$ , we define a mapping $ f_i : \{0, 1, *\}^n \to \{0, 1, *\}^n$ such that the $ j$ -th coordinate of $ f_i(s_i)$ is a $ *$ if and only if the $ j$ -th coordinate of $ s_i$ is a $ *$ . So intuitively, each $ f_i$ maps a $ d$ -dimensional subcube to another $ d$ -dimensional subcube on the same axes. Let $ H’$ denote the subgraph obtained by decomposing $ H$ as described above and applying the $ f_i$ ‘s on its $ 2^{n’-d}$ pieces. If $ H’$ is also isomorphic to $ Q_{n’}$ , then I call $ H’$ a “morph” of $ H$ .

So my question is the following. Given $ H$ , I would like to apply a sequence of “morph” operations to obtain a graph $ H”$ that “finishes where $ H$ started”. By this, I mean that the ternary string that represents $ H$ must be the same as $ H”$ . However, if we look at the placement of the vertices in $ H$ and $ H”$ , I want them to induce an odd permutation.

To make things clearer, let’s look at a small example. Let $ H$ denote a subgraph isomorphic to $ Q_2$ in $ Q_3$ . In my example, I will take $ H$ to be the graph induced by the vertices with labels $ \{a=000, b=001, c=010, d=011\}$ (i.e. the $ 0**$ face of $ Q_3$ ). Now, consider the following 3 morph operations when $ d=1$ :

1) Partition $ \{a,b,c,d\}$ into pairs $ \{a,b\}$ and $ \{c, d\}$ . These can be represented by ternary strings $ 00*$ and $ 01*$ respectively.We morph $ 00* \to 11*$ and leave $ 01*$ unchanged. This gives us a new graph isomorphic to $ Q_2$ with vertices $ \{a = 110, b = 111, c = 010, d = 011\}$ . Note that $ c$ and $ d$ are unchaged from before. This new square doesn’t have the same “orientation” as the first, since it has ternary string $ *1*$ .

2) Next, partition the newly obtained $ *1*$ into $ *10$ and $ *11$ and we morph $ *10 \to *01$ to obtain the square $ **1$ with labels $ \{a = 101, b = 111, c = 001, d = 011\}$ .

3) Finally, we partition the obtained $ **1$ into $ 1*1$ and $ 0*1$ and morph $ 1*1 \to 0*0$ . This gives us our graph $ H”$ induced by the square $ 0**$ (just as it was with $ H$ ). However, if we look at the new label placements, we see that we have $ \{a = 000, b = 010, c = 001, d=011\}$ . And if we look at the permutation induced by $ a,b,c,d$ , we see that: $ a$ went from $ 000$ to $ 000$ , $ b$ from $ 001$ to $ 010$ , $ c$ went from $ 010$ to $ 001$ and $ d$ went from $ 011$ to $ 011$ . This permutation is an odd permutation as needed.

So now I am interested in the case when $ d=2$ . Does there exists an $ n’$ and $ n$ such that there is a sequence of such “morph” operations that induce an odd permutation?

I can try to add additional details if the question is still unclear. I also apologize for using possibly faulty terminology… I don’t know the best way to frame/word this problem.

Cycle types of permutations from affine group

Let $ V$ be a vector space of dimension $ n$ over the field $ F=\mathrm{GF}(2)$ . We identify $ V$ with the set of columns of length $ n$ over $ F$ . Let $ G = \mathrm{AGL}(V)$ be a group of affine permutations of $ V$ . That is for every $ g\in G$ there exists a square invertible binary matrix $ M$ and vector $ b$ such that for every $ v \in V$ we have $ $ g(v) = Mv + b $ $

It is not hard to find a cycle type of a given prmutation $ g\in G$ . But I don’t know how to find all possible cycle types of permutations from $ G$

My question. Are there any theoretical results, which provide information about all possible cycle types of affine permutations? Or, maybe there are some efficient algorithms for finding all such cycle types?

On the product of two permutations (and its conjugates)

So this is from Charles C. Pinter’s “A Book of Abstract Algebra”- specifically, it’s from the second chapter on permutations. The question is:

Let $ \alpha_1$ and $ \alpha_2$ be cycles of the same length. Let $ \beta_1$ and $ \beta_2$ be cycles of the same length. Let $ \alpha_1$ and $ \beta_1$ be disjoint, and let $ \alpha_2$ and $ \beta_2$ be disjoint. [Prove that] There is a permutation, $ \pi\in S_n$ , such that $ \alpha_1\beta_1=\pi\alpha_2\beta_2\pi^{-1}$ .

That’s the question.

But this is actually the last of a five part question, sooooo here are the previous parts – the parts build on each other and it looks like part 4 (which can be found near the bottom) is of greatest relevance but I can’t quite see how to use it here.

Part 1 was:

Let $ \alpha=(a_1,…,a_s)$ be a cycle and let $ \pi$ be a permutation in $ S_n$ . Then $ \pi\alpha\pi^{-1}$ is the cycle $ (\pi(\alpha_1),…,\pi(\alpha_s))$ .

(a solution can be found here Proof for conjugate cycles)

Part 2 was:

Conclude from part 1: Any two cycles of the same length are conjugates of each other.

The idea here is not too hard to formulate and some formalization is given in a hint which suggests defining a permutation, $ \pi$ , as sending any element not in either cycle to itself, sending all of the elements of one of the cycles, denoted by A, to the other, denoted by B. Finally, define $ \pi$ over B-A as some bijection between B-A and A-B. Now, it is easy to show that $ \pi$ is a permutation and by part 1, that’s enough.

Parts 3 and 4 are straightforward.

Part 3:

If $ \alpha$ and $ \beta$ are disjoint cycles, then $ \pi\alpha\pi^{-1}$ and $ \pi\beta\pi^{-1}$ are disjoint cycles.
(this follows directly from part 1)

And Part 4:

Let $ \sigma$ be a product $ \alpha_1…\alpha_t$ of t disjoint cycles of lengths $ l_1,…,l_t$ , respectively. Then $ \pi\sigma\pi^{-1}$ is also a product of t disjoint cycles of lengths $ l_1,…,l_t$ .
(an easy generalization of part 3)

In the fifth part, I see how one can find a $ \pi$ such that $ \alpha_1=\pi\alpha_2\pi^{-1}$ . I also see how one can find a $ \pi$ such that $ \beta_1=\pi\beta_2\pi^{-1}$ (we can get this via an immediate application of part 2). What I can’t see is how we can ensure that these two $ \pi$ ‘s will be the same (which is what the question seems to be asking). I also can’t see how to use Part 4 here as, on its own, it doesn’t seem enough- it looks to me like we would need, in addition, to show that the act of taking a conjugate could be made ‘onto’ in a sense (and I don’t get how to do that).

Any help appreciated.