Zählen von 1 bis n ohne fortlaufende Nummern

19

Tor

Sie erhalten eine Ganzzahl n( n > 1). Sie müssen ausgegeben , wie viele Permutationen der ganzen Zahlen 1zu ngibt, die beim Start 1, Ende an n, und haben nicht zwei aufeinanderfolgende ganze Zahlen , die um 1 unterscheiden.

Wenn Sie alternativ das vollständige Diagramm erstellen K_nund die Kanten des Pfads entfernen 1-2-3-...-n, müssen Sie die Hamilton-Pfade von 1bis nim verbleibenden Diagramm zählen.

Die Beispiele werden f(n)für eine Funktion verwendet, die ndie Anzahl der gültigen Permutationen ein- und ausgibt, aber Ihre Einreichung kann eine Funktion oder ein Programm sein.


Beispiele

Denn n = 6eine mögliche Lösung ist1-3-5-2-4-6

Dies 1-3-5-2-6-4ist jedoch keine gültige Lösung, da sie nicht mit endet 6.

Tatsächlich n = 6gibt es für nur 2 Lösungen ( 1-4-2-5-3-6ist die andere).

Daher f(6) = 2.


Denn n = 4die einzigen Permutationen, die in 1und enden, 4sind 1-2-3-4und 1-3-2-4. In beiden 2steht das neben dem 3, was aufeinanderfolgende ganze Zahlen ergibt, die sich um 1 unterscheiden f(4) = 0.


Testfälle

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

Gewinnkriterium

Dies ist Code-Golf, die kürzeste Antwort gewinnt.

Philippe
quelle
7
Sie sehen, Kinder, Sie können nicht nur überprüfen, wie viele Permutationen von [2..n-1]keine Deltas von 1oder enthalten -1, Sie müssen auch überprüfen, ob keine von ihnen 2mit n-1... beginnt oder endet
ETHproductions
1
Muss die Liste mit 1 beginnen und mit der Nummer enden?
Okx
3
Vielleicht bedeutet das OP "nebeneinander", nicht "aufeinanderfolgend"?
Stilez
6
Seltsamerweise ist die Sequenz hier: algo.inria.fr/libraries/autocomb/graphs99.ps, wo auf Seite 6 geschrieben steht Q_ser:=z + 2 z^6 + 10 z^7 + 68 z^8 + 500 z^9 + 4174 z^10 + 38774 z^11 + 397584z^12 + 4462848 z^13 + 54455754 z^14Ich verbringe einige Zeit damit, die Formeln zu verwenden, aber ich kann keine erstellen, die die Sequenz erzeugt. Es ist erstaunlich zu sehen, dass der Exponent von z die Eingabe der Formel und das Ergebnis der Multiplikationsfaktor ist. Diejenige, die die Formel von dort ableiten kann, kann eine mit der kürzesten Antwort in Bytes sein
Christiaan Westerbeek
1
@ChristiaanWesterbeek, die als Erzeugungsfunktion für die Sequenz bezeichnet wird. Es gibt viele Sequenzen mit einer Erzeugungsfunktion, die eine schönere geschlossene Form hat als die Sequenz selbst, es ist cooles Zeug!
Carmeister

Antworten:

6

MATL , 16 Bytes

qtq:Y@0&Yc!d|qAs

Probieren Sie es online!

Bei Eingaben übersteigt 12es den Speicherplatz.

Erläuterung

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
Luis Mendo
quelle
1
Funktioniert gut, gut gemacht :)
Philippe
1
Obwohl es einige wirklich nette Fortschritte in diesem Problem gab, ist Ihre Lösung immer noch die kürzeste. Es ist auch schneller als das Gelee. Herzlichen Glückwunsch!
Philippe
19

Mathematica, 58 Bytes, Polynom ( n ) Zeit

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

Wie es funktioniert

Anstatt mit brachialer Gewalt über Permutationen zu iterieren, verwenden wir die Einschluss-Ausschluss-Prinzip, um sie kombinatorisch zu zählen.

Sei S die Menge aller Permutationen von [1,…, n] mit σ 1 = 1, σ n = n , und sei S i die Menge der Permutationen σ ∈ S, so dass | σ i - σ i + 1 | = 1. Dann ist die Anzahl die wir suchen

| S | - | S 1 ≤ ≤ S n - 1 | = ≤ 2 ≤ kn + 1; 1 ≤ i 2 <⋯ < i k - 1 < n (-1) k - 2 | S i 2 ∩ ⋯ ∩ S i k - 1 |.

Nun ist | S i 2 ≤ ≤ S i k - 1 | hängt nur von k und von der Anzahl j von Läufen aufeinanderfolgender Indizes in [ i 1 , i 2 ,…, i k - 1 , i k ] ab, wobei wir der Einfachheit halber i 1 = 0 und i k festlegen = n . Speziell,

| S i 2 ≤ ≤ S i k - 1 | = 2 j - 2 ( n - k ) !, für 2 ≤ jkn ,
| S i 2 ≤ ≤ S i k - 1 | = 1, für j = 1, k = n + 1.

Die Anzahl solcher Indexmengen [ i 1 , i 2 ,…, i k - 1 , i k ] mit j Läufen ist

( K - 1 C j - 1 ) ( n - k C j - 2 ), für 2 ≤ jkn ,
1, für j = 1, k = n + 1.

Das Ergebnis ist dann

(-1) n - 1 + Σ 2 ≤ kn Σ 2 ≤ jk (-1) k - 2 ( k - 1 C j - 1 ) ( n - k C j - 2 ) 2 j - 2 ( n - k )!

Die innere Summe über j kann mit der hypergeometrischen 2 F 1 -Funktion geschrieben werden :

(–1) n - 1 + ≤ 2 ≤ kn (–1) k ( k - 1) 2 F 1 (2 - k , k - n ; 2; 2) ( n - k )!

auf die wir eine Pfaff-Transformation anwenden, mit der wir die Potenzen von −1 mit einem absoluten Wert abschätzen können:

(−1) n - 1 + ≤ 2 ≤ kn (−1) n ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k )!
= | - 1 + ≤ 1 ≤ kn ( k - 1) 2 F 1 ( k , k - n ; 2; 2) ( n - k !) |.

Demo

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}
Anders Kaseorg
quelle
3
Mein Verstand ist überwältigt, gute Arbeit
Philippe
6

Jelly , 17 16 Bytes

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

Eine monadische Verbindung.

Probieren Sie es online!

Wie?

ṖḊŒ!ð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)
Jonathan Allan
quelle
Sorry, aber es erfüllt nicht die Testfälle
Philippe
1
Ja, du hast den gleichen Fehler gemacht, den Okx und ich zuerst gemacht haben. Sie müssen berücksichtigen, dass die zweite Ziffer nicht 2 und die vorletzte Ziffer nicht n-1 sein kann
ETHproductions
@Philippe hat es repariert.
Jonathan Allan
Ich denke nicht, dass die Verwendung IỊṀgültig ist. Was -2ist zum Beispiel , wenn dort eines der Deltas ist? Sie können mit IAỊṀfür +1 beheben .
Erik der Outgolfer
1
@ JonathanAllan Ooh, ich dachte, es kehrt zurück x <= 1.
Erik der Outgolfer
5

Japt , 19 18 Bytes

o2 á è_pU äÉ m²e>1

Online testen! Ich würde nicht empfehlen, auf etwas größer als zu testen 10.

Erläuterung

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
ETHproductions
quelle
Gut gemacht! Komisch, wie mein Brute-Force-Code weder n = 13 noch ahah
Philippe
@Philippe Ich würde nicht empfehlen, so schnell zu akzeptieren, ich bin sicher, dass dies in 05AB1E oder Jelly kürzer sein wird ;-)
ETHproductions
Schlägt im Testfall fehl 1.
Okx
2
@Okx OP hat angegeben, dass wir davon ausgehen können n > 1.
ETHproductions
5

05AB1E , 17 Bytes

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

Probieren Sie es online!

Okx
quelle
Es liefert nicht die richtigen Ergebnisse, sorry
Philippe
@Philippe Auf welchem ​​Testfall?
Okx
@Philippe Behoben.
Okx
¹1Š)˜Speichert ein Byte.
Emigna
5

Haskell, 76 65 Bytes

11 Bytes dank @xnor gespeichert.

Wenn Q_recwir das Ergebnis für auf Seite 7 von @ ChristiaanWesterbeeks Fund verwenden, erhalten wir

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

Ich verstehe nicht, wie ihr nächstes Ergebnis aussehen wird ha bezieht, aber nach dem Beschleunigen (zuerst durch Auswendiglernen, siehe frühere Versionen, dann wie unten) erhalte ich ihre Zahlen.

Während das oben Genannte in Ordnung ist n=20, ist es wesentlich ein Beispiel, wie man keine Rekursion macht. Hier ist eine schnellere Version (nur für n>=6), die auch nur konstanten Speicher benötigt - wenn nur die Zahlen nicht weiter steigen würden ...

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]]

Das gibt

Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096

Es ist kein Problem, es auch zu bekommen, f 5000aber ich möchte das Ergebnis nicht einfügen ...


Übrigens ist es möglich, keine ausgefallene Mathematik zu verwenden und trotzdem keine (ultra-) rohe Gewalt anzuwenden. Anstatt alle Permutationen zu betrachten, betrachten Sie zunächst Teilpermutationen und erweitern Sie sie nur, wenn sie noch nicht ungültig sind. Es hat keinen Sinn, alle Permutationen zu betrachten, die mit beginnen 1 6 5. Zweitens mögen 1 3 5 7und 1 5 3 7haben einige partielle Permutationen genau die gleichen gültigen Fortsetzungen. Behandeln Sie sie also zusammen. Mit diesen Ideen könnte ich die Werte bis zu n=16 0,3s berechnen.

Christian Sievers
quelle
Sie können die rekursive Ausdruck kürzer wie ein Punkt schreiben die Koeffizienten durch Extraktion aus: f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2].
xnor
@xnor Richtig, danke!
Christian Sievers
Das ist eine gute Arbeit, ich bin erstaunt über die Ergebnisse dieser Community! Schade, dass es ein Golf ist ^^
Philippe
4

Python, 125 Bytes

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)))
shooqie
quelle
Sieht ziemlich schnell aus, gute Arbeit!
Philippe
2
117 Bytes
Ovs
3

Mathematica, 66 Bytes

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

Erläuterung

Functionmit erstem 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 *)
                                                               ]]&
Genisis
quelle
3

Javascript (ES6), 100 74 72 60 Bytes

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

Unten ist die Version vor der Golf-Meisterschaft von @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)

Dank der Antwort von @ChristianSievers, die es geschafft hat, eine Haskell-Lösung aus einem Papier zu entwerfen , das ich nach dem googeln von '0, 2, 10, 68, 500, 4174, 38774, 397584' gefunden habe, ist hier eine Javascript-Version, die auch nicht permutiert.

Verwendung

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
Christiaan Westerbeek
quelle
1
In der Aufgabenbeschreibung wird nur nach dem f(n)Zeitpunkt gefragt n>1, sodass es keine Rolle spielt, wofür Sie zurückkehren n=1. Auch ich finde f(1)=1das richtig.
Christian Sievers
Sie können die Sonderfälle n<6?n==1|0:für eine weitere Zwei-Zeichen-Speicherung kombinieren .
Peter Taylor
Groß. Ich habe mich auf diese 2 Kommentare eingestellt.
Christiaan Westerbeek
1
Und wenn Sie die Begriffe neu ordnen und sich auf die Reihenfolge der Bewertungen verlassen, können Sie bis zu 60 f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)
Peter Taylor,
1

Brachylog , 26 Bytes

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

Probieren Sie es online!

Erläuterung

{                    }ᶜ       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
Tödlich
quelle
1

Python 3 , 109 107 102 Bytes

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)

Probieren Sie es online!

Es wurden vier Bytes entfernt, indem nicht versucht wurde, die Funktion in einer Zeile (wie von @shooqie vorgeschlagen) und ein weiteres Byte durch absein Quadrat zu ersetzen . (Benötigt Python 3.5+)

rici
quelle
103 Bytes
Shooqie
0

Python 2 , 136 Bytes

-10 Bytes dank @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*

Probieren Sie es online!

Mr. Xcoder
quelle
136 Bytes
Ovs
0

Mathematica, 134 Bytes

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


Testfälle n: 2 bis 12

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

J42161217
quelle
0

Python 2 , 105 Bytes

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]

Probieren Sie es online!

Dies basiert auf der Arbeit von Philippe Flajolet, die von @Christiaan Westerbeek entdeckt wurde . Es ist viel schneller und zwei Bytes kürzer als meine Python 3-Lösung, die die möglichen Permutationen auflistet. (In Python 3 reducewurde ärgerlicherweise nach verschoben functools.)

Es gibt eine viel kürzere Version mit numpy's dot product, die jedoch sehr schnell überläuft und den Import von numpy erfordert. Aber wofür es sich lohnt:

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]
rici
quelle