Nehmen wir an, Sie müssen Stangen malen, und ein Kunde bittet Sie, eine Stange mit 4 roten und 3 gelben Abschnitten zu malen. Das geht ganz einfach wie folgt:

r y r y r y r

Mit nur gelben und roten Streifen. Angenommen, Ihr Kunde fordert Sie auf, einen Pfahl mit 2 roten, 2 gelben und 1 grünen Abschnitten zu malen . Es gibt verschiedene Möglichkeiten, wie Sie Ihre Stange bemalen können

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

Genauer gesagt, das sind 12 Möglichkeiten, den Mast zu bemalen. Dadurch werden mehr Farben und Bereiche in die Luft gesprengt

Wenn Ihr Kunde nun sagt, er möchte 3 rote und 1 gelbe Abschnitte, gibt es keine Möglichkeit, einen solchen Pfahl zu malen. Denn unabhängig davon, wie Sie die Abschnitte anordnen, berühren sich zwei rote Abschnitte, und wenn sich zwei rote Abschnitte berühren, werden sie zu einem einzigen roten Abschnitt.

Und das ist so ziemlich unsere einzige Regel für das Malen von Stangen

Benachbarte Abschnitte haben möglicherweise nicht dieselbe Farbe

Aufgabe

Ausgehend von einer Liste der erforderlichen Farben und Abschnitte geben Sie die Anzahl der möglichen Möglichkeiten zum Malen eines Pfostens nach Bedarf aus. Sie können Farben auf jede vernünftige Weise darstellen (Ganzzahlen, Zeichen, Zeichenfolgen), aber Sie werden niemals mehr als 255 verschiedene Farben gleichzeitig erhalten. Wenn Sie möchten, können Sie auch festlegen, dass die Farben nicht mit Namen versehen werden, und nur eine Liste der Abschnittszählungen erstellen, wenn dies einfacher ist.

Testfälle

Diese sind von Hand eher schwer zu berechnen, zumal sie größer werden. Wenn jemand einen vorgeschlagenen Testfall hat, füge ich ihn hinzu.

[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

Nehmen Sie die Eingabe als eine Liste von ganzen Zahlen {1, 1, 1, 2, 2}. Probieren Sie es auf Wolfram Sandbox .

Pattern-Matching-Methode, danke @Not a tree!

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

SplitTeilt eine einzelne Liste in Unterlisten aufeinanderfolgender Elemente auf, z. B. {1, 1, 2, 3, 4, 4}in{{1, 1}, {2}, {3}, {4, 4}}

{{_}..}ist nämlich {{_}, {_}, {_}, ...}. Das Muster entspricht einer Liste unärer Unterlisten.

Differences Methode, 48 Bytes:

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

Der Code Differencesbestimmt, ob benachbarte Elemente identisch sind.

Schritt für Schritt:

1. Permutations@# Erzeugt alle Permutationen der Eingabeliste in eine N! * N-Liste.
2. Differences/@ berechnet die Differenz zwischen N Elementen und liefert eine N! * (N-1) Liste.
3. 1##&@@@berechnet die Multiplikation aller Listen. Wenn eine Liste enthält 0(zwei benachbarte Elemente sind gleich), ist das Ergebnis 0, ansonsten ungleich Null, ein N! Liste.
4. Clip[]verhält sich wie Sign[], transformiere die Liste von (-inf, inf) nach [-1, 1]
5. Tr@Absverwandelt sich alles -1in1 und jetzt enthält die N! -Länge nur 0(ungültig) und 1(gültig). Also fassen wir einfach die Liste zusammen.

Gelee , 7 Bytes

Œ!QIẠ€S

Probieren Sie es online!

Nimmt Eingaben wie zB [1,1,1,1,2,2,2]für [4,3]. Der [8,3,2]Testfall dauert zu lange, um mit TIO ausgeführt zu werden.

Wie es funktioniert

Œ!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

Probieren Sie es online!

-1 Danke an nmjcman101 für eine andere Antwort.

Mathematica, 50 Bytes

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

Probieren Sie es in Mathematik oder in der Wolfram Sandbox aus !

Nimmt Eingaben wie in den Testfällen vor - z {4,3} bedeutet "4 rote Streifen, 3 gelbe Streifen".

Dies ist eine naive Implementierung einer Formel, die ich hier gefunden habe . "Naiv" bedeutet "Ich habe keine Ahnung, wie die Mathematik funktioniert, bitte frag mich nicht nach einer Erklärung ..."

Python 3.5 , 65 Bytes

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

Probieren Sie es online!

Ruby 2.4, 47 Bytes

Die Eingabe ist eine Liste von Zeichen: für den Testfall [4,3], kann eingegeben werden %w[a a a a b b b], "1111222".charsoder eine andere Array Formatierungsmethode , die in Ruby gültig ist.

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

Benötigt 2.4 für Enumerator#uniq(frühere Versionen hatten es nur für die ArrayKlasse verfügbar ). Als solches fügt die TIO-Verbindung 5 Bytes hinzu, um den Permutations-Enumerator zuerst über in ein Array zu konvertieren to_a, da sie die obige Funktion nicht hat.

Probieren Sie es online!

R, 72 Bytes

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

Erzeugt die Funktion

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

Nimmt Eingaben in das Formular [1,1,1,1,2,2,2]gemäß dem Kommentar von Erik the Outgolfer vor. Verwendet combinatdie permnFunktion von 's , um eine Liste aller Permutationen zu erstellen und dann uniquealle eindeutigen Einträge abzurufen. sapplywendet dann auf alle Einträge die folgende Funktion an:

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

Welches bewertet zu

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

Beachten Sie, dass dies xnicht mit dem xEingang der großen Funktion identisch ist . Die Verwendung eines anderen Zeichens in dieser Funktion würde täuschenpryr::f dass die große Funktion ein anderes Argument benötigt.

Wie auch immer, wenn eine Permutation gegeben, nimmt diese Funktion die Differenz zwischen dem Vektor: 2 1 3 4 2 1 -> -1 2 1 -2 -1. !konvertiert Nicht- FALSENullen in und Nullen in TRUE, so dass der Vektor wird FALSE FALSE FALSE FALSE FALSE. Summiere das, um zu prüfen, ob es irgendwelche TRUEs gibt ( TRUEwürde bedeuten diff=0-> zwei gleiche fortlaufende Zahlen). Wir können dies erneut invertieren !, um einen Booleschen Wert zu erhalten, der angibt, ob die Permutation aufeinanderfolgende Werte enthält oder nicht.

Durch Summieren über diese Booleschen Werte erhalten wir die Gesamtzahl der Permutationen, bei denen dies nicht der Fall ist.

Funktioniert nicht für den [8,3,2]Testfall, da zum Speichern dieser Permutationen ein Vektor von 46 GB erforderlich ist.

Jelly , 11 Bytes

Œ!Q⁻2\Ạ$ÐfL

Probieren Sie es online!

Python 2 , 140 89 Bytes

Das Eingabeformat ist 'aaaabbb'für den Testfall [4,3].

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

Probieren Sie es online!

Schale , 8 Bytes

#ȯ¬ṁtguP

Probieren Sie es online! Übernimmt Eingaben im Format "aaabb"für [3,2]. Zeitüberschreitung beim längsten Testfall.

Erläuterung

Hier gibt es nichts Besonderes, nur die eindeutigen Permutationen zu zählen, bei denen alle Gruppen benachbarter Elemente die Länge 1 haben.

#ȯ¬ṁ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}

Eine rekursive Lambda-Funktion. Untersucht jede mögliche Farbe und führt eine rekursive Baumsuche durch, wobei die Häufigkeit gezählt wird, mit der alle Streifen verwendet werden.

Erklärung (für alte Version):

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

Eingabeformat ist [1 1 1 1 2 2 2] für [4 3]usw.

Läuft nicht mehr genügend Speicher für den letzten Testfall.

Probieren Sie es online!

Erläuterung

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