Introducción

Usted es amigo de un curador de un museo de arte, que recientemente tuvo el placer de obtener arte moderno de cuatro artistas ( algunos de los cuales pueden darle al curador cero piezas de arte, jóvenes sinvergüenzas ). Como se trata de arte moderno, todas las piezas de cualquier artista se ven exactamente iguales. Tu amigo quiere usar una computadora para ayudar a decidir en qué orden colocar estas piezas.

Requerimientos del programa

Su programa debe tomar cinco enteros (pasados ​​a una función o ingresados ​​a través de stdin (o de otra manera)). Los primeros cuatro son el número de pinturas proporcionadas por cada uno de los cuatro artistas. El último valor es un índice de permutación i(contando desde 1, no desde 0). El curador desea ver la ipermutación por orden lexicográfico de las pinturas.

Su programa debe generar esta permutación en cualquier formato razonable: por ejemplo, abbccdo [0 1 1 2 2 3]. El tiempo de ejecución para la entrada por un total de menos de diez pinturas debe tomar menos de una hora (con suerte esto no debería ser un problema)

No está permitido usar ninguna función incorporada para resolver las permutaciones

Ejemplos

Entrada: 0 1 2 0 2

Dado que tenemos una pintura del artista B y dos del artista C (y todas se ven iguales), las permutaciones en orden lexicográfico son:

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

La permutación resaltada sería la salida correcta, porque es la segunda en orden lexicográfico.

Entrada: 1 2 0 1 5

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

Pruebas

Aquí hay algunas pruebas que deberían ser correctas.

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

Aquí está disponible un pequeño fragmento de código en Python3 que debería generar aleatoriamente entradas y salidas (no válido para la entrada, esto usa la importación de permutaciones de 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]))

Marcador

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

Python 2: 175 163 caracteres

Esta no es una respuesta de golf seria. Con un algoritmo diferente llegué a 138 bytes. Solo quería publicar esto aquí, porque no usa fuerza bruta. La complejidad es Theta (#imágenes).

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:

Mismo algoritmo, solo un poco de golf: no importe el método factorial y los pequeños cambios en el orden de los cálculos.

Traducción Pyth: 61 caracteres

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

Nada especial aquí, traducción exacta de mi código de Python. Demasiado tiempo sin embargo. También tuve que usar algunas cosas feas (largas). La primera letra 9 sola es la definición del factorial.

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

También cosas como Q[j]-=1son demasiado largas: XQNt@QN(¡1 carácter más que Python!)

Uso:

Pruébelo aquí: Pyth Compiler / Executor . Deshabilite el modo de depuración y úselo [2, 2, 3, 1, 86]como entrada.

CJam, 50 43 39 bytes

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

Esto se puede jugar mucho al golf.

Toma información de STDIN en el siguiente formato:

4 1 2 0 24

Salidas de la pintura. Por ejemplo para la entrada anterior:

0020210

Pruébalo en línea aquí

Tenga en cuenta que el compilador en línea renuncia a los tamaños de pintura más grandes. Tendrá que probar entradas más grandes en la versión Java

JavaScript (ES6) 120 138 147

Como una función con los cinco parámetros requeridos, salida a través de la consola.
Usando los símbolos 0,1,2,3. Calculo el total de símbolos, luego construyo y verifico cada número base 4 que tiene el número requerido de dígitos. Los números con el número incorrecto de cualquier dígito se descartan.
Nota: con un entero de 32 bits de JavaScript, esto funciona para hasta 15 pinturas.

Editar más corto (evitar .toString) y mucho más rápido (condición de salida modificada). Tiempo para cada prueba por debajo de 1 seg.

Edit2 sin cambio de algoritmo, más golf (sangría agregada para facilitar la lectura)

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 y no requiere 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
}

Prueba en la consola 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)

Salida

01132222
01120232
0020210
0112113232

Pyth , 20

@fqPQm/TdU4^U4sPQteQ

Pruébalo aquí.

La entrada está en forma de lista de Python, p. Ej. [1, 2, 4, 1, 5]

La salida también está en forma de lista de Python, por ejemplo, [0, 1, 1, 3, 2, 2, 2, 2]para la entrada anterior.

La solución es la fuerza bruta y toma alrededor de 10 segundos, en el peor de los casos, en mi máquina.

Cómo 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)