Curator's Dilemma

Question

Introduction

You are a friend of a curator for an art museum, who has had the recent delight of getting modern art from four artists (some of which may give the curator zero pieces of art, young scoundrels). As this is modern art, all of any given artist's pieces look exactly the same. Your friend wants to use a computer to help decide which order to place these pieces in.

Program Requirements

Your program must take five integers (passed to a function or inputted through stdin (or someway else)). The first four are the number of paintings supplied by each of the four artists. The last value is an permutation index i (counting from 1, not 0). The curator wishes to see the ith permutation by lexicographic order of the paintings.

Your program must output this permutation in any reasonable format: e.g. abbccd or [0 1 1 2 2 3]. The runtime for input totalling fewer than ten paintings must take less than an hour (this should hopefully be no problem).

You are not allowed to use any in-built functions to work out permutations

Examples

Input: 0 1 2 0 2

Given that we have one painting by artist B and two by artist C (and they all look the same), the permutations in lexicographic order are:

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

The highlighted permutation would be the correct output, because it is the second in lexicographic order.

Input: 1 2 0 1 5

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

Testing

Here are some tests that should be correct.

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

A short piece of code in Python3 that should randomly generate inputs and outputs is available here (not valid for entry, this uses the Python import of permutations):

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

Scoreboard

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

Answer 1

Python 2: 175 163 chars

This is not a serious golfing answer. With a different algorithm I reached 138 byte. Just wanted to post this here, because it doesn't use brute force. Complexity is 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

Usage:

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

edit:

Same algorithm, just some golfing: don't import the factorial method and little changes in the order of the calculations.

Pyth translation: 61 characters

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

Nothing special here, exact translation of my python code. Way too long though. I had too use a few ugly (long) things. The first 9 letter alone is the definition of the factorial.

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

Also stuff like Q[j]-=1 is way too long: XQNt@QN (1 character more than Python!!!)

Usage:

Try it here: Pyth Compiler/Executor. Disable debug mode and use [2, 2, 3, 1, 86] as input.

Answer 2

CJam, 50 43 39 bytes

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

This can be golfed a lot.

Takes input from STDIN in following format:

4 1 2 0 24

Outputs the painting. For example for above input:

0020210

Try it online here

Do note that the online compiler gives up for larger painting sizes. You will have to try larger inputs on the Java version

Answer 3

JavaScript (ES6) 120 138 147

As a function with the required five parameters, output via console.
Using symbols 0,1,2,3. I calc the total of symbols, then build and check every base 4 number having the required number of digits. Numbers with the wrong number of any digit are discarded.
Note: with JavaScript 32 bit integer this works for up to 15 paintings.

Edit Shorter (avoid .toString) and way faster (modified exit condition). Time for each test below 1 sec.

Edit2 no algorithm change, golfed more (indentation added for readability)

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 And no FireFox required

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
}

Test In FireBug/FireFox console

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

Output

01132222
01120232
0020210
0112113232

Answer 4

Pyth, 20

@fqPQm/TdU4^U4sPQteQ

Try it here.

Input is in Python list form, e.g. [1, 2, 4, 1, 5]

Output is also in Python list form, e.g. [0, 1, 1, 3, 2, 2, 2, 2] for the above input.

The solution is brute force, and takes about 10 seconds, worst case, on my machine.

How it works:

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