13
2
Background
We define a circular step sequence of order \$n\$ as follows:
$$ a_1, a_2, \dots, a_n = \text{Permutation of } 1 \dots n \\ b_i = \min ( |a_{i+1} - a_i|, n-|a_{i+1} - a_i| ), 1 \le i < n \\ \text{Circular step sequence} \stackrel{\text{def}}{=} b_1, b_2, \dots, b_{n-1} $$
Informally, it is the \$n-1\$ distances between \$n\$ points evenly spaced on a circle, given a permutation of those points.
For example, if we choose a permutation \$1, 3, 6, 2, 4, 5 \$ for \$n = 6\$, we get a circular step sequence of \$2, 3, 2, 2, 1\$. (Refer to the circular layout below.)
1 2
6 3
5 4
On the other hand, a circular step sequence of order 6 cannot have a substring of \$2, 2, 2\$. Regardless of where you start and in which direction you go first, you'll get stuck at the third 2.
Task
Given the value of \$n\$ and a sequence \$b_1, b_2, \dots, b_{n-1}\$ of positive integers, determine if the given sequence can be a circular step sequence of order \$n\$, i.e. there exists a permutation \$a_1, \dots, a_n\$ which leads to the given sequence \$b\$.
Input and output
The elements \$b_i\$ of the input sequence are guaranteed to satisfy \$ 1 \le b_i \le n/2 \$ and \$ b_i \in \mathbb{Z}^+ \$. Also, you can assume \$n \ge 1\$. If \$ n = 1 \$, the only possible \$b\$ is a zero-length sequence. You can omit the number \$n\$ from the input.
For output, you can use truthy/falsy values for your language (swapping is allowed). If such a convention is not defined, you can use two distinct values to represent true/false respectively.
Scoring and winning criterion
Standard code-golf rules apply. The shortest code measured in bytes wins.
Test cases
True
1, [] # permutation: [1]
2, [1] # permutation: [1, 2]
3, [1, 1] # permutation: [1, 2, 3]
4, [1, 1, 1] # permutation: [1, 2, 3, 4]
4, [1, 2, 1] # permutation: [1, 2, 4, 3]
4, [2, 1, 2] # permutation: [1, 3, 2, 4]
5, [1, 2, 2, 1] # permutation: [1, 2, 5, 3, 4]
6, [2, 3, 2, 2, 1] # permutation: [1, 3, 6, 2, 4, 5]
False
4, [2, 2, 1]
5, [2, 2, 1, 1]
6, [1, 2, 2, 2, 3]
6, [3, 2, 1, 1, 2]
7, [2, 2, 3, 1, 2, 2]
Bubbler
Posted 2020-02-24T07:10:58.090
Reputation: 16 616
Related OEIS sequence – Arnauld – 2020-02-24T09:53:37.170
I'd find it more circular if also $b_n$ was defined in the obvious way. – Christian Sievers – 2020-02-24T11:42:20.473
Do the permutations
135642,135624,135462,135426,153462,153426,153264and153246all have the same step sequence22122? – Neil – 2020-02-24T16:33:54.690@Neil Yes, exactly. – Bubbler – 2020-02-24T22:03:30.153
1From the other perspective, $b_1, \dots, b_{n-1}$ is a CSS iff you can choose signs $s_1, \dots, s_{n-1} \in {-1, 1}$ such that the $n$ partial sums of $0 + s_1b_1 + s_2b_2 + \dots$ considered modulo $n$ are a permutation of all the members of $\mathbb{Z}_n$. – Lynn – 2020-02-24T22:49:04.280
As a consequence of @Lynn's observation, the partial sums are a permutation of $Z_n$ exactly if no two are the same modulo $n$, which means that no infix has $s_i b_i + s_{i+1} b_{i+1} + \cdots + s_{j} b_{j} = 0 \bmod n$. – xnor – 2020-02-27T03:07:57.247