馆长困境

Question

Introduction

你是一位美术馆馆长的朋友，他最近从四位艺术家那里获得了现代艺术的乐趣(其中有些可能给馆长零件艺术品，年轻的恶棍)。因为这是现代艺术，任何艺术家的作品看起来都是一样的。你的朋友想用一台电脑来帮助你决定把这些零件放哪一条。

程序需求

您的程序必须接受五个整数(传递给一个函数或通过stdin (或其他方式)输入)。前四位是每一位艺术家提供的绘画数量。最后一个值是置换索引i (从1开始计算，而不是0)。馆长希望通过词库顺序看到i第四次排列。

您的程序必须以任何合理的格式输出这个置换:例如abbccd或[0 1 1 2 2 3]。输入总数少于10幅画的运行时必须花费不到一个小时(希望这是没有问题的)。

不允许使用任何内置函数来计算排列

。

示例

输入:0 1 2 0 2

鉴于我们有一幅由艺术家B和两幅由艺术家C绘制的画(它们看起来都是一样的)，字典顺序排列如下：

‘bcc’，‘cbc’，‘建行’

突出显示的排列将是正确的输出，因为它是字典顺序的第二位。

投入:1 2 0 1 5

“‘abbd”，“abdb”，“adbb”，“babd”，badb“，”bbad“，”bbda“，”bdab“，”bdba“，”dabb“，”dbab“，”dbba“

测试

以下是一些应该是正确的测试。

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

Python3中应该随机生成输入和输出的一小部分代码在这里可用(不适用于输入，这使用了置换的Python3)：

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

Answer 1

皮斯，20

@fqPQm/TdU4^U4sPQteQ

在这里试试。

输入采用Python形式，例如[1, 2, 4, 1, 5]

输出也是Python形式，例如上面输入的[0, 1, 1, 3, 2, 2, 2, 2]。

解决方案是蛮力，在我的机器上大约需要10秒，最坏的情况。

它的工作原理：

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