Introdução

Você é amigo de um curador de um museu de arte, que teve o prazer recente de receber arte moderna de quatro artistas ( alguns dos quais podem dar ao curador zero peças de arte, jovens patifes ). Como se trata de arte moderna, todas as peças de qualquer artista parecem exatamente iguais. Seu amigo deseja usar um computador para ajudar a decidir em qual ordem colocar essas peças.

Requisitos do programa

Seu programa deve levar cinco números inteiros (passados ​​para uma função ou inseridos através do stdin (ou de outra maneira)). Os quatro primeiros são o número de pinturas fornecidas por cada um dos quatro artistas. O último valor é um índice de permutação i(contando de 1, não 0). O curador deseja ver a ipermutação por ordem lexicográfica das pinturas.

Seu programa deve gerar esta permutação em qualquer formato razoável: por exemplo, abbccdou [0 1 1 2 2 3]. O tempo de execução da entrada totalizando menos de dez pinturas deve levar menos de uma hora (esperamos que isso não seja problema).

Você não tem permissão para usar nenhuma função embutida para calcular permutações

Exemplos

Entrada: 0 1 2 0 2

Dado que temos uma pintura do artista B e duas do artista C (e todas parecem iguais), as permutações em ordem lexicográfica são:

['cco', ' cbc ', 'ccb']

A permutação destacada seria a saída correta, porque é a segunda em ordem lexicográfica.

Entrada: 1 2 0 1 5

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

Teste

Aqui estão alguns testes que devem estar corretos.

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

Um pequeno pedaço de código no Python3 que deve gerar entradas e saídas aleatoriamente está disponível aqui (não é válido para entrada, isso usa a importação de permutações do 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]))

Placar

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

Python 2: 175 163 caracteres

Esta não é uma resposta séria ao golfe. Com um algoritmo diferente, cheguei a 138 bytes. Só queria postar isso aqui, porque não usa força bruta. A complexidade é Theta (#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

Uso:

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

editar:

Mesmo algoritmo, apenas um pouco de golfe: não importe o método fatorial e faça pequenas alterações na ordem dos cálculos.

Tradução Pyth: 61 caracteres

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

Nada de especial aqui, tradução exata do meu código python. Muito tempo embora. Eu também tinha que usar algumas coisas feias (longas). A primeira letra de 9 por si só é a definição do fatorial.

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

Também coisas como Q[j]-=1é muito longa: XQNt@QN(1 caractere a mais que Python !!!)

Uso:

Experimente aqui: Pyth Compiler / Executor . Desative o modo de depuração e use [2, 2, 3, 1, 86]como entrada.

CJam, 50 43 39 bytes

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

Isso pode ser muito praticado.

Recebe entrada de STDIN no seguinte formato:

4 1 2 0 24

Mostra a pintura. Por exemplo, para a entrada acima:

0020210

Experimente online aqui

Observe que o compilador online desiste de tamanhos de pintura maiores. Você precisará tentar entradas maiores na versão Java

JavaScript (ES6) 120138 147

Como uma função com os cinco parâmetros necessários, faça a saída via console.
Usando símbolos 0,1,2,3. Calculo o total de símbolos e, em seguida, construo e verifico cada número base 4 com o número necessário de dígitos. Os números com o número errado de qualquer dígito são descartados.
Nota: com JavaScript inteiro de 32 bits, isso funciona para até 15 pinturas.

Edite Mais curto (evite .toString) e muito mais rápido (condição de saída modificada). Tempo para cada teste abaixo de 1 s.

Edit2 sem alteração de algoritmo, mais golfe (recuo adicionado para facilitar a leitura)

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 E nenhum Firefox necessário

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
}

Teste no console do 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)

Resultado

01132222
01120232
0020210
0112113232

Pyth , 20

@fqPQm/TdU4^U4sPQteQ

Experimente aqui.

A entrada está na forma de lista Python, por exemplo [1, 2, 4, 1, 5]

A saída também está no formato de lista Python, por exemplo [0, 1, 1, 3, 2, 2, 2, 2] para a entrada acima.

A solução é força bruta e leva cerca de 10 segundos, na pior das hipóteses, na minha máquina.

Como funciona:

@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)