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 i
th 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
{:A.a.{~97+[:I.}:
is valid J and works, but usesA.
for most of the work, so it isn't valid. If you could write a function that replacesA.
and subsitute it in this function, you'd have a valid answer. \$\endgroup\${:A.[:I.}:
... The thing is that, but I still don't thinkA.
would be valid: jsoftware.com/help/dictionary/dacapdot.htm \$\endgroup\$