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