Einführung

Sie sind ein Freund eines Kurators eines Kunstmuseums, der in letzter Zeit die Freude hatte, moderne Kunst von vier Künstlern zu erhalten ( von denen einige dem Kurator möglicherweise keine Kunstwerke geben, junge Schurken ). Da es sich um moderne Kunst handelt, sehen alle Werke eines Künstlers genau gleich aus. Ihr Freund möchte einen Computer verwenden, um zu entscheiden, in welcher Reihenfolge diese Teile platziert werden sollen.

Programmanforderungen

Ihr Programm muss fünf Ganzzahlen annehmen (an eine Funktion übergeben oder über stdin (oder anderswo) eingegeben). Die ersten vier sind die Anzahl der von jedem der vier Künstler gelieferten Gemälde. Der letzte Wert ist ein Permutationsindex i(von 1 bis 0). Der Kurator möchte die ith Permutation nach lexikographischer Reihenfolge der Bilder sehen.

Ihr Programm muss diese Permutation in einem angemessenen Format ausgeben: z . B. abbccdoder [0 1 1 2 2 3]. Die Laufzeit für die Eingabe von insgesamt weniger als zehn Gemälden muss weniger als eine Stunde betragen (dies sollte hoffentlich kein Problem sein).

Sie dürfen keine eingebauten Funktionen verwenden, um Permutationen zu berechnen

Beispiele

Eingabe: 0 1 2 0 2

Da wir ein Gemälde von Künstler B und zwei von Künstler C haben (und alle gleich aussehen), lauten die Permutationen in lexikografischer Reihenfolge:

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

Die hervorgehobene Permutation wäre die richtige Ausgabe, da sie die zweite in lexikografischer Reihenfolge ist.

Eingabe: 1 2 0 1 5

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

Testen

Hier sind einige Tests, die korrekt sein sollten.

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

Hier ist ein kurzer Code in Python3 verfügbar, der zufällig Ein- und Ausgaben generieren soll (nicht für die Eingabe gültig, dies verwendet den Python-Import von Permutationen):

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

Anzeigetafel

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

Python 2: 175 163 Zeichen

Dies ist keine ernsthafte Golfantwort. Mit einem anderen Algorithmus erreichte ich 138 Byte. Ich wollte das nur hier posten, weil es keine rohe Gewalt anwendet. Komplexität ist Theta (#Bilder).

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

Verwendungszweck:

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

bearbeiten:

Gleicher Algorithmus, nur ein bisschen Golf: Importieren Sie nicht die Fakultätsmethode und kleine Änderungen in der Reihenfolge der Berechnungen.

Pyth-Übersetzung: 61 Zeichen

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

Nichts Besonderes hier, genaue Übersetzung meines Python-Codes. Viel zu lange. Ich hatte auch ein paar hässliche (lange) Dinge benutzt. Der erste 9 Buchstabe allein ist die Definition der Fakultät.

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

Auch Sachen wie Q[j]-=1ist viel zu lang: XQNt@QN(1 Zeichen mehr als Python !!!)

Verwendungszweck:

Probieren Sie es hier aus: Pyth Compiler / Executor . Deaktivieren Sie den Debug-Modus und verwenden Sie ihn [2, 2, 3, 1, 86]als Eingabe.

CJam, 50 43 39 Bytes

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

Dies kann viel Golf gespielt werden.

Übernimmt Eingaben von STDIN in folgendem Format:

4 1 2 0 24

Gibt das Bild aus. Zum Beispiel für die obige Eingabe:

0020210

Probieren Sie es hier online aus

Beachten Sie, dass der Online-Compiler für größere Gemälde aufgibt. Sie müssen größere Eingaben in der Java-Version versuchen

JavaScript (ES6) 120 138 147

Als Funktion mit den erforderlichen fünf Parametern über die Konsole ausgegeben.
Mit Symbolen 0,1,2,3. Ich berechne die Summe der Symbole, baue und überprüfe dann jede Basis-4-Zahl mit der erforderlichen Anzahl von Ziffern. Zahlen mit der falschen Nummer einer Ziffer werden verworfen.
Hinweis: Mit JavaScript 32-Bit-Ganzzahl funktioniert dies für bis zu 15 Bilder.

Bearbeiten Sie kürzer (vermeiden Sie .toString) und viel schneller (geänderte Beendigungsbedingung). Zeit für jeden Test unter 1 Sek.

Edit2 keine Änderung des Algorithmus, mehr Golf (Einrückung zur besseren Lesbarkeit hinzugefügt)

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 Und kein FireFox erforderlich

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 Konsole

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

Ausgabe

01132222
01120232
0020210
0112113232

Pyth , 20

@fqPQm/TdU4^U4sPQteQ

Probieren Sie es hier aus.

Die Eingabe erfolgt in Python-Listenform, z [1, 2, 4, 1, 5]

Die Ausgabe erfolgt auch in Python-Listenform, z. B. [0, 1, 1, 3, 2, 2, 2, 2]für die obige Eingabe.

Die Lösung ist Brute Force und dauert auf meinem Computer im schlimmsten Fall etwa 10 Sekunden.

Wie es funktioniert:

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