Введение

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

Требования к программе

Ваша программа должна иметь пять целых чисел (переданных в функцию или введенных через stdin (или как-то еще)). Первые четыре - это количество картин, предоставленных каждым из четырех художников. Последнее значение - это индекс перестановки i(считая от 1, а не от 0). Куратор желает увидеть iперестановку по лексикографическому порядку картин.

Ваша программа должна выводить эту перестановку в любом приемлемом формате: например, abbccdили [0 1 1 2 2 3]. Время выполнения для ввода менее десяти картин должно занимать менее часа (надеюсь, это не должно быть проблемой).

Вам не разрешается использовать любые встроенные функции для выработки перестановок

Примеры

Вход: 0 1 2 0 2

Учитывая, что у нас есть одна картина художника B и две картины художника C (и все они выглядят одинаково), перестановки в лексикографическом порядке:

['bcc', ' cbc ', 'ccb']

Выделенная перестановка будет правильным выводом, поскольку она является второй в лексикографическом порядке.

Вход: 1 2 0 1 5

['abbd', 'abdb', 'adbb', 'babd', ' badb ', 'bbad', 'bbda', 'bdab', 'bdba', 'dabb', 'dbab', 'dbba']

тестирование

Вот некоторые тесты, которые должны быть правильными.

1 2 4 1 5    - ABBDCCCC
2 2 3 1 86   - ABBCACDC
4 1 2 0 24   - AACACBA
1 4 3 2 65   - ABBCBBDCDC

Небольшой фрагмент кода в Python3, который должен случайным образом генерировать входные и выходные данные, доступен здесь (недопустимо для ввода, здесь используется импорт перестановок Python):

from itertools import permutations
from random import randint
a,b,c,d,n = randint(1,2),randint(1,2),randint(1,3),randint(1,3),randint(1,15)
print(str(a) + " " + str(b) + " " + str(c) + " " + str(d) + " " + str(n) + " - " + str(sorted(set([''.join(p) for p in permutations(a * "a" + b * "b" + c * "c" + d * "d")]))[n-1]))

Табло

Optimizer - CJam       - 39  - Confirmed - Bruteforce
EDC65     - JavaScript - 120 - Confirmed - Bruteforce
Jakube    - Python2    - 175 - Confirmed - Algorithmic

Python 2: 175 163 символа

Это не серьезный гольф-ответ. С другим алгоритмом я достиг 138 байт. Просто хотел опубликовать это здесь, потому что он не использует грубую силу. Сложность Тета (#pictures).

f=lambda x:0**x or x*f(x-1)
def g(Q,n):
 while sum(Q):
  for j in 0,1,2,3:
   p=f(sum(Q)-1)*Q[j]
   for k in Q:p/=f(k)
   if p<n:n-=p
   else:print j;Q[j]-=1;break

Применение:

g([1, 4, 3, 2], 65)

редактировать:

Тот же алгоритм, только немного игры в гольф: не импортируйте метод факториала и небольшие изменения в порядке вычислений.

Перевод Pyth: 61 символов

Lu*GhHUb1WsPQV4J*@QNytsPQFZPQ=J/JyZ)I<JeQ XQ4-eQJ)EN XQNt@QNB

Ничего особенного, точный перевод моего кода на Python. Слишком долго, хотя. Я тоже использовал несколько уродливых (длинных) вещей. Только первые 9 букв - это определение факториала.

Lu*GhHUb1    def y(b): G=1; for H in range(b): G*= H+1; return G

Также такие вещи Q[j]-=1слишком длинны: XQNt@QN(на 1 символ больше, чем в Python !!!)

Применение:

Попробуйте это здесь: Pyth Compiler / Executor . Отключить режим отладки и использовать в [2, 2, 3, 1, 86]качестве ввода.

CJam, 50 43 39 байт

q~(])\{W):Wa*}%s:X{Xm*:s_&}X,(*{$X=},$=

Это может быть много в гольфе.

Принимает ввод из STDIN в следующем формате:

4 1 2 0 24

Выводит картину. Например, для ввода выше:

0020210

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

Обратите внимание, что онлайн-компилятор отказывается от больших размеров рисования. Вам придется попробовать более крупные входные данные в версии Java

JavaScript (ES6) 120 138 147

Как функция с необходимыми пятью параметрами, вывод через консоль.
Использование символов 0,1,2,3. Я вычисляю общее количество символов, затем строю и проверяю каждое основание 4, имеющее требуемое количество цифр. Числа с неправильным номером любой цифры отбрасываются.
Примечание: с 32-битным целым числом JavaScript это работает до 15 картин.

Изменить короче (избегать .toString) и намного быстрее (изменено условие выхода). Время для каждого теста ниже 1 сек.

Edit2 без изменения алгоритма, больше в гольфе (для удобства чтения добавлены отступы)

F=(w,x,y,z,n)=>{
  for(a=0;n;n-=l=='0,0,0,0')
    for(l=[w,x,y,z],t=w+x+y+z,v='',b=a++;t--;b/=4)--l[d=b&3],v=d+v;
  console.log(v)
}

Ungolfed И не требуется FireFox

F=function(w,x,y,z,n) {
  for(a=0; n; a++) // exit when solution found (if wrong parameters, run forever)
  {
    l=[w,x,y,z]; // required number of each symbol
    t=w+x+y+z; // total of digits
    v=''; // init output string
    for(b=a;
      t--; // digit count down
      b >>= 2) // shift for next digit
    {
        d = b & 3; //get digit
        --l[d]; // decrement for the current digit
        v = d + v; // add to output string         
    }
    l[0]|l[1]|l[2]|l[3] // if digits ok
    ||--n // decrement counter
  }
  console.log(v) // when found, exit for and print the answer
}

Тест в консоли FireBug / FireFox

F(1, 2, 4, 1, 5) 
F(2, 2, 3, 1, 86)
F(4, 1, 2, 0, 24)
F(1, 4, 3, 2, 65)

Вывод

01132222
01120232
0020210
0112113232

Пиф , 20

@fqPQm/TdU4^U4sPQteQ

Попробуй это здесь.

Ввод в форме списка Python, например, [1, 2, 4, 1, 5]

Вывод также в форме списка Python, например, [0, 1, 1, 3, 2, 2, 2, 2]для ввода выше.

Решение - грубая сила, и на моем компьютере это занимает около 10 секунд, в худшем случае.

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

@fqPQm/TdU4^U4sPQteQ
           ^U4sPQ         All permutations of [0, 1, 2, 3] with length equal to the number
                          of paintings.
     m/TdU4               Find the count (/) of paintings by painter in the input list.
 fqPQ                     Filter the permutations on the counts being the desired counts
                          in the input.
                          This gives all possible orderings of the paintings.
@                teQ      Index into this list at the given location - 1. (0-indexing)