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


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


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


Optimizer - CJam       - 39  - Confirmed - Bruteforce
EDC65     - JavaScript - 120 - Confirmed - Bruteforce
Jakube    - Python2    - 175 - Confirmed - Algorithmic
  • 1
    \$\begingroup\$ You say, " all of the pieces look exactly the same". Do you mean "all the the pieces from a given artist look exactly the same, but pieces from different artists look different"? \$\endgroup\$
    – DavidC
    Jan 4, 2015 at 17:04
  • \$\begingroup\$ This wouldn't be a valid entry, but I think it might still be useful for someone: {:A.a.{~97+[:I.}: is valid J and works, but uses A. for most of the work, so it isn't valid. If you could write a function that replaces A. and subsitute it in this function, you'd have a valid answer. \$\endgroup\$ Jan 4, 2015 at 17:05
  • \$\begingroup\$ @ɐɔıʇǝɥʇuʎs - You don't have to use "ABCD", you can use any character/numerical/symbolic system at all. I'm afraid I don't know J, and so cannot tell the exact problem, but hope this helps =) \$\endgroup\$ Jan 4, 2015 at 17:07
  • \$\begingroup\$ @PopeyGilbert Well, a version that just spits out numbers would be {:A.[:I.}:... The thing is that, but I still don't think A. would be valid: jsoftware.com/help/dictionary/dacapdot.htm \$\endgroup\$ Jan 4, 2015 at 17:10
  • \$\begingroup\$ What if the required permutation does not exists? 1 0 0 0 100 ? \$\endgroup\$
    – edc65
    Jan 4, 2015 at 20:29

4 Answers 4


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


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

Pyth translation: 61 characters


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


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

  • \$\begingroup\$ It works! Congratulations on coming up with the first Python solution! However, I did find that in my environment I have to move from math import* outside the function. Adding you to the leaderboard! \$\endgroup\$ Jan 5, 2015 at 10:36
  • \$\begingroup\$ Wow... Your solution is incredibly efficient - For 32 paintings it takes only 0.034 seconds o.0. \$\endgroup\$ Jan 5, 2015 at 10:48

CJam, 50 43 39 bytes


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:


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

  • \$\begingroup\$ Congratulations on being the first solver! 50 bytes is certainly a hard value to beat. I'll add you as the top of the leaderboard! \$\endgroup\$ Jan 4, 2015 at 17:13
  • \$\begingroup\$ @PopeyGilbert you should at least wait for 1 week or so before accepting an answer \$\endgroup\$
    – Optimizer
    Jan 4, 2015 at 17:52
  • \$\begingroup\$ Ah, okay, I'm very sorry! In my previous challenge I just changed the accepted answer when someone got beaten. My bad. \$\endgroup\$ Jan 4, 2015 at 17:53
  • 1
    \$\begingroup\$ @PopeyGilbert That's very noble of you (and I wish all challenger authors did), and in principle there's nothing wrong with accepting early if you do, but some people seem to get offended if a challenge around here accepts an answer early (because, I guess, no one expects the author to change the accepted answer). \$\endgroup\$ Jan 4, 2015 at 17:59
  • \$\begingroup\$ I personally think that there should be at least 2 answers to choose between before accepting, even if its done early. Of course if there is only 1 answer till a week or so, accept it. \$\endgroup\$
    – Optimizer
    Jan 4, 2015 at 18:01

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)


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


  • \$\begingroup\$ Hello! Having a bit of trouble running it. I'm downloading FireFox to see if that will help. I'll add you to the leaderboard! \$\endgroup\$ Jan 4, 2015 at 21:13
  • \$\begingroup\$ I found rather a nice table here - I'll assume Firefox is necessary. Tested and it works! Changed leaderboard to confirmed. \$\endgroup\$ Jan 4, 2015 at 21:21
  • \$\begingroup\$ Leaderboard but no upvote ... you really don't like it! :( \$\endgroup\$
    – edc65
    Jan 4, 2015 at 21:28
  • \$\begingroup\$ Agh! I'm so sorry =( It's upvoted now =) \$\endgroup\$ Jan 4, 2015 at 21:30
  • \$\begingroup\$ I wonder how long this algorithm will be in CJam. But as of now, I have no idea how this works :P \$\endgroup\$
    – Optimizer
    Jan 4, 2015 at 21:54

Pyth, 20


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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.