Przegrupowanie Nierówności

10

tło

Przegrupowanie Nierówność jest nierówność, która opiera się na przestawienie cyfr. Jeśli mam dwie listy liczb o tej samej długości, x 0 , x 1 , x 2 ... x n-1 i y 0 , y 1 , y 2 ... y n-1 o tej samej długości, gdzie I mogę zmienić kolejność liczb na liście, sposobem na maksymalizację sumy x 0 y 0 + x 1 y 1 + x 2 y 2 + ... + x n-1 y n-1 jest posortowanie 2 list w nie malejące zamówienie.

Przeczytaj artykuł w Wikipedii tutaj.

Zadanie

Napisałbyś program, który pobiera dane wejściowe ze STDIN lub funkcję, która akceptuje 2 tablice (lub powiązane kontenery) liczb (o tej samej długości).

Zakładając, że napiszesz funkcję, która akceptuje 2 tablice (a i b), znajdziesz liczbę sposobów na zmianę kolejności liczb w drugiej tablicy (b), aby zmaksymalizować:

a[0]*b[0]+a[1]*b[1]+a[2]*b[2]+...+a[n-1]*b[n-1]

W takim przypadku, jeśli tablica b wynosi [1 0 , 2 1 , 2 2 , 3 3 , 3 4 ] (wskaźniki dla przejrzystości),

[1 0 , 2 1 , 2 2 , 3 3 , 3 4 ],

[1 0 , 2 1 , 2 2 , 3 4 , 3 3 ], (zamień dwie 3)

[1 0 , 2 2 , 2 1 , 3 3 , 3 4 ] (zamień dwie 2)

[1 0 , 2 2 , 2 1 , 3 4 , 3 3 ] (zamień dwie 3 i zamień dwie 2)

są uważane za różne ustalenia. Oryginalna tablica sama w sobie również liczy się jako możliwa rearanżacja, jeśli również maksymalizuje sumę.

W przypadku danych wejściowych STDIN można założyć, że długość tablic jest podana przed tablicami (proszę podać, aby z nich korzystać), lub że tablice są podane w różnych wierszach (proszę również podać).

Oto 4 możliwe dane wejściowe (dla wygody):

5 1 1 2 2 2 1 2 2 3 3 (length before arrays)

1 1 2 2 2 1 2 2 3 3 (the 2 arrays, concatenated)

1 1 2 2 2
1 2 2 3 3 (the 2 arrays on different lines)

5
1 1 2 2 2
1 2 2 3 3 (length before arrays and the 2 arrays on different lines)

W przypadku danych wyjściowych możesz zwrócić odpowiedź (jeśli napiszesz funkcję) lub wydrukować odpowiedź do STDOUT. Możesz wybrać wyjście mod 10 9 +7 (od 0 do 10 9 +6), jeśli jest to wygodniejsze.

Przypadki testowe (i wyjaśnienia):

[1 1 2 2 2] [1 2 2 3 3] => 24

Pierwsze 2 wpisy muszą mieć wartość 1 i 2. Ostatnie 3 wpisy to 2, 3 i 3. Istnieją 2 sposoby rozmieszczenia tych 2 między pierwszymi 2 wpisami a ostatnimi 2 wpisami. Wśród pierwszych 2 wpisów są 2 sposoby ich zmiany. Wśród 2 ostatnich wpisów istnieje 6 sposobów na ich zmianę.

[1 2 3 4 5] [6 7 8 9 10] => 1

Jest tylko jeden sposób, czyli ustawienie podane w tablicach.

[1 1 ... 1 1] [1 1 ... 1 1] (10000 numbers) => 10000! or 531950728

Każda możliwa permutacja drugiej tablicy jest poprawna.

Test Dennisa: Pastebin => 583159312 (mod 1000000007)

Punktacja:

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź.

W przypadku remisu remisy zostaną zerwane przez czas złożenia, co sprzyja wcześniejszemu zgłoszeniu.

Uwaga:

Pojemniki mogą być nieposortowane.

Liczby całkowite w pojemnikach mogą być zerowe lub ujemne.

Program musi działać wystarczająco szybko (najwyżej godzinę) dla tablic o skromnych rozmiarach (około 10000 długości).

Inspirowane tym pytaniem na temat wymiany stosów matematycznych.

code-golf math combinatorics permutations Element118
źródło
2
Podaj przypadek testowy zawierający 10000 elementów na tablicę, abyśmy mogli sprawdzić, czy nasz kod działa poprawnie i jest wystarczająco szybki.
Dennis
1
W podanym przykładzie do zamiany drugiej tablicy [1_0, 2_2, 2_1, 3_4, 3_3] (zamień dwie 2 i zamień dwie 3) brakuje
Willem
czy akceptujesz dane wejściowe, takie jak [. . .]odpowiedź plz
Abr001am
Jeśli podamy funkcję, czy musimy wziąć dwa oddzielne argumenty, czy też możemy wziąć tablicę tablic?
Dennis
Cóż, tablica tablic wydaje się w porządku i nie wpływa zbytnio na wyzwanie. Popracuję nad przypadkiem testowym.
Element118,

Odpowiedzi:

4

CJam, 30 26 bajtów

q~](/:$_za+{e`0f=:m!:*}//*

Wypróbuj online w interpretatorze CJam .

Uzupełnia ten przypadek testowy krócej niż sekundę:

$ time cjam <(echo 'q~](/:$_za+{e`0f=:m!:*}%)\:*\/N') < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

real    0m0.308s
user    0m0.667s
sys     0m0.044s

Uruchomienie go w tłumaczu online powinno zająć mniej niż 10 sekund.

Algorytm

Wynik nie zależy od kolejności A , więc możemy założyć, że jest on posortowany. Oznacza to, że B należy również posortować, aby uzyskać maksymalny iloczyn punktowy.

Teraz, jeżeli r 1 ,… r n są długością serii posortowanego A , to ∏r k ! różne przegrupowania elementów A, które wciąż powodują rosnącą kolejność.

Podobnie, jeśli s 1 ,… s n są długością serii posortowanego B , to są ∏s k ! różne przegrupowania elementów B które wciąż powodują rosnącą kolejność.

Zlicza to jednak wszystkie pary wiele razy. Jeśli weźmiemy pary odpowiednich elementów posortowanego A i posortowanego B i zdefiniujemy t 1 ,… t n jako długość serii wynikowej tablicy, ∏t k ! jest wyżej wymienionym mnożnikiem.

Zatem pożądanym wynikiem jest (∏r k !) × (∏s k !) ÷ (∏t k !) .

Kod

 q~                          Read and evaluate all input.
   ]                         Wrap the resulting integers in an array.
    (                        Shift out the first (length).
     /                       Split the remainder into chunks of that length.
      :$                     Sort each chunk.
        _z                   Push a copy and transpose rows with columns.
                             This pushes the array of corresponding pairs.
          a+                 Wrap in array and concatenate (append).
            {          }/    For A, B, and zip(A,B):
             e`                Perform run-length encoding.
               0f=             Select the runs.
                  :m!          Apply factorial to each.
                     :*        Reduce by multiplication.
                         /   Divide the second result by the third.
                          *  Multiply the quotient with the first result.
Dennis
źródło
6

Pyth, 29 28 bajtów

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

Wypróbuj online w kompilatorze Pyth .

Algorytm

Wynik nie zależy od kolejności A , więc możemy założyć, że jest on posortowany. Oznacza to, że B należy również posortować, aby uzyskać maksymalny iloczyn punktowy.

Teraz, jeżeli r 1 ,… r n są długością serii posortowanego A , to ∏r k ! różne przegrupowania elementów A, które wciąż powodują rosnącą kolejność.

Podobnie, jeśli s 1 ,… s n są długością serii posortowanego B , to są ∏s k ! różne przegrupowania elementów B, które wciąż powodują rosnącą kolejność.

Zlicza to jednak wszystkie pary wiele razy. Jeśli weźmiemy pary odpowiednich elementów posortowanego A i posortowanego B i zdefiniujemy t 1 ,… t n jako długość serii wynikowej tablicy, ∏t k ! jest wyżej wymienionym mnożnikiem.

Zatem pożądanym wynikiem jest (∏r k !) × (∏s k !) ÷ (∏t k !) .

Kod

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

M                             Define g(G,H):
                      SGSH      Sort G and H.
                     ,          For the pair of the results.
                   CB           Bifurcated zip (C).
                                This returns [[SG, SH], zip([SG, SH])].
                 aF             Reduce by appending.
                                This returns [SG, SH, zip([SG, SH])].
      m                         Map; for each d in the resulting array:
              rd8                 Perform run-length encoding on d.
            hM                    Mapped "head". This returns the lengths.
         .!M                      Mapped factorial.
       *F                         Reduce by multiplication.
     J                          Save the result in J.
    P                           Discard the last element.
  *F                            Reduce by multiplication.
 /                  
                          eJ    Divide the product by the last element of J.
                                Return the result of the division.

Weryfikacja

Pseudolosowo wygenerowałem 100 przypadków testowych o długości 6, które rozwiązałem za pomocą powyższego kodu i tego podejścia opartego na brutalnej sile:

Ml.Ms*VGZ.pH

M             Define g(G,H) (or n(G,H) on second use):
         .pH    Compute all permutations of H.
  .M            Filter .pH on the maximal value of the following;
                 for each Z in .pH:
     *VGZ         Compute the vectorized product of G and Z.
    s             Add the products.
                  This computes the dot product of G and Z.
 l              Return the length of the resulting array.

Oto wyniki:

$ cat test.in
6,9,4,6,8,4,5,6,5,0,8,2
0,7,7,6,1,6,1,7,3,3,8,0
3,6,0,0,6,3,8,2,8,3,1,1
2,3,0,4,0,6,3,4,5,8,2,4
9,1,1,2,2,8,8,1,7,4,9,8
8,3,1,1,9,0,2,8,3,4,9,5
2,0,0,7,7,8,9,2,0,6,7,7
0,7,4,2,2,8,6,5,0,5,4,9
2,7,7,5,5,6,8,8,0,5,6,3
1,7,2,7,7,9,9,2,9,2,9,8
7,2,8,9,9,0,7,4,6,2,5,3
0,1,9,2,9,2,9,5,7,4,5,6
8,4,2,8,8,8,9,2,5,4,6,7
5,2,8,1,9,7,4,4,3,3,0,0
9,3,6,2,5,5,2,4,6,8,9,3
4,2,0,6,2,3,5,3,6,3,1,4
4,8,5,2,5,0,5,1,2,5,9,5
6,8,4,4,9,5,9,5,4,2,8,7
8,9,8,1,2,2,9,0,5,6,4,9
4,7,6,8,0,3,7,7,3,9,8,6
7,5,5,6,3,9,3,8,8,4,8,0
3,8,1,8,5,6,6,7,2,8,5,3
0,9,8,0,8,3,0,3,5,9,5,6
4,2,7,7,5,8,4,2,6,4,9,4
3,5,0,8,2,5,8,7,3,4,5,5
7,7,7,0,8,0,9,8,1,4,8,6
3,9,7,7,4,9,2,5,9,7,9,4
4,5,5,5,0,7,3,4,0,1,8,2
7,4,4,2,5,1,7,4,7,1,9,1
0,6,2,5,4,5,1,8,0,8,9,9
3,8,5,3,2,1,1,2,2,2,8,4
6,1,9,1,8,7,5,6,9,2,8,8
6,2,6,6,6,0,2,7,8,6,8,2
0,7,1,4,5,5,3,4,4,0,0,2
6,0,1,5,5,4,8,5,5,2,1,6
2,6,3,0,7,4,3,6,0,5,4,9
1,4,8,0,5,1,3,2,9,2,6,5
2,7,9,9,5,0,1,5,6,8,4,6
4,0,1,3,4,3,6,9,1,2,7,1
6,5,4,7,8,8,6,2,3,4,1,2
0,3,6,3,4,0,1,4,5,5,5,7
5,4,7,0,1,3,3,0,2,1,0,8
8,6,6,1,6,6,2,2,8,3,2,2
7,1,3,9,7,4,6,6,3,1,5,8
4,8,3,3,9,1,3,4,1,3,0,6
1,4,0,7,4,9,8,4,2,1,0,3
0,4,1,6,4,4,4,7,5,1,4,2
0,0,4,4,9,6,7,2,7,7,5,4
9,0,5,5,0,8,8,9,5,9,5,5
5,7,0,4,2,7,6,1,1,1,9,1
3,1,7,5,0,3,1,4,0,9,0,3
4,4,5,7,9,5,0,3,7,4,7,5
7,9,7,3,0,8,4,0,0,3,1,0
2,4,4,3,1,2,5,2,9,0,8,5
4,8,7,3,0,0,9,3,7,3,0,6
8,9,1,0,7,7,6,0,3,1,8,9
8,3,1,7,3,3,6,1,1,7,6,5
6,5,6,3,3,0,0,5,5,0,6,7
2,4,3,9,7,6,7,6,5,6,2,0
4,8,5,1,8,4,4,3,4,5,2,5
7,5,0,4,6,9,5,0,5,7,5,5
4,8,9,5,5,2,3,1,9,7,7,4
1,5,3,0,3,7,3,8,5,5,3,3
7,7,2,6,1,6,6,1,3,5,4,9
9,7,6,0,1,4,0,4,4,1,4,0
3,5,1,4,4,0,7,1,8,9,9,1
1,9,8,7,4,9,5,2,2,1,2,9
8,1,2,2,7,7,6,8,2,3,9,7
3,5,2,1,3,5,2,2,4,7,0,7
9,6,8,8,3,5,2,9,8,7,4,7
8,8,4,5,5,1,5,6,5,1,3,3
2,6,3,5,0,5,0,3,4,4,0,5
2,2,7,6,3,7,1,4,0,3,8,3
4,8,4,2,6,8,5,6,2,5,0,1
7,2,4,3,8,4,4,6,5,3,9,4
4,6,1,0,6,0,2,6,7,4,9,5
6,3,3,4,6,1,0,8,6,1,7,5
8,3,4,2,8,3,0,1,8,9,1,5
9,6,1,9,1,1,8,8,8,9,1,4
3,6,1,6,1,4,5,1,0,1,9,1
6,4,3,9,3,0,5,0,5,3,2,4
5,2,4,6,1,2,6,0,1,8,4,0
3,5,7,6,3,6,4,5,2,8,1,5
6,3,6,8,4,2,7,1,5,3,0,6
9,1,5,9,9,1,1,4,5,7,3,0
1,6,7,3,5,8,6,5,5,2,6,0
2,8,8,6,5,5,2,3,8,1,9,8
0,4,5,3,7,6,2,5,4,3,2,5
5,1,2,3,0,3,4,9,4,9,4,9
5,8,2,2,0,2,4,1,1,7,0,3
0,6,0,0,3,6,3,6,2,2,2,9
2,4,8,1,9,4,0,8,8,0,4,7
3,9,1,0,5,6,8,8,2,5,2,6
5,3,8,9,1,6,5,9,7,7,6,1
8,6,9,6,1,1,6,7,7,3,2,2
7,2,1,9,8,8,5,3,6,3,3,6
9,9,4,8,7,9,8,6,6,0,3,1
8,3,0,9,1,7,4,8,0,1,6,2
8,2,6,2,4,0,2,8,9,6,3,7
1,0,8,5,3,2,3,7,1,7,8,2
$ while read; do
> pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJMl.Ms*VGZ.pHAc2Q,gGHnGH' <<< "$REPLY"
> done < test.in
[4, 4]
[4, 4]
[8, 8]
[4, 4]
[8, 8]
[2, 2]
[4, 4]
[4, 4]
[4, 4]
[36, 36]
[2, 2]
[8, 8]
[24, 24]
[8, 8]
[2, 2]
[2, 2]
[6, 6]
[2, 2]
[8, 8]
[2, 2]
[12, 12]
[2, 2]
[8, 8]
[12, 12]
[4, 4]
[12, 12]
[4, 4]
[6, 6]
[8, 8]
[8, 8]
[6, 6]
[4, 4]
[48, 48]
[8, 8]
[4, 4]
[1, 1]
[4, 4]
[4, 4]
[8, 8]
[4, 4]
[12, 12]
[2, 2]
[96, 96]
[2, 2]
[4, 4]
[2, 2]
[6, 6]
[24, 24]
[24, 24]
[48, 48]
[4, 4]
[8, 8]
[12, 12]
[8, 8]
[4, 4]
[2, 2]
[24, 24]
[16, 16]
[2, 2]
[8, 8]
[24, 24]
[4, 4]
[24, 24]
[4, 4]
[12, 12]
[8, 8]
[12, 12]
[4, 4]
[8, 8]
[4, 4]
[16, 16]
[4, 4]
[8, 8]
[8, 8]
[4, 4]
[4, 4]
[4, 4]
[4, 4]
[72, 72]
[24, 24]
[4, 4]
[4, 4]
[4, 4]
[2, 2]
[12, 12]
[4, 4]
[8, 8]
[4, 4]
[36, 36]
[6, 6]
[12, 12]
[8, 8]
[4, 4]
[2, 2]
[8, 8]
[24, 24]
[6, 6]
[1, 1]
[2, 2]
[2, 2]

Aby sprawdzić, czy przesłany dokument spełnia wymagania dotyczące prędkości, uruchomiłem go w tym przypadku testowym .

$ time pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJAc2QgGH' < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

real    0m0.233s
user    0m0.215s
sys     0m0.019s
Dennis
źródło
2

Matlab, 230 bajtów

Edycja: Naprawiono wiele rzeczy pasujących do przypadków testowych dennisa, a nnz jest zastępowany przez numel z powodu wartości zero.

f=1;t=-1;q=1;a=sort(input(''));b=sort(input(''));for i=unique(a)c=b(find(a==i));r=numel(c(c==t));f=f*factorial(numel(c))*sum(arrayfun(@(u)nchoosek(max(q,r),u),0:min(q,r)));z=c(end);y=numel(c(c==z));q=(t==z)*(q+r)+(t~=z)*y;t=z;end,f

Wykonanie

[2 2 1 2 1]
[3 2 3 2 1]

f =

    24

Testowa Dennisa:

   A = importdata('f:\a.csv'); for i=1:100,a=sort(A(i,1:6));b=sort(A(i,7:12));
   f=1;t=-1;q=1;for i=unique(a)c=b(find(a==i));r=numel(c(c==t));f=f*factorial(numel(c))*sum(arrayfun(@(u)nchoosek(max(q,r),u),0:min(q,r)));z=c(end);y=numel(c(c==z));q=(t==z)*(q+r)+(t~=z)*y;t=z;end;
   disp(f);end

Wyjścia:

 4

 4

 8

 4

 8

 2

 4

 4

 4

36

 2

 8

24

 8

 2

 2

 6

 2

 8

 2

12

 2

 8

12

 4

12

 4

 6

 8

 8

 6

 4

48

 8

 4

 1

 4

 4

 8

 4

12

 2

96

 2

 4

 2

 6

24

24

48

 4

 8

12

 8

 4

 2

24

16

 2

 8

24

 4

24

 4

12

 8

12

 4

 8

 4

16

 4

 8

 8

 4

 4

 4

 4

72

24

 4

 4

 4

 2

12

 4

 8

 4

36

 6

12

 8

 4

 2

 8

24

 6

 1

 2

 2
Abr001am
źródło
Cóż, to rozwiązuje problem, więc wkład nie powinien mieć większego znaczenia.
Element118
1

C ++, 503 bajty

(tylko dla zabawy, język nie golfowy)

#import<iostream>
#import<algorithm>
#define U 12345
#define l long long
using namespace std;int N,X=1,Y=1,Z=1,x[U],y[U],i=1;l p=1,M=1000000007,f[U];l e(l x,int y){return y?y%2?(x*e(x,y-1))%M:e((x*x)%M,y/2):1;}main(){for(f[0]=1;i<U;i++)f[i]=(f[i-1]*i)%M;cin>>N;for(i=0;i<N;i++)cin>>x[i];for(i=0;i<N;i++)cin>>y[i];sort(x,x+N);sort(y,y+N);for(i=1;i<N;i++)x[i]^x[i-1]?p=p*f[X]%M,X=1:X++,y[i]^y[i-1]?p=p*f[Y]%M,Y=1:Y++,x[i]^x[i-1]|y[i]^y[i-1]?p=p*e(f[Z],M-2)%M,Z=1:Z++;cout<<p*f[X]%M*f[Y]%M*e(f[Z],M-2)%M;}

Wersja bez golfa:

#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int N; // number of integers
int x[1000010]; // the 2 arrays of integers
int y[1000010];
long long product = 1;
long long factorial[1000010]; // storing factorials mod 1000000007
long long factorialInv[1000010]; // storing the inverse mod 1000000007
long long pow(long long x, int y) {
    if (y == 0) return 1;
    if (y == 1) return x;
    if (y%2 == 1) return (x*pow(x, y-1))%MOD;
    return pow((x*x)%MOD, y/2);
}
int main(void) {
    //freopen("in.txt", "r", stdin); // used for faster testing
    //precomputation
    factorial[0] = factorial[1] = 1;
    for (int i=2;i<=1000000;i++) {
        factorial[i] = (factorial[i-1]*i)%MOD;
        factorialInv[i] = pow(factorial[i], MOD-2);
    }
    // input
    scanf("%d", &N);
    for (int i=0;i<N;i++) {
        scanf("%d", &x[i]);
    }
    for (int i=0;i<N;i++) {
        scanf("%d", &y[i]);
    }
    // sort the 2 arrays
    sort(x, x+N);
    sort(y, y+N);
    int sameX = 1;
    int sameY = 1;
    int sameXY = 1;
    for (int i=1;i<N;i++) {
        if (x[i]==x[i-1]) {
            sameX++;
        } else {
            product *= factorial[sameX];
            product %= MOD;
            sameX = 1;
        }
        if (y[i]==y[i-1]) {
            sameY++;
        } else {
            product *= factorial[sameY];
            product %= MOD;
            sameY = 1;
        }
        if (x[i]==x[i-1] && y[i]==y[i-1]) {
            sameXY++;
        } else {
            product *= factorialInv[sameXY];
            product %= MOD;
            sameXY = 1;
        }
    }
    product *= factorial[sameX];
    product %= MOD;
    product *= factorial[sameY];
    product %= MOD;
    product *= factorialInv[sameXY];
    product %= MOD;
    printf("%lld\n", product);
    return 0;
}
Element118
źródło