Contando de 1 a n sem números consecutivos

19

Objetivo

Você recebe um número inteiro n( n > 1). Você deve imprimir quantas permutações dos números inteiros 1para nhá que começar no 1, final na n, e não têm dois inteiros consecutivos que diferem em 1.

Como alternativa, se você pegar o gráfico completo K_ne remover as bordas do caminho, 1-2-3-...-ndeverá contar os caminhos hamiltonianos de 1para nno gráfico restante.

Os exemplos serão usados f(n)para uma função que recebe ne gera o número de permutações válidas, mas sua submissão pode ser uma função ou um programa.


Exemplos

Pois n = 6, uma possível solução é1-3-5-2-4-6

No entanto, 1-3-5-2-6-4não é uma solução válida, pois não termina com 6.

De fato, pois n = 6existem apenas 2 soluções ( 1-4-2-5-3-6é a outra).

Por isso f(6) = 2.


Pois n = 4as únicas permutações que começam 1e terminam em 4são 1-2-3-4e 1-3-2-4. Em ambos, o 2é adjacente ao 3, fornecendo números inteiros consecutivos que diferem por 1. Portanto f(4) = 0.


Casos de teste

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

Critério de vitória

Isso é código-golfe, a resposta mais curta vence.

Philippe
fonte
7
Você vê, crianças, você não pode apenas verificar quantas permutações de [2..n-1]não contêm deltas de 1ou -1, você tem que verificar também que nenhum deles começar com 2ou terminar com n-1...
ETHproductions
11
A lista precisa começar com 1 e terminar com o número?
Okx 5/07
3
Talvez o OP signifique "adjacente" e não "consecutivo"?
Stilez 5/07
6
Estranhamente, a sequência está aqui: algo.inria.fr/libraries/autocomb/graphs99.ps, onde na página 6 está escrita 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^14, passo algum tempo agora tentando usar as fórmulas, mas não consigo compor uma que gere a sequência. É incrível ver que o expoente de z é a entrada da fórmula e o resultado é o fator de multiplicação. A um como se pode deduzir a partir da fórmula pode haver uma com a resposta mais curto em bytes
Christiaan Westerbeek
11
@ChristiaanWesterbeek, que é chamada de função geradora da sequência. Existem muitas sequências com uma função geradora que tem uma forma melhor fechada que a própria sequência, é uma coisa legal!
Carmeister

Respostas:

6

MATL , 16 bytes

qtq:Y@0&Yc!d|qAs

Experimente online!

Para entradas excedentes 12, fica sem memória.

Explicação

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
fonte
11
Funcionando bem, bem feito :)
Philippe
11
Embora tenha havido um avanço muito bom nesse problema, sua solução ainda é a mais curta. Também é mais rápido que o da geléia. Congratz!
Philippe
19

Mathematica, 58 bytes, tempo polinomial ( n )

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

Como funciona

Em vez de iterar sobre permutações com força bruta, usamos o princípio de inclusão-exclusão para contá-las combinatoriamente.

Seja S o conjunto de todas as permutações de [1,…, n] com σ 1 = 1, σ n = n , e seja S i o conjunto de permutações σ ∈ S tal que | σ i - σ i + 1 | = 1. Então a contagem que estamos procurando é

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

Agora, | S i 2 ∩ ⋯ S i k - 1 | depende apenas de k e do número j de execuções de índices consecutivos em [ i 1 , i 2 ,…, i k - 1 , i k ] onde, por conveniência, fixamos i 1 = 0 e i k = n . Especificamente,

| S i 2 ∩ ⋯ S i k - 1 | = 2 j - 2 ( n - k ) !, para 2 ≤ jkn ,
| S i 2 ∩ ∩ S i k - 1 | = 1, para j = 1, k = n + 1.

O número desses conjuntos de índices [ i 1 , i 2 ,…, i k - 1 , i k ] com j execuções é

( k - 1 C j - 1 ) ( n - k C j - 2 ), para 2 ≤ jkn ,
1, para j = 1, k = n + 1.

O resultado é então

(−1) n - 1 + ∑ 2 ≤ kn2 ≤ jk (−1) k - 2 ( k - 1 C j - 1 ) ( n - k C j - 2 ) 2 j - 2 ( n - k )!

A soma interior sobre j pode ser escrito usando o hipergeométrico 2 F uma função :

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

à qual aplicamos uma transformação Pfaff que nos permite desviar os poderes de -1 usando um valor absoluto:

(−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
fonte
3
Minha mente é soprado, bom trabalho
Philippe
6

Geléia , 17 16 bytes

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

Um link monádico.

Experimente online!

Quão?

ṖḊŒ!ð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
fonte
Desculpe, mas ele não atende os casos de teste
Philippe
11
Sim, você cometeu o mesmo erro que Okx e eu cometemos no começo. Você tem que conta para o fato de que o segundo número não pode ser 2 e no segundo ao último número não pode ser n-1
ETHproductions
@ Philippe consertou.
Jonathan Allan
Eu não acho que usar IỊṀé válido. Especificamente, e se -2houver um dos deltas lá, por exemplo? Você pode corrigir com IAỊṀ+1.
Erik the Outgolfer
11
@ JonathanAllan Ooh eu pensei que ele retornou x <= 1.
Erik the Outgolfer
5

Japonês , 19 18 bytes

o2 á è_pU äÉ m²e>1

Teste online! Eu não recomendaria testar em algo maior que 10.

Explicação

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
fonte
Bom trabalho! Engraçado como meu código de força bruta não consegue superar n = 13 nem ahah
Philippe
@Philippe Eu não recomendaria aceitar tão rápido, eu tenho certeza que isso vai ser encurtado em 05AB1E ou Jelly ;-)
ETHproductions
Falha no testcase 1.
Okx 05/07/19
2
A @Okx OP especificou que podemos assumir n > 1.
ETHproductions
5

05AB1E , 17 bytes

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

Experimente online!

Okx
fonte
Não está fornecendo os resultados da direita, desculpe
Philippe
@ Philippe Em qual testcase?
Okx 05/07/19
@Philippe Fixed.
Okx 05/07/19
¹1Š)˜salva um byte.
Emigna
5

Haskell, 76 65 bytes

Economizou 11 bytes graças a @xnor.

Usando o resultado da Q_recpágina 7 da descoberta de @ ChristiaanWesterbeek, obtemos

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

Não entendo como o próximo resultado hase relaciona a isso, mas depois de acelerar (primeiro por memorização, veja versões anteriores e depois abaixo), recebo seus números.

Embora o acima seja bom n=20, é essencialmente um exemplo de como não fazer recursão. Aqui está uma versão mais rápida (apenas para n>=6) que também precisaria apenas de memória constante - se apenas os números não continuassem aumentando ...

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

Isso dá

Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096

Também não há problema em obter, f 5000mas não quero colar o resultado ...


BTW, é possível não usar matemática sofisticada e ainda não usar força (ultra) bruta. Primeiro, em vez de examinar todas as permutações, observe as permutações parciais e apenas as estenda quando elas ainda não são inválidas. Não adianta olhar para todas as permutações que começam com 1 6 5. Segundo, algumas permutações parciais gostam 1 3 5 7e 1 5 3 7têm exatamente as mesmas continuações válidas; portanto, manuseie-as juntas. Usando essas idéias, eu poderia calcular os valores n=16 em 0,3s.

Peneiradores cristãos
fonte
Você pode escrever a expressão recursiva mais curto como um ponto extraindo os coeficientes: f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2].
Xnor
@ xnor Certo, obrigado!
Christian Sievers
Este é um bom trabalho, estou surpreso com os resultados que esta comunidade teve! Pena que é um campo de golfe ^^
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
fonte
Parece bem rápido, bom trabalho!
Philippe
2
117 bytes
ovs 5/07/07
3

Mathematica, 66 bytes

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

Explicação

Functioncom o primeiro argumento #.

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 *)
                                                               ]]&
ngenisis
fonte
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)

Abaixo está a versão anterior ao domínio do golfe 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)

Graças à resposta de @ChristianSievers que conseguiu redigir uma solução Haskell a partir de um artigo que eu encontrei após pesquisar '0, 2, 10, 68, 500, 4174, 38774, 397584', aqui está uma versão Javascript que também não permuta.

Uso

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
fonte
11
A descrição da tarefa pede apenas f(n)quando n>1, portanto, não importa para o que você retorna n=1. Também acho que f(1)=1está correto.
Christian Sievers
Você pode combinar os casos especiais n<6?n==1|0:para uma economia adicional de dois caracteres.
Peter Taylor
Ótimo. Eu ajustei para esses 2 comentários.
Christiaan Westerbeek
11
E reordenando termos e confiando na ordem de avaliação é possível chegar até a 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

Braquilog , 26 bytes

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

Experimente online!

Explicação

{                    }ᶜ       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
Fatalizar
fonte
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)

Experimente online!

Removido quatro bytes por não tentar alinhar a função (como sugerido por @shooqie) e outro byte, substituindo-o abspor um quadrado. (Requer Python 3.5 ou superior)

rici
fonte
103 bytes
shooqie
0

Python 2 , 136 bytes

-10 bytes graças a @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*

Experimente online!

Mr. Xcoder
fonte
136 bytes
ovs 5/07/07
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]&])&


casos de teste n: 2 a 12

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

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

Experimente online!

Isso é baseado no artigo de Philippe Flajolet descoberto por @Christiaan Westerbeek ; é muito mais rápido e dois bytes mais curto que minha solução Python 3, que enumera as possíveis permutações. (No Python 3, reducefoi movido irritantemente para functools.)

Existe uma versão muito mais curta usando o produto de pontos da numpy, mas ela transborda rapidamente e requer que a numpy tenha sido importada. Mas pelo que vale a pena:

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
fonte