Powiedzmy, że Twoim zadaniem jest malowanie tyczek, a klient prosi o pomalowanie tyczki za pomocą 4 czerwonych odcinków i 3 żółtych odcinków. Możesz to zrobić dość łatwo w następujący sposób:

r y r y r y r

Tylko żółte i czerwone paski. Powiedzmy teraz, że klient prosi o pomalowanie słupa za pomocą 2 czerwonych sekcji, 2 żółtych sekcji i 1 zielonej sekcji . Istnieje kilka sposobów na pomalowanie słupa

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

Dokładniej, to 12 sposobów na pomalowanie słupa. To wysadza więcej kolorów i sekcji, które są zaangażowane

Teraz, jeśli klient mówi, że chce 3 czerwonych sekcji i 1 żółtej sekcji, nie ma sposobu, aby pomalować taki słup. Ponieważ bez względu na to, jak spróbujesz ułożyć sekcje, dwie czerwone sekcje się dotkną, a gdy dwie czerwone sekcje się dotkną, staną się pojedynczą czerwoną sekcją.

I to właściwie nasza jedyna zasada malowania tyczek

Sąsiednie sekcje mogą nie być tego samego koloru

Zadanie

Biorąc pod uwagę listę wymaganych kolorów i przekrojów, podaj liczbę możliwych sposobów pomalowania słupa zgodnie z życzeniem. Możesz przedstawiać kolory w dowolny rozsądny sposób (liczby całkowite, znaki, łańcuchy), ale nigdy nie otrzymasz więcej niż 255 różnych kolorów jednocześnie. Jeśli chcesz, możesz nawet nie mieć nazw kolorów i po prostu zrób listę sekcji, jeśli jest to łatwiejsze.

Przypadki testowe

Są one trudne do obliczenia ręcznie, zwłaszcza gdy stają się większe. Jeśli ktoś ma sugerowany przypadek testowy, dodam go.

[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 bajty

Weź dane jako listę liczb całkowitych {1, 1, 1, 2, 2}. Wypróbuj na Wolfram Sandbox .

Metoda dopasowywania wzorów, dzięki @Nie drzewo!

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

Splitdzieli pojedynczą listę na podlisty kolejnych elementów, np. {1, 1, 2, 3, 4, 4}na{{1, 1}, {2}, {3}, {4, 4}}

{{_}..}jest mianowicie {{_}, {_}, {_}, ...}. Wzór pasuje do listy pojedynczych podlist.

Differences metoda, 48 bajtów:

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

Kod używa Differencesdo ustalenia, czy sąsiednie elementy są takie same.

Krok po kroku:

1. Permutations@# generuje wszystkie permutacje listy wejściowej do listy N! * N.
2. Differences/@ oblicza różnicę między N elementami i daje listę N! * (N-1).
3. 1##&@@@oblicza pomnożenie wszystkich list. Jeśli lista zawiera 0(dwa sąsiednie elementy są takie same), wynik będzie 0, w przeciwnym razie niezerowy, na N! lista.
4. Clip[]działa jak Sign[], przekształca listę z (-inf, inf) na [-1, 1]
5. Tr@Abszamienia wszystko -1w, 1a teraz lista długości N! zawiera tylko 0(niepoprawne) i 1(ważne). Podsumowujemy więc listę.

Galaretka , 7 bajtów

Œ!QIẠ€S

Wypróbuj online!

Pobiera dane wejściowe jak np . [1,1,1,1,2,2,2]Dla [4,3]. [8,3,2]Testcase trwa zbyt długo, aby uruchomić na TIO.

Jak to działa

Œ!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 bajtów

œÙ€¥PĀO

Wypróbuj online!

-1 dzięki nmjcman101 na innej odpowiedzi.

Mathematica, 50 bajtów

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

Wypróbuj w Mathics lub w piaskownicy Wolfram !

Pobiera dane jak w przypadkach testowych - np. {4,3}Oznacza „4 czerwone paski, 3 żółte paski”.

To naiwne wdrożenie wzoru, który tu znalazłem . „Naiwny” oznacza „nie mam pojęcia, jak działa matematyka, więc proszę nie pytaj mnie o wyjaśnienia…”

Python 3.5 , 65 bajtów

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

Wypróbuj online!

Ruby 2.4, 47 bajtów

Wejście znajduje się lista znaków: Dla przypadku testowego [4,3], wejście może być %w[a a a a b b b], "1111222".charsalbo jakaś inna metoda formatowania tablica to ważne w Ruby.

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

Wymaga wersji 2.4 dla Enumerator#uniq(wcześniejsze wersje posiadały ją tylko w Arrayklasie). Jako taki, łącze TIO dodaje 5 bajtów, aby najpierw przekonwertować moduł wyliczający permutację na tablicę to_a, ponieważ nie ma powyższej funkcji.

Wypróbuj online!

R, 72 bajty

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

Tworzy funkcję

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

Pobiera dane w formularzu [1,1,1,1,2,2,2]zgodnie z komentarzem Erika the Outgolfer. Zastosowania combinat„s permnfunkcja utworzyć listę wszystkich permutacji, a następnie unique, aby uzyskać wszystkie odrębne pozycje. sapplynastępnie stosuje następującą funkcję do wszystkich wpisów:

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

Który ocenia na

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

Zauważ, że to x nie to samo, co na xwejściu dużej funkcji. Użycie innej postaci w tej funkcji mogłoby doprowadzić pryr::fdo przekonania, że ​​duża funkcja wymaga kolejnego argumentu.

W każdym razie, gdy podaje się permutacji, funkcja do kwadratu różnicę pomiędzy wektorem: 2 1 3 4 2 1 -> -1 2 1 -2 -1. !konwertuje niezerowe na FALSEi zera na TRUE, więc wektor staje się FALSE FALSE FALSE FALSE FALSE. Podsumowując, aby sprawdzić, czy są jakieś TRUEs ( TRUEoznaczałoby todiff=0 -> dwie takie same kolejne liczby). Możemy ponownie odwrócić to za pomocą, !aby uzyskać wartość logiczną określającą, czy w permutacji występują kolejne wartości.

Podsumowanie tych boolanów daje nam całkowitą liczbę permutacji, w których tak nie jest.

Nie działa dla przypadku [8,3,2]testowego, ponieważ wymaga wektora 46 GB do przechowywania tych permutacji.

Galaretka , 11 bajtów

Œ!Q⁻2\Ạ$ÐfL

Wypróbuj online!

Python 2 , 140 89 bajtów

Format wejściowy jest 'aaaabbb'dla przypadku testowego [4,3].

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

Wypróbuj online!

Łuska , 8 bajtów

#ȯ¬ṁtguP

Wypróbuj online! Trwa wejście w formacie "aaabb"do [3,2]. Przekroczono limit czasu najdłuższego przypadku testowego.

Wyjaśnienie

Nic szczególnego tutaj, licząc tylko unikalne permutacje, w których wszystkie grupy sąsiednich elementów mają długość 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.

Rubin, 84 76 bajtów

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}

Rekurencyjna funkcja lambda. Patrzy na każdy możliwy kolor i dozuje rekurencyjne wyszukiwanie drzewa, licząc ile razy używa wszystkich pasków.

Objaśnienie (dla starej wersji):

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 bajtów

Y@Xu!dAs

Format wejściowy to [1 1 1 1 2 2 2] za [4 3], itd.

Skończy się pamięć dla ostatniego przypadku testowego.

Wypróbuj online!

Wyjaśnienie

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