{'fraction_non_alphanumeric': 0.05499153976311337, 'fraction_numerical': 0.016305183817874172, 'mean_word_length': 3.567088162978574, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cyclic Shift Problems on Graphs

We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We first investigate a large class of graphs, which generalizes several classic puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.


Introduction
Recently, variations of reconfiguration problems have been attracting much interest, and several of them are being studied as important fundamental problems in theoretical computer science [8]. Also, many real puzzles which can be modeled as reconfiguration problems have been invented and proposed by the puzzle community, such as the 15-puzzle and Rubik's cube. Among these, we focus on a popular type of puzzle based on cyclic shift operations: see Fig. 1. In these puzzles, we can shift some elements along predefined cycles as a basic operation, and the goal is to rearrange the pieces into a desired pattern.
In terms of reconfiguration problems, this puzzle can be modeled as follows. The input of the problem is a graph G = (V, E), a set of colors Col = {1, 2, . . . , c}, and one colored token on each vertex in V . We are also given a set C of cycles of G. The basic operation on G is called "shift" along a cycle C in C, and it moves each token located on a vertex in C into the next vertex along C. This operation generalizes the token swapping problem, which was introduced by Yamanaka et al. [11], and has been well investigated recently. Indeed, when we restrict each cycle in C to have length two (each cycle would correspond to an edge in E), the cyclic shift problem is equivalent to the token swapping problem.
This work is partially supported by KAKENHI grant numbers 17H06287 and 18H04091. In the mathematical literature, the study of permutation groups and their generators has a long history. An important theorem by Babai [1] states that the probability that two random permutations of n objects generate either the symmetric group S n (i.e., the group of all permutations) or the alternating group A n (i.e., the group of all even permutations) is 1 − 1/n + O(n 2 ). However, the theorem says nothing about the special case where the generators are cycles.
In [4], Heath et al. give a characterization of the permutations that, together with a cycle of length n, generate either A n or S n , as opposed to a smaller permutation group. On the other hand, in [7], Jones shows that A n and S n are the only finite primitive permutation groups containing a cycle of length n − 3 or less. However, his proof is non-constructive, as it heavily relies on the classification of finite simple groups (and, as the author remarks, a self-contained proof is unlikely to exist). In particular, no non-trivial upper bound is known on the distance of two given permutations in terms of a set of generators.
The computational complexity of related problems has been studied, too. It is well known that, given a set of generators, the size of the permutation group they generate is computable in polynomial time. Also, the inclusion of a given permutation π in the group is decidable in polynomial time, and an expression for π in terms of the generators is also computable in polynomial time [2].
In contrast, Jerrum showed that computing the distance between two given permutations in terms of two generators is PSPACE-complete [6]. However, the generators used for the reduction are far from being cycles.
In this paper, after giving some definitions (Section 2), we study the configuration space of a large class of cyclic shift problems which generalize the puzzles in Fig. 1 (Section 3). We show that, except for one special case, the permutation group generated by a given set of cycles is S n if at least one of the cycles has even length, and it is A n otherwise. This result is in agreement with Babai's theorem [1], and shows a similarity with the configuration space of the (generalized) 15-puzzle [10]. Moreover, our proofs in Section 3 are constructive, and yield polynomial upper bounds on the number of shift operations required to reach a given configuration. This is contrasted with Section 4, where we show that finding a shortest sequence of shift operations to obtain a desired configuration is NP-hard, even for puzzles with tokens of only two different colors.

Preliminaries
Let G = (V, E) be a finite, simple, undirected graph, where V is the vertex set, with n = |V |, and E is the edge set. Let Col = {1, 2, . . . , c} be a set of colors, where c is a constant. A token placement for G is a function f : V → Col: that is, f (v) represents the color of the token placed on the vertex v. Without loss of generality, we assume f to be surjective.
Let us fix a set C of cycles in G (note that C does not necessarily contain all cycles of G). Two distinct token placements f and f of G are adjacent with respect to C if the following two conditions hold: (1) there exists a cycle In this case, we say that f is obtained from f by shifting the tokens along the cycle C. If an edge e ∈ E is not spanned by any cycle in C, e plays no role in shifting tokens. Therefore, without loss of generality, we assume that every edge is spanned by at least one cycle in C.
We say that two token placements f 1 and f 2 are compatible if, for each color c ∈ Col, we have f −1 1 (c ) = f −1 2 (c ) . Obviously, compatibility is an equivalence relation on token placements, and its equivalence classes are called compatibility classes for G and Col. For a compatibility class P and a cycle set C, we define the token-shifting graph of P and C as the undirected graph with vertex set P , where there is an edge between two token placements if and only if they are adjacent with respect to C. A walk in a token-shifting graph starting from f and ending in f is called a shifting sequence between f and f , and the distance between f and f , i.e., the length of a shortest walk between them, is denoted as dist(f, f ) (if there is no walk between f and f , their distance is defined to be ∞).
For a given number of colors c, we define the c-Colored Token Shift problem as follows. The input is a graph G = (V, E), a cycle set C for G, two compatible token placements f 0 and f t (with colors drawn from the set Col = {1, 2, . . . , c}), and a non-negative integer . The goal is to determine whether dist(f 0 , f t ) ≤ holds. In the case that is not given, we consider the c-Colored Token Shift problem as an optimization problem that aims at computing dist(f 0 , f t ).

Algebraic Analysis of the Puzzles
For the purpose of this section, the vertex set of the graph G = (V, E) will be V = {1, 2, . . . , n}, and the number of colors will be c = n, so that Col = V , and a token placement on G can be interpreted as a permutation of V . To denote a permutation π of V , we can either use the one-line notation π = [π(1) π(2) . . . π(n)], or we can write down its cycle decomposition: for instance, the permutation [3 6 4 1 7 2 5] can be expressed as the product of disjoint cycles (1 3 4)(2 6)(5 7).
Note that, given a cycle set C, shifting tokens along a cycle (v 1 , v 2 , . . . , v j ) ∈ C corresponds to applying the permutation ( to V . The set of token placements generated by shifting sequences starting from the "identity token placement" f 0 = [1 2 . . . n] is therefore a permutation group with the composition operator, which we denote by H C , and we call it configuration group generated by C. Since we visualize permutations as functions mapping vertices of G to colors (and not the other way around), it makes sense to compose chains of permutations from right to left, contrary to the common convention in the permutation group literature. So, for example, if we start from the identity token placement for n = 5 and we shift tokens along the cycles (1 2 3) and (3 4 5) in this order, we obtain the token placement One of our goals in this section is to determine the configuration groups H C generated by some classes of cycle sets C. Our choice of C will be inspired by the puzzles in Fig. 1, and will consist of arrangements of cycles that share either one or two adjacent vertices. As we will see, except in one special case, the configuration groups that we obtain are either the symmetric group S n (i.e., the group of all permutations) or the alternating group A n (i.e., the group of all even permutations), depending on whether the cycle set C contains at least one even-length cycle or not: indeed, observe that a cycle of length j corresponds to an even permutation if and only if j is odd.
Note that the set of permutations in the configuration group H C coincides with the connected component of the token-shifting graph (as defined in the previous section) that contains f 0 . The other connected components are simply given by the cosets of H C in S n (thus, they all have the same size), while the number of connected components of the token-shifting graph is equal to the index of H C in S n , i.e., n!/|H C |.
The other goal of this section is to estimate the diameter of the token-shifting graph, i.e., the maximum distance between any two token placements f 0 and f t such that f 0 f t . To this end, we state some basic preliminary facts, which are folklore, and can be proved by mimicking the "bubble sort" algorithm. All upper bounds given in Proposition 1 are worst-case asymptotically optimal (refer to [6] for some proofs).

Puzzles with two cycles
We first investigate the case where the cycle set C contains exactly two cycles α and β, either of the form α = (1 2 . . . a) and β = (a a+1 . . . n) with 1 < a < n, or of the form α = (1 2 . . . a) and β = (a − 1 a a + 1 . . . n), with 1 < a ≤ n. The first puzzle is called 1-connected (a, b)-puzzle, where n = a + b − 1, and the second one is called 2-connected (a, b)-puzzle, where n = a + b − 2 (so, in both cases a > 1 and b > 1 are the lengths of the two cycles α and β, respectively). See Fig. 2 for some examples. Note that the Turnstile puzzle in Fig. 1 (left) can be regarded as a 2-connected (6, 6)-puzzle. Proof. Observe that the commutator of α and β −1 is the 3-cycle α −1 βαβ −1 = (a − 1 a a + 1). So, we can apply Proposition 1.2 to the n-cycle αβ = (1 2 . . . n) and the 3-cycle (a − 1 a a + 1) to generate any even permutation in O(n 2 ) shifts. If a and b are odd, then α and β are even permutations, and therefore cannot generate any odd permutation.
On the other hand, if a is even (the case where b is even is symmetric), then the a-cycle α is an odd permutation. So, to generate any odd permutation π ∈ S n , we first generate the even permutation πα in O(n 2 ) shifts, and then we do one extra shift along the cycle α −1 .
Let π ∈ A n be an even permutation of V . In order to generate π, we first move the correct token π(1) to position 1 in O(n) shifts, possibly scrambling the rest of the tokens: let σ be the resulting permutation. If σ is even, then σ −1 π is an even permutation of V \ {1}, and we can generate it in O(n 2 ) shifts as shown before, obtaining π.
On the other hand, if σ is odd, then one of the generators α and β must be odd, too. Since α is a 3-cycle, it follows that β is odd. In this case, after placing the correct token in position 1 via σ, we shift the rest of the tokens along β, and then we follow up with β −1 σ −1 π, which is an even permutation of V \ {1}, and can be generated it in O(n 2 ) shifts. Again, the result is σββ −1 σ −1 π = π. Lemma 2. In a 2-connected (a, b)-puzzle with a ≥ 4 and b ≥ 5, any even permutation can be generated in O(n 2 ) shifts.
Theorem 2. The configuration group of a 2-connected (a, b)-puzzle is: Any permutation in the configuration group can be generated in O(n 2 ) shifts. Proof. By the symmetry of the puzzle, we may assume a ≤ b. The case with a = 2 is equivalent to Proposition 1.1, so let a ≥ 3. If a = 4 or b = 4, then Lemmas 1 and 2 apply, hence we can generate any even permutation in O(n 2 ) shifts: the configuration group is therefore at least A n . Now we reason as in Theorem 1: if a and b are odd, then α and β are even permutations, and cannot generate any odd one. If a is even (the case where b is even is symmetric), then α is an odd permutation. In this case, to generate any odd permutation π ∈ S n , we first generate the even permutation πα in O(n 2 ) shifts, and then we do one more shift along the cycle α −1 to obtain π. The only case left is a = b = 4. To analyze the 2-connected (4, 4)-puzzle, consider the outer automorphism ψ : S 6 → S 6 defined on a generating set of S 6 as follows (cf. Because ψ is an automorphism, the subgroup of S 6 generated by α and β is isomorphic to the subgroup generated by the permutations ψ(α) and ψ(β). Since  1 6)(1 3), and recalling that ψ(π 1 π 2 ) = ψ(π 1 )ψ(π 2 ) for all π 1 , π 2 ∈ S 6 , we have: (1 3) Note that the new generators ψ(α) and ψ(β) both leave the token 4 in place, and so they cannot generate a subgroup larger than S 5 (up to isomorphism). On the other hand, we have ψ(α)ψ(β) = (1 6 2). This 3-cycle, together with the 4-cycle ψ(α), induces a 2-connected (3, 4)-puzzle on {1, 2, 3, 5, 6}: as shown before, the configuration group of this puzzle is (isomorphic to) S 5 . We conclude that the configuration group of the 2-connected (4, 4)-puzzle is isomorphic to S 5 , as well. A given permutation π ∈ S 6 is in the configuration group if and only if ψ(π) leaves the token 4 in place.

Puzzles with any number of cycles
Let us generalize the (a, b)-puzzle to larger numbers of cycles. (As far as the authors know, there are commercial products that have 2, 3, 4, and 6 cycles.) We say that two cycles are properly interconnected if they share exactly one vertex, of if they share exactly two vertices which are consecutive in both cycles. Note that all 1-connected and 2-connected (a, b)-puzzles consist of two properly interconnected cycles. Given a set of cycles C in a graph G = (V, E), let us define the interconnection graphĜ = (C,Ê), where there is an (undirected) edge between two cycles of C if and only if they are properly interconnected. Let us assume |V | > 6 (to avoid special configurations of small size, which can be analyzed by hand), and let C consist of k cycles of lengths n 1 , n 2 , . . . , n k , respectively. We say that C induces a generalized (n 1 , n 2 , . . . , n k )-puzzle on V if there is a subset C ⊆ C such that: (1) C contains at least two cycles; (2) the induced subgraphĜ[C ] is connected; (3) each vertex of G is contained in at least one cycle in C .
When we fix such a subset C , the cycles in C are called relevant cycles, and the vertices of G that are shared by two properly interconnected relevant cycles are called relevant vertices for those cycles. See Fig. 4 for an example of a generalized puzzle. Fig. 4. A generalized puzzle where any permutation can be generated in O(n 5 ) shifts, due to Theorem 3. Note that the blue cycle is the only cycle of even length, and is not properly interconnected with any other cycle. Also, the two red cycles and the two green cycles intersect each other but are not properly interconnected.
The next two lemmas are technical; their proof is found in the Appendix.
Lemma 3. In a generalized puzzle with three relevant cycles, C = {C 1 , C 2 , C 3 }, such that C 1 and C 2 induce a 2-connected (4, 4)-puzzle, any permutation involving only vertices in C 1 and C 2 can be generated in O(n 2 ) shifts. Lemma 4. Let V = {1, . . . , n}, and let W = (w 1 , . . . , w m ) ∈ V m be a sequence such that each element of V appears in W at least once, and any three consecutive elements of W are distinct. Then, the set of 3-cycles C = {(w i−1 w i w i+1 ) | 1 < i < m} can generate any even permutation of V in O(n 3 ) shifts.
Theorem 3. The configuration group of a generalized (n 1 , n 2 , . . . , n k )-puzzle is A n if n 1 , n 2 , . . . , n k are all odd, and it is S n otherwise. Any permutation in the configuration group can be generated in O(n 5 ) shifts.
Proof. Observe that it suffices to prove that the given cycles can generate any even permutation in O(n 5 ) shifts. Indeed, if all cycles have odd length, they cannot generate any odd permutation. On the other hand, if there is a cycle of even length and we want to generate an odd permutation π, we can shift tokens along that cycle, obtaining an odd permutation σ, and then we can generate the even permutation σ −1 π in O(n 5 ) shifts, obtaining π.
Let us fix a set of k ≥ 3 relevant cycles C ⊆ C: we will show how to generate any even permutation by shifting tokens only along relevant cycles. By properties (2) and (3) of generalized puzzles, there exists a walk W on G that visits all vertices (possibly more than once), traverses only edges of relevant cycles, and transitions from one relevant cycle to another only if they are properly interconnected, and only through a relevant vertex shared by them. We will now slightly modify W so that it satisfies the hypotheses of Lemma 4, as well as some other conditions. Namely, if w i−1 , w i , w i+1 are any three vertices that are consecutive in W , we would like the following conditions to hold: (1) w i−1 , w i , w i+1 are all distinct (this is the condition required by Lemma 4); (2) either w i−1 and w i are in the same relevant cycle, or w i and w i+1 are in the same relevant cycle; (3) w i−1 and w i+1 are either in the same relevant cycle, or in two properly interconnected relevant cycles.
To satisfy all conditions, it is sufficient to let W do a whole loop around a relevant cycle before transitioning to the next (note that Lemma 4 applies regardless of the length of W ). The only case where this is not possible is when W has to go through a relevant 2-cycle C = (u 1 u 2 ) that is a leaf in the induced subgraphĜ[C ], such that C shares exactly one relevant vertex, say u 1 , with another relevant cycle C = (v 0 u 1 v 1 v 2 . . . ). To let W cover C in a way that satisfies the above conditions, we set either W = (. . . , v 0 , u 1 , u 2 , v 1 , . . . ) or W = (. . . , v 1 , u 1 , u 2 , v 0 , . . . ): that is, we skip u 1 after visiting u 2 . After this modification, W is no longer a walk on G, but it satisfies the hypotheses of Lemma 4, as well as the three conditions above.
We will now show that the 3-cycle (w i−1 w i w i+1 ) can be generated in O(n 2 ) shifts, for all 1 < i < |W |. By Lemma 4, we will therefore conclude that any even permutation of V can be generated in O(n 2 ) · O(n 3 ) = O(n 5 ) shifts. Due to conditions (2) and (3), we can assume without loss of generality that w i−1 and w i are both in the same relevant cycle C 1 , and that w i+1 is either in C 1 or in a different relevant cycle C 2 which is properly interconnected with C 1 . In the first case, by property (1) of generalized puzzles, there exists another relevant cycle C 2 properly interconnected with C 1 . So, in all cases, C 1 and C 2 induce a 1-connected or a 2-connected (|C 1 |, |C 2 |)-puzzle.
That the 3-cycle (w i−1 w i w i+1 ) can be generated in O(n 2 ) shifts now follows directly from Theorems 1 and 2, except if |C 1 | = |C 2 | = 4 and C 1 and C 2 share exactly two vertices: indeed, the 2-connected (4, 4)-puzzle is the only case where we cannot generate any 3-cycle. However, since we are assuming that V > 6, there must be a third relevant cycle C 3 , which is properly interconnected with C 1 or C 2 . Our claim now follows from Lemma 3.

NP-Hardness for Puzzles with Two Colors
In this section, we show that the 2-Colored Token Shift problem is NP-hard. That is, for a graph G = (V, E), cycle set C, two token placements f 0 and f t for G, and a non-negative integer , it is NP-hard to determine if dist(f 0 , f t ) ≤ . Proof. We will give a polynomial-time reduction from the NP-complete problem 3-Dimensional Matching, or 3DM [3]: given three disjoint sets X, Y , Z, each of size m, and a set of triplets T ⊆ X × Y × Z, does T contain a matching, i.e., a subset M ⊆ T of size exactly m such that all elements of X, Y , Z appear in M ?
Given an instance of 3DM (X, Y, Z, T ), with n = |T |, we construct the instance of the 2-Colored Token Shift problem illustrated in Fig. 5.
The vertex set of G = (V, E) includes the sets X, Y , Z (shown with a green background in the figure: these will be called green vertices), as well as the vertex u. Also, for each triplett i = (x, y, z) ∈ T , with 1 ≤ i ≤ n, the vertex set contains three vertices t i,1 , t i,2 , t i,3 (shown with a yellow background in the figure: these will be called yellow vertices), and the cycle set C has the three cycles (u, t i,1 , t i,2 , t i,3 , x), (u, t i,1 , t i,2 , t i,3 , y), and (u, t i,1 , t i,2 , t i,3 , z) (drawn in blue in the figure). Finally, we have the vertex w, and the vertices v 1 , v 2 , . . . , v 3n−3m ; for each i ∈ {1, 2, . . . , n}, the cycle set C contains the cycle (t i,3 , t i,2 , t i,1 , v 1 , v 2 , . . . , v 3n−3m , w) (drawn in red in the figure). In the initial token placement f 0 , there are black tokens on the 3n vertices of the form t i,j , and white tokens on all other vertices. In the final token placement f t , there is a total of 3m black tokens on all the vertices in X, Y , Z, plus 3n − 3m black tokens on v 1 , v 2 , . . . , v 3n−3m ; all other vertices have white tokens. With this setup, we let = 3n.
It is easy to see that, if the 3DM instance has a matching M = {t i1 ,t i2 , . . . ,t im }, then dist(f 0 , f t ) ≤ . Indeed, for eacht ij = (x j , y j , z j ), with 1 ≤ j ≤ m, we can shift tokens along the three blue cycles containing the yellow vertices t ij ,1 , t ij ,2 , t ij ,3 , thus moving their three black tokens into the green vertices x j , y j , and z j . Since M is a matching, these 3m shifts eventually result in X, Y , and Z being covered by black tokens. Finally, we can shift the 3n − 3m black tokens corresponding to triplets in T \ M along red cycles, moving them into the vertices v 1 , We will now prove that, assuming that dist(f 0 , f t ) ≤ , the 3DM instance has a matching. Note that each shift, no matter along which cycle, can move at most one black token from a yellow vertex to a non-yellow vertex. Since in f 0 there are = 3n black tokens on yellow vertices, and in f t no token is on a yellow vertex, it follows that each shift must cause exactly one black token to move from a yellow vertex to a non-yellow vertex, and no black token to move back into a yellow vertex.
This implies that no black token should ever reach vertex u: if it did, it would eventually have to be moved to some other location, because u does not hold a black token in f t . However, the black token in u cannot be shifted back into a yellow vertex, and therefore it will be shifted into a green vertex along a blue cycle. Since every shift must cause a black token to leave the set of yellow vertices, such a token will move into u: we conclude that u will always contain a black token, which is a contradiction. Similarly, we can argue that the vertex w should never hold a black token.
Let us now focus on a single triplet of yellow vertices t i,1 , t i,2 , t i,3 . Exactly three shifts must involve these vertices, and they must result in the three black tokens leaving such vertices. Clearly, this is only possible if the three black tokens are shifted in the same direction. If they are shifted in the direction of t i,3 (i.e., rightward in Fig. 5), they must move into green vertices (because they cannot go into w); if they are shifted in the direction of t i,1 (i.e., leftward in Fig. 5), they must move into v 1 (because they cannot go into u).
Note that, if a black token ever reaches a green vertex, it can no longer be moved: any shift involving such a token would move it back into a yellow vertex or into u. It follows that the only way of filling all the green vertices with black token is to select a subset of exactly m triplets of yellow vertices and shift each of their black tokens into a different green vertex. These m triplets of yellow vertices correspond to a matching for the 3DM instance.
In the above reduction, we can easily observe that the final token placement f t can always be reached from the initial token placement f 0 in a polynomial number of shifts. Therefore, for this particular set of instances, the 2-Colored Token Shift problem is in NP. The same is also true of the puzzles introduced in Section 3, due to the polynomal upper bound given by Theorem 3. However, we do not know whether this is true for the c-Colored Token Shift problem in general, even assuming c = 2. A theorem of Helfgott and Seress [5] implies that, if f 0 f t , the distance between f 0 and f t has a quasi-polynomial upper bound; this, however, is insufficient to conclude that the problem is in NP. On the other hand, it is not difficult to see that the c-Colored Token Shift problem is in PSPACE; characterizing its computational complexity is left as an open problem. It would also be interesting to establish if the problem remains NP-hard when restricted to planar graphs or to graphs of constant maximum degree.
Otherwise, {j, j } and {k, k } intersect in exactly one element, which we may assume to be j = k , without loss of generality. In this case, σ 1 = σ 2 σ 3 , where σ 3 is defined as above. So, C can generate σ 1 in at most 3i + 1 < 3(i + 1) shifts.
By taking i = n, we conclude that C can generate any 3-cycle on V in at most 3n = O(n) shifts, implying that it can generate any even permutation of V in O(n 3 ) shifts, due to Proposition 1.3.