Wprowadzenie

Jesteś przyjacielem kustosza muzeum sztuki, który ostatnio czerpał przyjemność z otrzymywania sztuki nowoczesnej od czterech artystów ( z których niektórzy mogą dać kustoszowi zero dzieł sztuki, młodych łotrów ). Ponieważ jest to sztuka współczesna, wszystkie dzieła danego artysty wyglądają dokładnie tak samo. Twój przyjaciel chce użyć komputera, aby zdecydować, w której kolejności umieścić te elementy.

Wymagania programowe

Twój program musi przyjąć pięć liczb całkowitych (przekazanych do funkcji lub wprowadzonych przez stdin (lub w jakiś inny sposób)). Pierwsze cztery to liczba obrazów dostarczonych przez każdego z czterech artystów. Ostatnia wartość to indeks permutacji i(liczony od 1, a nie 0). Kurator chce zobaczyć ipermutację według porządku leksykograficznego obrazów.

Twój program musi wyprowadzić tę permutację w dowolnym rozsądnym formacie: np . abbccdLub [0 1 1 2 2 3]. Środowisko wykonawcze dla danych wejściowych wynoszące mniej niż dziesięć obrazów musi zająć mniej niż godzinę (mam nadzieję, że nie powinno to stanowić problemu).

Nie wolno używać żadnych wbudowanych funkcji do obliczania permutacji

Przykłady

Wejście: 0 1 2 0 2

Biorąc pod uwagę, że mamy jeden obraz artysty B i dwa artysty C (i wszystkie wyglądają tak samo), permutacje w porządku leksykograficznym to:

[„bcc”, „ cbc ”, „ccb”]

Podświetlona permutacja byłaby prawidłowym wyjściem, ponieważ jest to druga w kolejności leksykograficznej.

Wejście: 1 2 0 1 5

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

Testowanie

Oto kilka testów, które powinny być poprawne.

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

Krótki fragment kodu w Python3, który powinien losowo generować dane wejściowe i wyjściowe, jest dostępny tutaj (niepoprawny dla wpisu, używa importu permutacji w Pythonie):

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

Tablica wyników

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

Python 2: 175 163 znaków

To nie jest poważna odpowiedź na golfa. Z innym algorytmem osiągnąłem 138 bajtów. Chciałem to tutaj opublikować, ponieważ nie używa brutalnej siły. Złożoność to Theta (# zdjęcia).

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

Stosowanie:

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

edytować:

Ten sam algorytm, tylko niektóre gry w golfa: nie importuj metody czynnikowej i drobnych zmian w kolejności obliczeń.

Tłumaczenie Pyth: 61 znaków

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

Nic specjalnego tutaj, dokładne tłumaczenie mojego kodu python. Jednak zdecydowanie za długo. Użyłem też kilku brzydkich (długich) rzeczy. Pierwsze 9 liter jest definicją silni.

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

Także rzeczy takie Q[j]-=1są o wiele za długie: XQNt@QN(1 znak więcej niż Python !!!)

Stosowanie:

Wypróbuj tutaj: Pyth Compiler / Executor . Wyłącz tryb debugowania i użyj [2, 2, 3, 1, 86]jako danych wejściowych.

CJam, 50 43 39 bajtów

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

Można w to dużo grać w golfa.

Pobiera dane wejściowe ze STDIN w następującym formacie:

4 1 2 0 24

Wysyła obraz. Na przykład dla powyższego wejścia:

0020210

Wypróbuj online tutaj

Pamiętaj, że internetowy kompilator rezygnuje z większych rozmiarów obrazów. Będziesz musiał wypróbować większe dane wejściowe w wersji Java

JavaScript (ES6) 120 138 147

Jako funkcja z wymaganymi pięcioma parametrami, wyjście przez konsolę.
Używanie symboli 0,1,2,3. Obliczam sumę symboli, a następnie buduję i sprawdzam każdą podstawową liczbę 4 mającą wymaganą liczbę cyfr. Liczby z niewłaściwą liczbą dowolnej cyfry są odrzucane.
Uwaga: w przypadku 32-bitowej liczby całkowitej JavaScript działa to maksymalnie dla 15 obrazów.

Edytuj Krótszy (unikaj .toString) i znacznie szybszy (zmodyfikowany warunek wyjścia). Czas na każdy test poniżej 1 sek.

Edycja2 bez zmiany algorytmu, więcej golfa (dodano wcięcie dla czytelności)

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

Niegolfowany I nie wymaga FireFox

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
}

Testuj w konsoli FireBug / FireFox

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

Wynik

01132222
01120232
0020210
0112113232

Pyth , 20 lat

@fqPQm/TdU4^U4sPQteQ

Wypróbuj tutaj.

Dane wejściowe są w formie listy Python, np [1, 2, 4, 1, 5]

Dane wyjściowe mają również postać listy w języku Python, np. [0, 1, 1, 3, 2, 2, 2, 2]Dla powyższych danych wejściowych.

Rozwiązaniem jest brutalna siła, co w najgorszym przypadku zajmuje około 10 sekund na moim komputerze.

Jak to działa:

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