Antecedentes

La desigualdad de reordenamiento es una desigualdad que se basa en reorganizar números. Si tengo dos listas de números de la misma longitud, x ₀ , x ₁ , x ₂ ... x _n-1 e y ₀ , y ₁ , y ₂ ... y _n-1 de la misma longitud, donde yo se me permite reorganizar los números en la lista, una forma de maximizar la suma x ₀ y ₀ + x ₁ y ₁ + x ₂ y ₂ + ... + x _n-1 y _n-1 es ordenar las 2 listas en orden no decreciente.

Lea el artículo de Wikipedia aquí.

Tarea

Escribiría un programa que tome datos de STDIN o una función que acepte 2 matrices (o contenedores relacionados) de números (que son de la misma longitud).

Suponiendo que escribe una función que acepta 2 matrices (ayb), encontrará la cantidad de formas en que puede reorganizar los números en la segunda matriz (b) para maximizar:

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

En este caso, si la matriz b es [1 ₀ , 2 ₁ , 2 ₂ , 3 ₃ , 3 ₄ ] (índices de claridad),

[1 ₀ , 2 ₁ , 2 ₂ , 3 ₃ , 3 ₄ ],

[1 ₀ , 2 ₁ , 2 ₂ , 3 ₄ , 3 ₃ ], (intercambie los dos 3)

[1 ₀ , 2 ₂ , 2 ₁ , 3 ₃ , 3 ₄ ] (intercambie los dos 2)

[1 ₀ , 2 ₂ , 2 ₁ , 3 ₄ , 3 ₃ ] (intercambia los dos 3 y cambia los dos 2)

se consideran diferentes arreglos. La matriz original, en sí misma, también cuenta como una posible reorganización si también maximiza la suma.

Para la entrada STDIN, puede suponer que la longitud de las matrices se proporciona antes de las matrices (indique para que la use), o que las matrices se proporcionan en diferentes líneas (también indique).

Aquí están las 4 entradas posibles (por conveniencia):

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)

Para la salida, puede devolver la respuesta (si escribe una función) o imprimir la respuesta en STDOUT. Puede optar por enviar la respuesta mod 10 ⁹ +7 (de 0 a 10 ⁹ +6) si es más conveniente.

Casos de prueba (y explicación):

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

Las primeras 2 entradas deben ser 1 y 2. Las últimas 3 entradas son 2, 3 y 3. Hay 2 formas de organizar los 2 entre las primeras 2 entradas y las últimas 2 entradas. Entre las primeras 2 entradas, hay 2 formas de reorganizarlas. Entre las últimas 2 entradas, hay 6 formas de reorganizarlas.

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

Solo hay 1 forma, que es la disposición dada en las matrices.

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

Toda permutación posible de la segunda matriz es válida.

Dennis 'Testcase: Pastebin => 583159312 (mod 1000000007)

Puntuación:

Este es el código de golf, por lo que gana la respuesta más corta.

En caso de empate, los empates se romperán en el momento de la presentación, favoreciendo la presentación anterior.

Tomar nota:

Los contenedores pueden estar sin clasificar.

Los enteros en los contenedores pueden ser cero o negativos.

El programa tiene que ejecutarse lo suficientemente rápido (como máximo una hora) para matrices de tamaño modesto (alrededor de 10000 de longitud).

Inspirado por esta pregunta en Mathematics Stack Exchange.

code-golf math combinatorics permutations Element118
fuente

2

Proporcione un caso de prueba con 10000 elementos por matriz, para que podamos verificar que nuestro código funcione correctamente y sea lo suficientemente rápido.

Dennis

1

En el ejemplo que da para intercambiar la segunda matriz [1_0, 2_2, 2_1, 3_4, 3_3] (intercambie los dos 2 y los dos 3) falta

Willem

¿acepta entradas como por [. . .]

favor

Si presentamos una función, ¿tenemos que tomar dos argumentos separados o podríamos tomar una matriz de matrices?

Dennis

Bueno, la matriz de matrices parece estar bien y no afecta demasiado el desafío. Trabajaré en el caso de prueba.

Element118

4

CJam, 30 26 bytes

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

Pruébelo en línea en el intérprete de CJam .

Completa este caso de prueba en menos de un segundo:

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

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

Ejecutarlo en el intérprete en línea debería tomar menos de 10 segundos.

Algoritmo

El resultado no depende del orden de A , por lo que podemos suponer que está ordenado. Esto significa que B también debe clasificarse para obtener el producto punto máximo.

Ahora, si r ₁ , ... r _n son la longitud de las corridas de la A ordenada , ¡hay ∏r _k ! diferentes reordenamientos de los elementos de A que todavía resultan en orden ascendente.

Del mismo modo, si s ₁ , ... s _n son la longitud de las corridas de la B ordenada , ¡hay ∏s _k ! diferentes reordenamientos de los elementos de B que todavía resultan en orden ascendente.

Sin embargo, esto cuenta todas las parejas varias veces. Si tomamos los pares de los elementos correspondientes de ordenado A y ordenado B y definimos t ₁ , ... t _n como la longitud de las corridas de la matriz resultante, ∏t _k ! es el multiplicador mencionado anteriormente.

Por lo tanto, el resultado deseado es (∏r _k !) × (∏s _k !) ÷ (∏t _k !) .

Código

 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
fuente

6

Pyth, 29 28 bytes

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

Pruébelo en línea en el compilador Pyth .

Algoritmo

El resultado no depende del orden de A , por lo que podemos suponer que está ordenado. Esto significa que B también debe clasificarse para obtener el producto punto máximo.

Ahora, si r ₁ , ... r _n son la longitud de las corridas de la A ordenada , ¡hay ∏r _k ! diferentes reordenamientos de los elementos de A que todavía resultan en orden ascendente.

Del mismo modo, si s ₁ , ... s _n son la longitud de las corridas de la B ordenada , ¡hay ∏s _k ! diferentes reordenamientos de los elementos de B que todavía resultan en orden ascendente.

Sin embargo, esto cuenta todas las parejas varias veces. Si tomamos los pares de los elementos correspondientes de ordenado A y ordenado B y definimos t ₁ , ... t _n como la longitud de las corridas de la matriz resultante, ∏t _k ! es el multiplicador mencionado anteriormente.

Por lo tanto, el resultado deseado es (∏r _k !) × (∏s _k !) ÷ (∏t _k !) .

Código

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.

Verificación

He generado seudoaleatoriamente 100 casos de prueba de longitud 6, que he resuelto con el código anterior y este enfoque de fuerza bruta:

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.

Estos fueron los resultados:

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

Para verificar que mi envío satisfaga el requisito de velocidad, lo ejecuté con este caso de prueba .

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

real    0m0.233s
user    0m0.215s
sys     0m0.019s

Dennis
fuente

2

Matlab, 230 bytes

Editar: Se arreglaron muchas cosas para que coincidan con los casos de prueba de Dennis, y nnz se reemplaza por numeral debido a valores nulos.

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

Ejecución

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

f =

    24

Dennis 'Testcase:

   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

Salidas:

Abr001am
fuente

Bueno, resuelve el problema, por lo que la entrada no debería importar demasiado.

Element118

1

C ++, 503 bytes

(solo por diversión, un lenguaje que no es de golf)

#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;}

Versión sin golf:

#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
fuente

Desigualdad de reordenamiento

Antecedentes

Tarea

Casos de prueba (y explicación):

Puntuación:

Tomar nota:

Respuestas:

CJam, 30 26 bytes

Algoritmo

Código

Pyth, 29 28 bytes

Algoritmo

Código

Verificación

Matlab, 230 bytes

Ejecución

Dennis 'Testcase:

C ++, 503 bytes