Given an integer\$N\$ consider a permutation\$p=p_1,p_2,p_3,\ldots\$ of\$1,\ldots,N-1\$. Let\$P = p_1 , p_1+p_2 \bmod N, p_1+p_2+p_3 \bmod N, \ldots\$ be its prefix sums modulo\$N\$. Sometimes\$P\$ will be a permutation of\$1,\ldots,N-1\$ itself.
For example,\$N=4: p=3,2,1 \rightarrow P=3,1,2\$
Negative examples:\$p=2,3,1 \rightarrow P=2,1,2\$ is not a permutation ;\$p=3,1,2 \rightarrow P=3,0,2\$ is a permutation but not of\$1,\ldots,3\$
Your task is to write a program or function that takes\$N\$ and returns the number of permutations\$p\$ of\$1,\ldots,N-1\$ such that\$P\$ is also a permutation of\$1,\ldots,N-1\$.
Rules:
You may return integers or integer-valued numbers.
You may return the\$N\$-th term, the first\$N\$ terms or the entire series.
You may ignore/skip odd\$N\$. If you choose to do so you may take\$N\$ or\$N/2\$ as the input.
Other than that default rules and loopholes for integer sequences apply.
This is code-golf, so shortest code in bytes wins. Different languages compete independently.
First few terms:
\$\begin{align}2 &\rightarrow 1 \\4 &\rightarrow 2 \\6 &\rightarrow 4 \\8 &\rightarrow 24 \\10 &\rightarrow 288\end{align}\$
OEIS has more.
- 1\$\begingroup\$OEIS says the problem is NP hard. I'd be willing to see a solution which isn't brute force\$\endgroup\$Rachit Arora– Rachit Arora2022-06-06 07:16:48 +00:00CommentedJun 6, 2022 at 7:16
- 2\$\begingroup\$Given an integer 1,…,N−1 doesn't make any sense. Perhaps you mean:Given an integer N consider 1,…,N−1. Also the next sentence talks aboutp1,p2 etc without any definition as what they represent.\$\endgroup\$Noodle9– Noodle92022-06-06 12:39:28 +00:00CommentedJun 6, 2022 at 12:39
- \$\begingroup\$@Noodle9 Oops, fixed.\$\endgroup\$Albert.Lang– Albert.Lang2022-06-06 12:43:33 +00:00CommentedJun 6, 2022 at 12:43
12 Answers12
Wolfram Language (Mathematica), 60 bytes
Count[Sort/@Mod[Accumulate/@Permutations[r=Range@#-1],#],r]&
Vyxal, 11 bytes
ɽ:Ṗv¦⁰%vs^OHow?
ɽ:Ṗv¦⁰%vs^Oɽ # exclusive range from 0; range(1, N) : # duplicate top of stack Ṗ # get permutations v¦ # vectorized cumulative sum ⁰ # push N to top of stack % # modulo (vectorizes) vs # vectorized sort ^ # flip stack (so range(1, N) is now on top) O # count number of instances
JavaScript (ES7), 88 bytes
f=(n,m=z=2**n-2,p=o=0,x,g=i=>(q=1<<++i)>m?o+=x==z:g(i,m&q&&f(n,m^q,i+=p,x|1<<i%n)))=>g``How?
We compute the bitmask\$z=2^n-2\$ where the bits\$1\$ to\$n-1\$ are set (e.g.\$n=4\$ gives\$z=14=1110_2\$).
We start with\$m=z\$ and\$x=0\$. We recursively clear the bits of\$m\$ in all possible orders while keeping track of the sum of said bit indices in\$p\$ and setting the bits\$p \bmod n\$ in\$x\$. (Note that we do not need to keep track of the permutation itself.)
We have a solution whenever we end up with\$x=z\$, in which case the output value\$o\$ is incremented.
Husk, 13 bytes
S#omȯOm%¹∫Ptŀ t # tail: all except the first element of ŀ # the sequence 0..N-1;S#o # now, how many times does this occur among P # get all permutations of this mȯ # and for each of them ∫ # get the cumulative sums m%¹ # each modulo the input O # and sort the resultsAlternative, also 13 bytes
LSnm(†%¹∫)Pḣ← ← # decrement the input by 1 ḣ # get the sequence 1..N P # and get all permutations of this; Sn # now get all common elements between this and m( ) # for each permutation ∫ # get the cumulative sums †%¹ # each modulo the inputL # how long is the resulting list of common elements?
K (ngn/k), 23 bytes
{+/~^a?x!+\'a:?>'+!x#x}+!x#x All length x combinations of0 1 ... x-1.a:?>' The unique results of grading up each combination. This gives all permutation, assign these toa:.x!+\' Cumulative sum of each permutation, modulo x.a? Find each row in the result in the list of permutations. This gives nulls for non-permutations.+/~^ Count the non-null values.
Jelly, 9bytes
’Œ!ðÄ%f⁸LA monadic Link that accepts an integer and yields the count of permutations summing to permutations.
How?
’Œ!ðÄ%f⁸L - Link: integer, N’ - decrement -> N-1 Œ! - all permutations of [1..N-1] ð - start a new dyadic chain, f(permutations, N) Ä - cumulative sums (of each of the permutations) % - modulo N f⁸ - filter keep if in (the permutations) L - length
Factor +math.combinatorics math.unicode, 71 bytes
[| n | n [1,b) <permutations> [ dup cum-sum [ n mod ] map ⊂ ] count ]n [1,b) <permutations>Get all the permutations of [1..n) as a virtual sequence.[ ... ] countCount how many of them...dup cum-sum [ n mod ] map ⊂...are supersets of their cumulative sum modulo n.
Burlesque, 30 bytes
J-.ror@Jbcjm{q++pa}x/.%q~[Z]++J # Dup-. # Decrementro # Range 1..N-1r@ # PermutationsJ # Dupbc # Infinite cyclej # Swapm{ # Map q++ # Sum pa # Partial}x/ # Reorder stack.% # Moduloq~[Z] # Zip with contained in permutations++ # Sum (count)
05AB1E, 13bytes
L¨œεηOI%{āQ}OTry it online orverify all test cases.
Explanation:
L # Push a list in the range [1, (implicit) input] ¨ # Remove the last item to make the range [1,input) œ # Get all its permutations ʒ # Filter the permutations by: η # Get all prefixes of the current permutation O # Sum each prefix I% # Modulo the input { # Sort it ā # Push a list in the range [1,length] (without popping) Q # Check if both lists are the same }g # After the filter: pop and push the length # (which is output implicitly as result)
Python, 116 bytes
from itertools import*f=lambda n:(r:=set(range(1,n)))and sum({sum(x[:i])%n for i in r}==r for x in permutations(r))
Haskell, 102 bytes
import Data.Listf n=length$filter((`elem`p).tail.map(`mod`n).scanl(+)0)p where p=permutations[1..n-1]Explore related questions
See similar questions with these tags.