Digamos que seu trabalho é pintar postes, e um cliente pede para você pintar um poste com 4 seções vermelhas e 3 seções amarelas. Você pode fazer isso com muita facilidade da seguinte maneira:

r y r y r y r

Com apenas listras amarelas e vermelhas. Agora, digamos que seu cliente solicite que você pinte um poste com 2 seções vermelhas, 2 seções amarelas e 1 seção verde . Existem algumas maneiras de pintar o seu poste

g y r y r
y g r y r
y r g y r
y r y g r
y r y r g
g r y r y
r g y r y
r y g r y
r y r g y
r y r y g
y r g r y
r y g y r

Mais precisamente, são 12 maneiras de pintar o poste. Isso explode mais cores e seções envolvidas

Agora, se o seu cliente disser que deseja 3 seções vermelhas e 1 seção amarela, não há como pintar um poste assim. Como não importa como você tenta organizar as seções, duas seções vermelhas tocarão e, quando duas seções vermelhas tocarem, elas se tornarão uma única seção vermelha.

E essa é praticamente a nossa única regra para pintar postes

Seções adjacentes podem não ser da mesma cor

Tarefa

Dada uma lista de cores e seções necessárias, imprima o número de maneiras possíveis de pintar um poste, conforme solicitado. Você pode representar cores de qualquer maneira razoável (números inteiros, caracteres, seqüências de caracteres), mas nunca receberá mais de 255 cores diferentes por vez. Se desejar, você pode optar por não atribuir nomes às cores e apenas fazer uma lista das contagens de seção, se isso for mais fácil.

Casos de teste

Eles são difíceis de calcular manualmente, principalmente à medida que aumentam. Se alguém tiver um caso de teste sugerido, eu o adicionarei.

[4,3]    -> 1
[2,2,1]  -> 12
[3,1]    -> 0
[8,3,2]  -> 0
[2,2,1,1]-> 84

Mathematica, 37 44 48. 60 62 bytes

Tome entrada como uma lista de números inteiros {1, 1, 1, 2, 2}. Experimente na Wolfram Sandbox .

Método de correspondência de padrões, obrigado @Não é uma árvore!

Count[Split/@Permutations@#,{{_}..}]&

Splitdivide uma lista única em sublistas de elementos consecutivos, por exemplo, {1, 1, 2, 3, 4, 4}em{{1, 1}, {2}, {3}, {4, 4}}

{{_}..}é, ou seja {{_}, {_}, {_}, ...},. O padrão corresponde a uma lista de sublistas unárias.

Differences método, 48 bytes:

Tr@Abs@Clip[1##&@@@Differences/@Permutations@#]&

O código usa Differencespara determinar se os elementos adjacentes são os mesmos.

Passo a passo:

1. Permutations@# gera todas as permutações da lista de entrada em uma lista N! * N.
2. Differences/@ calcula a diferença entre N elementos e gera uma lista N! * (N-1).
3. 1##&@@@calcula a multiplicação de todas as listas. Se uma lista contiver 0(dois elementos adjacentes são iguais), o resultado será 0, caso contrário, diferente de zero, para um N! Lista.
4. Clip[]age como Sign[], transformar a lista de (-inf, inf) para [-1, 1]
5. Tr@Abstransforma tudo -1em 1e agora a lista de comprimento N! contém apenas 0(inválido) e 1(válido). Então, apenas somamos a lista.

Geléia , 7 bytes

Œ!QIẠ€S

Experimente online!

Toma entrada como por exemplo [1,1,1,1,2,2,2]para [4,3]. O [8,3,2]testcase leva muito tempo para ser executado no TIO.

Como funciona

Œ!QIẠ€S - main link, input as a list
Œ!      - all permutations
  Q     - remove duplicates
   I    - take increments (returns a 0 for two adjacent identical numbers)
    Ạ€  - apply “all” atom to each: 0 for containing 0 and 1 otherwise
      S - sum

05AB1E , 7 bytes

œÙ€¥PĀO

Experimente online!

-1 graças a nmjcman101 em outra resposta.

Mathematica, 50 bytes

Expand[1##&@@(LaguerreL[#,-1,x](-1)^#)]/._^i_:>i!&

Experimente em matemática ou na caixa de areia Wolfram !

Recebe informações como nos casos de teste - por exemplo, {4,3}significa "4 listras vermelhas, 3 listras amarelas".

Esta é uma implementação ingênua de uma fórmula que encontrei aqui . "Ingênuo" significa "Eu não tenho idéia de como a matemática funciona, então, por favor, não me peça uma explicação ..."

Python 3.5 , 65 bytes

f=lambda s,p=0:sum(f(s.replace(c,'',1),c)for c in{*s}-{p})or''==s

Experimente online!

Ruby 2.4, 47 bytes

A entrada é uma lista de caracteres: Para o caso de teste [4,3], a entrada pode ser %w[a a a a b b b], "1111222".charsou algum outro método de formatação matriz que é válida em Ruby.

->x{x.permutation.uniq.count{|a|a*''!~/(.)\1/}}

Requer 2.4 para Enumerator#uniq(as versões anteriores apenas o disponibilizavam noArray classe). Como tal, o link TIO adiciona 5 bytes para converter primeiro o enumerador de permutação em uma matriz to_a, uma vez que não possui a função acima.

Experimente online!

R, 72 bytes

pryr::f(sum(sapply(unique(combinat::permn(x)),pryr::f(!sum(!diff(x))))))

Cria a função

function (x) 
{
    sum(sapply(unique(combinat::permn(x)), pryr::f(!sum(!diff(x)))))
}

É inserido no formulário de [1,1,1,1,2,2,2]acordo com o comentário do Erik the Outgolfer. Usa combinata permnfunção para criar uma lista de todas as permutações e uniqueobter todas as entradas distintas. sapplyaplica a seguinte função em todas as entradas:

pryr::f(!sum(!diff(x)))

O que avalia como

function (x) 
!sum(!diff(x))

Observe que isso xnão é o mesmo xda entrada da grande função. Usar outro caractere nessa função enganaria, pryr::facreditando que a grande função precisa de outro argumento.

De qualquer forma, quando dada uma permutação, esta função toma a diferença entre o vector: 2 1 3 4 2 1 -> -1 2 1 -2 -1. !converte zero FALSEe zeros em TRUE, para que o vetor se torne FALSE FALSE FALSE FALSE FALSE. Somando isso, para verificar se há algum TRUEs ( TRUEimplicaria diff=0-> dois os mesmos números consecutivos). Podemos novamente inverter isso com !para obter um valor booleano se há ou não valores consecutivos na permutação.

A soma desses booleanos nos dá o número total de permutações onde esse não é o caso.

Não funciona para o [8,3,2]testcase porque requer um vetor de 46 GB para armazenar essas permutações.

Gelatina , 11 bytes

Œ!Q⁻2\Ạ$ÐfL

Experimente online!

Python 2 , 140 89 bytes

O formato de entrada é 'aaaabbb'para o caso de teste [4,3].

lambda s:len({p for p in permutations(s)if all(map(cmp,p,p[1:]))})
from itertools import*

Experimente online!

Casca , 8 bytes

#ȯ¬ṁtguP

Experimente online! Recebe entrada no formato "aaabb"para [3,2]. Tempos limite no caso de teste mais longo.

Explicação

Nada extravagante aqui, apenas contando as permutações únicas em que todos os grupos de elementos adjacentes têm comprimento 1.

#ȯ¬ṁtguP
       P  Permutations.
      u   Remove duplicates.
#ȯ        Count how many satisfy the following condition:
     g    group adjacent elements,
   ṁt     concatenate tails of groups
  ¬       and negate.

Ruby, 84 76 bytes

f=->a,x=p{i=s=0;a.map{a[i-=1]-=1;a[i]<0||i!=x&&s+=f[a,i];a[i]+=1}.max>0?s:1}

Uma função lambda recursiva. Analisa cada cor possível e administra uma pesquisa em árvore recursiva, contando o número de vezes que usa todas as faixas.

Explicação (para versão antiga):

f=->
  a, # a is the input array in [3,3,4] form
  x = -1 # x is the last color placed (-1 when run normaly, used in recursive calls)
{
  j = i = s = 0;
  # i is the index
  # s is the sum of valid final patterns (the answer)
  # j is used to count the total stripes

  a.map{|e| # Iterate over array of colors

    a[i] -= 1; # remove a stripe of current color (the array will be used in recursive call)

    s += f[a,i] if i!=x && e>0;
      # add to sum recursively if:
        # we are not using the same color as the last color AND
        # we have stripes of the current color left to paint

    a[i] += 1; # replace the stripe we removed above 

    j += a[i]; # add stripes to j

    i+=1 # increment the index

  }; # End loop

  j == 0 ? 1 : s
  # if we had stripes, give the recursive sum, otherwise return 1 
}

MATL , 11 8 bytes

Y@Xu!dAs

O formato de entrada é [1 1 1 1 2 2 2]para[4 3] etc.

Fica sem memória para o último caso de teste.

Experimente online!

Explicação

Y@    % Implicit input. Matrix of all permutations. Each row is a permutation
Xu    % Unique rows
!     % Transpose
d     % Consecutive differences along each column
A     % All: true for columns such that all its entries are nonzero
s     % Sum. Implicitly display