Objectif

Vous obtenez un entier n( n > 1). Vous devez sortie le nombre de permutations des nombres entiers 1à nil y a qui commencent à la 1fin à n, et n'ont pas deux entiers consécutifs qui diffèrent par 1.

Alternativement, si vous prenez le graphique complet K_net supprimez les bords du chemin, 1-2-3-...-nvous devez compter les chemins hamiltoniens de 1à ndans le graphique restant.

Les exemples utiliseront f(n)pour une fonction qui accepte net génère le nombre de permutations valides, mais votre soumission peut être une fonction ou un programme.

Exemples

Pour n = 6, une solution possible est1-3-5-2-4-6

Cependant, ce 1-3-5-2-6-4n'est pas une solution valable car elle ne se termine pas par 6.

En fait, pour n = 6, il n'y a que 2 solutions ( 1-4-2-5-3-6c'est l'autre).

Par conséquent f(6) = 2.

Car n = 4les seules permutations qui commencent 1et se terminent par 4sont 1-2-3-4et 1-3-2-4. Dans les deux, le 2est adjacent au 3, ce qui donne des entiers consécutifs qui diffèrent de 1. Par conséquent f(4) = 0.

Cas de test

f(6) = 2
f(4) = 0
f(8) = 68
f(13) = 4462848

Critère gagnant

C'est le code-golf, la réponse la plus courte l'emporte.

MATL , 16 octets

qtq:Y@0&Yc!d|qAs

Essayez-le en ligne!

Pour les entrées supérieures, 12il manque de mémoire.

Explication

q      % Implicitly input n. Push n-1
tq     % Duplicate and subtract 1: pushes n-2
:      % Range [1 2 ... n-2]
Y@     % Matrix with all permutations, each in a row
0      % Push 0
&Yc    % Append n-1 and predend 0 to each row
!      % Tranpose
d      % Consecutive differences along each column
|      % Absolute value
q      % Subtract 1
A      % All: true if all values in each column are non-zero
s      % Sum. Implicitly display

Mathematica, 58 octets, temps polynomial ( n )

Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&

Comment ça fonctionne

Plutôt que d'itérer sur les permutations avec force brute, nous utilisons le principe d'inclusion-exclusion pour les compter de manière combinatoire.

Soit S l'ensemble des permutations de [1,…, n] avec σ ₁ = 1, σ _n = n , et soit S _i l'ensemble des permutations σ ∈ S telles que | σ _i - σ _{i + 1} | = 1. Ensuite, le nombre que nous recherchons est

| S | - | S ₁ ∪ ⋯ ∪ S _{n - 1} | = ∑ _{2 ≤ k ≤ n + 1; 1 ≤ i 2 <⋯ < i k - 1 < n} (−1) ^{k - 2} | S _{i 2} ∩ ⋯ ∩ S _{i k - 1} |.

Maintenant, | S _{i 2} ∩ ⋯ ∩ S _{i k - 1} | dépend uniquement de k et du nombre j de séries d'indices consécutifs dans [ i ₁ , i ₂ ,…, i _{k - 1} , i _k ] où pour des raisons de commodité nous fixons i ₁ = 0 et i _k = n . Plus précisément,

| S _{i 2} ∩ ⋯ ∩ S _{i k - 1} | = 2 ^{j - 2} ( n - k ) !, pour 2 ≤ j ≤ k ≤ n ,
| S _{i 2} ∩ ⋯ ∩ S _{i k - 1} | = 1, pour j = 1, k = n + 1.

Le nombre de ces ensembles d'index [ i ₁ , i ₂ ,…, i _{k - 1} , i _k ] avec j exécutions est

( _{k - 1} C _{j - 1} ) ( _{n - k} C _{j - 2} ), pour 2 ≤ j ≤ k ≤ n ,
1, pour j = 1, k = n + 1.

Le résultat est alors

(−1) ^{n - 1} + ∑ _{2 ≤ k ≤ n} ∑ _{2 ≤ j ≤ k} (−1) ^{k - 2} ( _{k - 1} C _{j - 1} ) ( _{n - k} C _{j - 2} ) 2 ^{j - 2} ( n - k )!

La somme intérieure sur j peut être écrit à l' aide du hypergeometric ₂ F ₁ fonction :

(−1) ^{n - 1} + ∑ _{2 ≤ k ≤ n} (−1) ^k ( k - 1) ₂ F ₁ (2 - k , k - n ; 2; 2) ( n - k )!

auquel nous appliquons une transformation Pfaff qui nous permet de jouer au golf les puissances de -1 en utilisant une valeur absolue:

(−1) ^{n - 1} + ∑ _{2 ≤ k ≤ n} (−1) ⁿ ( k - 1) ₂ F ₁ ( k , k - n ; 2; 2) ( n - k )!
= | −1 + ∑ _{1 ≤ k ≤ n} ( k - 1) ₂ F ₁ ( k , k - n ; 2; 2) ( n - k )! |.

Démo

In[1]:= Table[Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&[n],{n,50}]

Out[1]= {1, 0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848, 

>    54455754, 717909202, 10171232060, 154142811052, 2488421201446, 

>    42636471916622, 772807552752712, 14774586965277816, 297138592463202402, 

>    6271277634164008170, 138596853553771517492, 3200958202120445923684, 

>    77114612783976599209598, 1934583996316791634828454, 

>    50460687385591722097602304, 1366482059862153751146376304, 

>    38366771565392871446940748410, 1115482364570332601576605376898, 

>    33544252621178275692411892779180, 1042188051349139920383738392594332, 

>    33419576037745472521641814354312790, 

>    1105004411146009553865786545464526206, 

>    37639281863619947475378460886135133496, 

>    1319658179153254337635342434408766065896, 

>    47585390139805782930448514259179162696722, 

>    1763380871412273296449902785237054760438426, 

>    67106516021125545469475040472412706780911268, 

>    2620784212531087457316728120883870079549134420, 

>    104969402113244439880057492782663678669089779118, 

>    4309132147486627708154774750891684285077633835734, 

>    181199144276064794296827392186304334716629346180848, 

>    7800407552443042507640613928796820288452902805286368, 

>    343589595090843265591418718266306051705639884996218154, 

>    15477521503994968035062094274002250590013877419466108978, 

>    712669883315580566495978374316773450341097231239406211100, 

>    33527174671849317156037438120623503416356879769273672584588, 

>    1610762789255012501855846297689494046193178343355755998487686}

Gelée , 17 16 octets

ṖḊŒ!ð1;;⁹IỊṀðÐḟL

Un lien monadique.

Essayez-le en ligne!

Comment?

ṖḊŒ!ð1;;⁹IỊṀðÐḟL - Link: number n
Ṗ                - pop (implicit range build) -> [1,n-1]
 Ḋ               - dequeue -> [2,n-1]
  Œ!             - all permutations of [2,n-1]
    ð       ðÐḟ  - filter discard those entries for which this is truthy:
     1;          -   1 concatenated with the entry
       ;⁹        -   ...concatenated with right (n)
         I       -   incremental differences
          Ị      -   is insignificant (absolute value <=1)
           Ṁ     -   maximum
               L - length (the number of valid arrangements)

Japt , 19 18 octets

o2 á è_pU äÉ m²e>1

Testez-le en ligne! Je ne recommanderais pas de tester sur quelque chose de plus grand que 10.

Explication

o2 á è_  pU äÉ  m²  e>1
o2 á èZ{ZpU ä-1 mp2 e>1}
                          : Implicit: U = input integer
o2                        : Create the range [2..U-1].
   á                      : Generate all permutations of this range.
     èZ{               }  : Check how many permutations Z return a truthy value:
        ZpU               :   Push U to the end of Z.
            ä-1           :   Push 1 to the beginning of Z, then take the difference
                          :   of each pair of items.
                m         :   Map each item X to
                 p2       :     X ** 2. This gives a number greater than 1 unless the
                          :     item is 1 or -1.
                    e>1   :   Return whether every item in this list is greater than 1.
                          :   This returns `true` iff the permutation contains no
                          :   consecutive pairs of numbers.
                          : Implicit: output result of last expression

05AB1E , 17 octets

L¦¨œʒ¹1Š)˜¥Ä1å_}g

Essayez-le en ligne!

Haskell, 76 65 octets

Enregistré 11 octets grâce à @xnor.

En utilisant le résultat de la Q_recpage 7 de la découverte de @ ChristiaanWesterbeek, nous obtenons

f 1=1
f n|n<6=0
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]

Je ne comprends pas comment leur prochain résultat ha lié à cela, mais après avoir accéléré (d'abord par mémorisation, voir les versions antérieures, puis comme ci-dessous), j'obtiens leurs chiffres.

Bien que ce qui précède soit acceptable n=20, c'est un exemple essentiel pour ne pas faire de récursivité. Voici une version plus rapide (uniquement pour n>=6) qui n'aurait également besoin que d'une mémoire constante - si seulement les chiffres ne continuaient pas d'augmenter ...

f n=last$foldl(#)[1,0,0,0,0][6..n]
l#n=tail l++[sum$zipWith(*)l[n-4,1,10-2*n,4,n-2]]

Ça donne

Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096

Ce n'est pas un problème pour obtenir également f 5000 mais je ne veux pas coller le résultat ...

BTW, il est possible de ne pas utiliser de mathématiques fantaisistes et de ne pas utiliser de force (ultra) brute. Tout d'abord, au lieu de regarder toutes les permutations, regardez les permutations partielles et ne les étendez que lorsqu'elles ne sont pas déjà invalides. Il est inutile de regarder toutes les permutations en commençant par 1 6 5. Deuxièmement, certaines permutations partielles aiment 1 3 5 7et 1 5 3 7ont exactement les mêmes continuations valides, alors gérez-les ensemble. En utilisant ces idées, j'ai pu calculer les valeurs jusqu'à n=16 0,3 s.

Python, 125 octets

from itertools import*
lambda n:sum(p[-1]-p[0]==n-1and all(~-abs(x-y)for x,y in zip(p,p[1:]))for p in permutations(range(n)))

Mathematica, 66 octets

Count[Permutations@Range@#,x:{1,__,#}/;FreeQ[Differences@x,1|-1]]&

Explication

Functionavec le premier argument #.

Count[                                                             (* Count the number of *)
      Permutations@                                                (* permutations of *)
                   Range@#,                                        (* the list {1, ..., #} *)
                           x:{1,__,#}                              (* of the form {1, __, #} *)
                                     /;                            (* such that *)
                                             Differences@x,        (* the list of differences of consecutive elements *)
                                       FreeQ[                      (* is free of elements of the form *)
                                                           1|-1    (* 1 or -1 *)
                                                               ]]&

Javascript (ES6), 100 74 72 60 octets

f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)

Voici la version avant la maîtrise du golf de @PeterTaylor

f=n=>n<6?n==1|0:(n-4)*f(n-5)+f(n-4)-2*(n-5)*f(n-3)+4*f(n-2)+(n-2)*f(n-1)

Merci à la réponse de @ChristianSievers qui a réussi à rédiger une solution Haskell à partir d'un document que j'ai trouvé après avoir googlé '0, 2, 10, 68, 500, 4174, 38774, 397584', voici une version Javascript qui ne permutait pas trop.

Usage

for (i=1; i<=20; i++) {
  console.log(i, f(i))
}

1 1 
2 0 
3 0 
4 0 
5 0 
6 2 
7 10 
8 68 
9 500 
10 4174 
11 38774 
12 397584 
13 4462848 
14 54455754 
15 717909202 
16 10171232060 
17 154142811052 
18 2488421201446 
19 42636471916622 
20 772807552752712

Brachylog , 26 octets

{⟦₁pLh1&~tLs₂ᶠ{-ȧ>1}ᵐ}ᶜ|∧0

Essayez-le en ligne!

Explication

{                    }ᶜ       Output = count the number of outputs of:
 ⟦₁pL                           L is a permutation of [1, …, Input]
    Lh1                         The head of L is 1
       &~tL                     The tail of L is the Input
          Ls₂ᶠ                  Find all sublists of length 2 of L
              {    }ᵐ           Map on each sublist:
               -ȧ>1               The elements are separated by strictly more than 1
                       |      Else (no outputs to the count)
                        ∧0    Output = 0

Python 3 , 109 107 102 102 octets

q=lambda s,x,n:sum(q(s-{v},v,n)for v in s if(v-x)**2>1)if s else x<n;f=lambda n:q({*range(2,n)},1,n-1)

Essayez-le en ligne!

Suppression de quatre octets en n'essayant pas de mettre une ligne sur la fonction (comme suggéré par @shooqie) et d'un autre octet en le remplaçant abspar un carré. (Nécessite Python 3.5+)

Python 2 , 136 octets

-10 octets grâce à @ovs.

lambda n,r=range:sum(x[0]<1and~-n==x[-1]and 2+~any(abs(x[i]-x[i+1])<2for i in r(n-1))for x in permutations(r(n)))
from itertools import*

Essayez-le en ligne!

Mathematica, 134 octets

(s=Permutations@Range[2,#-1];g=Table[Join[Prepend[s[[i]],1],{#}],{i,Length@s}];Length@Select[Union@*Abs@*Differences/@g,FreeQ[#,1]&])&

cas de test n: 2 à 12

{0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584}

Python 2 , 105 octets

lambda n:reduce(lambda a,i:a+[i*a[-5]+a[-4]+2*(1-i)*a[-3]+4*a[-2]+(i+2)*a[-1]],range(2,n),[0,1]+4*[0])[n]

Essayez-le en ligne!

Ceci est basé sur l'article de Philippe Flajolet découvert par @Christiaan Westerbeek ; c'est beaucoup plus rapide et deux octets plus court que ma solution Python 3 qui énumère les permutations possibles. (Dans Python 3, reducea été déplacé de façon agaçante functools.)

Il existe une version beaucoup plus courte utilisant le produit scalaire de numpy, mais qui déborde assez rapidement et nécessite que numpy ait été importé. Mais pour ce que ça vaut:

lambda n:reduce(lambda a,i:a+[dot([i,1,2-2*i,4,i+2],a[-5:])],range(2,n),[0,1]+4*[0])[n]