Допустим, ваша задача - рисовать столбы, а клиент просит вас нарисовать столб с четырьмя красными и тремя желтыми. Вы можете сделать это довольно легко следующим образом:

r y r y r y r

Только с желтыми и красными полосами. Теперь предположим, что ваш клиент просит вас нарисовать столб с 2 красными секциями, 2 желтыми секциями и 1 зеленой секцией . Есть несколько способов нарисовать свой столб

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

Точнее вот 12 способов покрасить шест. Это взрывает больше цветов и разделов, которые участвуют

Теперь, если ваш клиент говорит, что он хочет 3 красных раздела и 1 желтый, нет никакого способа нарисовать такой столб. Потому что независимо от того, как вы пытаетесь расположить секции, две красные секции соприкасаются, а когда две красные секции соприкасаются, они становятся одной красной секцией.

И это в значительной степени наше единственное правило для рисования столбов

Соседние секции не могут быть одного цвета

задача

Учитывая список требуемых цветов и разделов, выведите количество возможных способов покраски полюса в соответствии с запросом. Вы можете представлять цвета любым разумным способом (целые числа, символы, строки), но вам никогда не будет предоставлено более 255 различных цветов одновременно. Если вы хотите, вы можете даже не назначать цвета именам и просто взять список подсчетов разделов, если это проще.

Тестовые случаи

Их довольно сложно вычислить вручную, особенно когда они становятся больше. Если у кого-то есть предложенный тестовый пример, я добавлю его.

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

Математика, 37 44 48 60 62 байтов

Взять входные данные как список целых чисел {1, 1, 1, 2, 2}. Попробуйте это на Wolfram Sandbox .

Метод сопоставления с образцом, спасибо @ Не дерево!

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

Splitразбивает один список на подсписки последовательных элементов, например, {1, 1, 2, 3, 4, 4}в{{1, 1}, {2}, {3}, {4, 4}}

{{_}..}есть, а именно {{_}, {_}, {_}, ...}. Шаблон соответствует списку унарных подсписков.

Differences метод, 48 байтов:

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

Код использует, Differencesчтобы определить, являются ли смежные элементы одинаковыми.

Шаг за шагом:

1. Permutations@# генерирует все перестановки входного списка в список N! * N.
2. Differences/@ вычисляет разницу между N элементами и выдает список N! * (N-1).
3. 1##&@@@рассчитывает умножение всех списков. Если список содержит 0(два смежных элемента одинаковы), результатом будет 0, в противном случае ненулевое, значение N! список.
4. Clip[]действует как Sign[], преобразовать список из (-inf, inf) в [-1, 1]
5. Tr@Absпревращает все -1в 1и теперь список длины N! содержит только 0(недействительно) и 1(допустимо). Итак, мы просто суммируем список.

Желе , 7 байт

Œ!QIẠ€S

Попробуйте онлайн!

Принимает входные данные, например, [1,1,1,1,2,2,2]для [4,3]. [8,3,2]TestCase занимает слишком много времени , чтобы работать на TIO.

Как это работает

Œ!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 байтов

œÙ€¥PĀO

Попробуйте онлайн!

-1 спасибо nmjcman101 за другой ответ.

Mathematica, 50 байтов

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

Попробуйте в Mathics или в песочнице Wolfram !

Вводит данные, как в тестовых случаях - например, {4,3}означает «4 красные полосы, 3 желтые полосы».

Это наивная реализация формулы, которую я нашел здесь . «Наивный» означает «Я понятия не имею, как работает математика, поэтому, пожалуйста, не спрашивайте меня об объяснениях…»

Python 3.5 , 65 байт

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

Попробуйте онлайн!

Ruby 2.4, 47 байт

Входной список символов: Для теста [4,3], вход может быть %w[a a a a b b b], "1111222".charsили какой -либо другой метод массива форматирования , что это действительно в Ruby.

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

Требуется 2.4 для Enumerator#uniq(более ранние версии были доступны только в Arrayклассе). Таким образом, ссылка TIO добавляет 5 байтов, чтобы сначала преобразовать перечислитель перестановки в массив to_a, поскольку он не имеет вышеуказанной функции.

Попробуйте онлайн!

R, 72 байта

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

Создает функцию

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

Принимает участие в форме [1,1,1,1,2,2,2]согласно комментарию Эрика Outgolfer. Использование combinat«ы permnфункции , чтобы создать список всех перестановок, а затем , uniqueчтобы получить все отдельные записи. sapplyзатем применяет следующую функцию ко всем записям:

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

Который оценивает

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

Обратите внимание, что это xне то же самое, что xво входе большой функции. Использование другого символа в этой функции было бы глупо pryr::fверить, что большой функции нужен другой аргумент.

В любом случае, когда данная перестановку, эта функция принимает разницу между вектором: 2 1 3 4 2 1 -> -1 2 1 -2 -1. !преобразует ненулевые в FALSEи нули в TRUE, поэтому вектор становится FALSE FALSE FALSE FALSE FALSE. Подводя итог, чтобы проверить, есть ли TRUEs ( TRUEбудет означать diff=0-> два одинаковых последовательных числа). Мы можем снова инвертировать это, !чтобы получить логическое значение того, есть ли последовательные значения в перестановке или нет.

Суммирование по этим логическим значениям дает нам общее количество перестановок, где это не так.

Не работает для [8,3,2]тестового набора, потому что для хранения этих перестановок требуется вектор 46 ГБ.

Желе , 11 байт

Œ!Q⁻2\Ạ$ÐfL

Попробуйте онлайн!

Python 2 , 140 89 байт

Формат ввода 'aaaabbb'для тестового примера [4,3].

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

Попробуйте онлайн!

Шелуха , 8 байт

#ȯ¬ṁtguP

Попробуйте онлайн! Принимает ввод в формате "aaabb"для [3,2]. Тайм-аут на самом длинном тестовом случае.

объяснение

Ничего особенного, только подсчитав уникальные перестановки, где все группы смежных элементов имеют длину 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.

Рубин, 84 76 байт

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}

Рекурсивная лямбда-функция. Просматривает каждый возможный цвет и дозирует рекурсивный поиск по дереву, считая количество раз, когда оно использует все полосы.

Пояснение (для старой версии):

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 байт

Y@Xu!dAs

Формат ввода [1 1 1 1 2 2 2]для [4 3]и т. Д.

Недостаточно памяти для последнего контрольного примера.

Попробуйте онлайн!

объяснение

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