Заказать 40 палочек

15

У нас 40 палочек одинаковой ширины, но разной высоты. Сколько можно расположить аранжировок рядом друг с другом, чтобы, когда мы смотрим справа, мы видели 10 палочек, а когда мы смотрим слева, мы снова видели ровно 10 палочек?

Например, такой порядок:Пример заказа

Черные палочки спрятаны, красные палочки - это те, которые вы можете видеть, когда смотрите слева, синие палочки - те, которые вы можете видеть, когда смотрите справа, и пурпурная (т.е. самая длинная) - та, которую можно увидеть, если смотреть. с обеих сторон.

Как тестовые случаи:

  • Если бы у нас было 3 палки, количество заказов, чтобы увидеть 2 слева и 2 справа, равно 2
  • Если у нас было 5 стиков, количество заказов, чтобы увидеть 3 слева и 3 справа, равно 6
  • Если бы у нас было 10 стиков, количество заказов, чтобы увидеть 4 слева и 4 справа, составляет 90720
code-golf combinatorics permutations дружище
источник
13
Возможно, вы захотите избежать вопросов с фиксированным выводом, потому что оптимальный код-гольф-ответ, скорее всего, просто напечатает результат, не вычисляя его. Я бы порекомендовал сделать так, чтобы в вопросе было несколько переменных входных данных, например, N палочек, так что вы видите K из них слева / справа, где N и K - входные целые числа
Sp3000
4
Если вы измените спецификацию так, чтобы программы принимали входные данные (я не понимаю, почему нет - у вас уже есть тестовые случаи), вы можете подумать о том, хотите ли вы установить ограничение по времени для программ.
Sp3000
1
«Необходимо использовать вашу опубликованную программу для расчета случая 40/10» должно быть достаточно хороший срок.
feersum
1
Я не могу смириться с тем, что 10!/40 = 90720... это совпадение?
Тим
1
@Tim Какое значение 90720? Почтовый индекс для Лос-Аламитос, Калифорния ?
Цифровая травма

Ответы:

8

PARI / GP, 80

f(n,v)=abs(sum(k=1,n-1,binomial(n-1,k)*stirling(k,v-1,1)*stirling(n-k-1,v-1,1)))

Количество видимых палочек также называют числами небоскребов после игры карандашом / сеткой. Этот код основан на (только слегка измененной) формуле из OEIS A218531 . Я не знаю много PARI, но я действительно не думаю, что есть много для игры в гольф здесь.

Все тестовые примеры показаны на ideone.com . Результат для f(40,10):

192999500979320621703647808413866514749680
Geobits
источник
1
Есть хорошая причина для формулы. Число перестановок с vвидимыми слева палочками - число Стирлинга s(n,v). Если самый высокий стержень находится в положении k, то видимые слева - это этот стержень, а видимые слева - в подперестановке слева от k-1значений слева от положения k. Таким образом, чтобы иметь vвидимые слева палочки и видимые vсправа палочки, у вас есть s(k,v-1)выбор переставить левую половину, s(n-k-1,v-1)переставить правую половину, и binomial(n-1,k)варианты разделить палочки на две половины.
xnor
@xnor Они приводят в основном это объяснение в связанном PDF, но ваше мнение написано намного лучше IMO.
Geobits
Вы можете сэкономить 11 байт: f(n,v,s=stirling)=abs(sum(k=1,n--,binomial(n,k)*s(k,v-1)*s(n-k,v-1))). Это сохраняет sterlingпеременную для повторного использования, исключает ее последний аргумент, поскольку 1 является значением по умолчанию, и вычитает 1 из n один раз, а не три раза.
Чарльз
1

Python 3, 259 байт

Не очень доволен этим.

import itertools as i
x=input().split()
y,k=x
y=int(y)
c=0
x=list(i.permutations(list(range(1,y+1))))
for s in x:
 t=d=0;l=s[::-1]
 for i in range(y):
  if max(s[:i+1])==s[i]:t+=1
 for i in range(y):
  if max(l[:i+1])==l[i]:d+=1
 if t==d==int(k):c+=1
print(c)

Пример ввода и вывода:

10 4
90720

Он генерирует все возможные комбинации предоставленного диапазона, а затем просматривает их, проверяя каждое число в них, чтобы увидеть, равно ли оно максимуму предыдущих чисел. Затем он делает то же самое в обратном направлении, и если счет вперед (t) = счет назад (d) = заданный номер представления (k), то он действителен. Это добавляет это к счетчику (c) и печатает это в конце.

Тим
источник
0

R, 104

function(N,K)sum(sapply(combinat::permn(N),function(x)(z=function(i)sum(cummax(i)==i)==K)(x)&z(rev(x))))

Немного де-гольф:

    function(N,K) {
      all_perm <- combinat::permn(N)
      can_see_K_from_left <- function(i)sum(cummax(i) == i) == K
      can_see_K_from_both <- function(x)can_see_K_from_left(x) &
                                        can_see_K_from_left(rev(x))
      return(sum(sapply(all_perm, can_see_K_from_both)))
    }
flodel
источник
0

Pyth - 38 36 байт

В основном порт ответа R. Довольно медленно, даже не могу завершить 10, 4онлайн.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

Единственное, чего нет у Pyth, - это cummax и ==избыточные векторы, но для их реализации потребовалось всего несколько байтов.

Объяснение и дальнейшая игра в гольф в ближайшее время.

Попробуйте здесь онлайн .

Maltysen
источник