Rearrangement Inequality

Background

The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same length, where I am allowed to rearrange the numbers in the list, a way to maximize the sum x0y0+x1y1+x2y2+...+xn-1yn-1 is to sort the 2 lists in non-decreasing order.

You would write a program that takes input from STDIN or a function that accepts 2 arrays (or related containers) of numbers (which are of the same length).

Assuming you write a function which accepts 2 arrays (a and b), you are going to find the number of ways you can rearrange the numbers in the second array (b) to maximize:

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


In this case, if the array b is [10, 21, 22, 33, 34] (indices for clarity),

[10, 21, 22, 33, 34],

[10, 21, 22, 34, 33], (swap the two 3's)

[10, 22, 21, 33, 34] (swap the two 2's)

[10, 22, 21, 34, 33] (swap the two 3's and swap the two 2's)

are considered different arrangements. The original array, itself, also counts as a possible rearrangement if it also maximizes the sum.

For STDIN input, you may assume that the length of the arrays is provided before the arrays (please state so that you use it), or that the arrays are provided on different lines (also please state).

Here are the 4 possible inputs (for convenience):

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)


For output, you are allowed to return the answer (if you write a function) or print the answer to STDOUT. You may choose to output the answer mod 109+7 (from 0 to 109+6) if it is more convenient.

Test Cases (and explanation):

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


The first 2 entries have to be 1 and 2. The last 3 entries are 2, 3 and 3. There are 2 ways to arrange the 2's between the first 2 entries and the last 2 entries. Among the first 2 entries, there are 2 ways to rearrange them. Among the last 2 entries, there are 6 ways to rearrange them.

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


There is only 1 way, which is the arrangement given in the arrays.

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


Every possible permutation of the second array is valid.

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

Scoring:

This is code-golf, so shortest answer wins.

In case of tie, ties will be broken by time of submission, favouring the earlier submission.

Take note:

The containers may be unsorted.

The integers in the containers may be zero or negative.

The program has to run fast enough (at most an hour) for modestly sized arrays (around 10000 in length).

Inspired by this question on Mathematics Stack Exchange.

• Please provide a test case with 10000 elements per array, so we can verify our code works correctly and is fast enough. Commented Nov 21, 2015 at 13:25
• In the example you give for swaping the second array [1_0, 2_2, 2_1, 3_4, 3_3] (swap the two 2's and swap the two 3's) is missing Commented Nov 21, 2015 at 14:07
• do you accept inputs like [. . .] plz respond Commented Nov 21, 2015 at 15:27
• If we submit a function, do we have to take two separate arguments or could we take an array of arrays? Commented Nov 21, 2015 at 17:52
• Well, array of arrays seems fine, and does not affect the challenge too much. I'll work on the test case. Commented Nov 22, 2015 at 0:31

Pyth, 29 28 bytes

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ


Try it online in the Pyth Compiler.

Algorithm

The result does not depend on the order of A, so we can assume it to be sorted. This means that B must also be sorted to attain the maximal dot product.

Now, if r1, … rn are the length of the runs of the sorted A, there are ∏rk! different rearrangements of the elements of A that still result in ascending order.

Likewise, if s1, … sn are the length of the runs of the sorted B, there are ∏sk! different rearrangements of the elements of B that still result in ascending order.

However, this counts all pairings multiple times. If we take the pairs of of the corresponding elements of sorted A and sorted B and define t1, … tn as the length of the runs of the resulting array, ∏tk! is the aforementioned multiplier.

Thus, the desired result is (∏rk!) × (∏sk!) ÷ (∏tk!).

Code

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.
*F                            Reduce by multiplication.
/
eJ    Divide the product by the last element of J.
Return the result of the division.


Verification

I've pseudo-randomly generated 100 test cases of length 6, which I've solved with the above code and this brute-force approach:

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.
This computes the dot product of G and Z.
l              Return the length of the resulting array.


These were the results:

$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]  To verify my submission satisfies the speed requirement, I've ran it with this test case. $ time pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJAc2QgGH' < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

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


CJam, 30 26 bytes

q~](/:$_za+{e0f=:m!:*}//*  Try it online in the CJam interpreter. It completes this test case in less than a second: $ time cjam <(echo 'q~](/:$_za+{e0f=:m!:*}%)\:*\/N') < test-large.in | md5sum 5801bbf8ed0f4e43284f7ec2206fd3ff - real 0m0.308s user 0m0.667s sys 0m0.044s  Running it in the online interpreter should take less than 10 seconds. Algorithm The result does not depend on the order of A, so we can assume it to be sorted. This means that B must also be sorted to attain the maximal dot product. Now, if r1, … rn are the length of the runs of the sorted A, there are ∏rk! different rearrangements of the elements of A that still result in ascending order. Likewise, if s1, … sn are the length of the runs of the sorted B, there are ∏sk! different rearrangements of the elements of B that still result in ascending order. However, this counts all pairings multiple times. If we take the pairs of of the corresponding elements of sorted A and sorted B and define t1, … tn as the length of the runs of the resulting array, ∏tk! is the aforementioned multiplier. Thus, the desired result is (∏rk!) × (∏sk!) ÷ (∏tk!). Code  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.


Matlab, 230 bytes

Edit: Many things fixed to match dennis' test cases, and nnz is replaced by numel due to nil values.

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


Execution

[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


Outputs:

 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

• Well, it solves the problem, so input shouldn't matter too much. Commented Nov 22, 2015 at 1:06

C++, 503 bytes

(just for fun, a non-golfing language)

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


Ungolfed version:

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


Jelly, 14 bytes

Ṣ€ZṭµŒɠ!P)×:ƭ/


Try it online!

Implements Dennis' method. Ignoring time requirements leads to an 8 byte solution:

Œ!ḋÐṀ¥@L


Try it online!

which can be 6 bytes if we take input in reverse order:

Œ!ḋÐṀL


Try it online!

How they work

Ṣ€ZṭµŒɠ!P)×:ƭ/ - Main link. Takes a pair of lists [A, B]
Ṣ€             - Sort each
Z            - Transpose to get all pairs
ṭ           - Append that to [A, B], yielding [A, B, zip(A, B)]
µ          - Call that triple T and start a new link with T as the argument
)     - Over each element in T:
Œɠ        -   Lengths of runs
!       -   Factorial of each
P      -   Product
/ - Reduce the triple:
ƭ  -   Tie 2 dyads and cycle them:
×    -     Multiplication
:   -     Integer division
For the triple [r, s, t], this yields (r×s):t


The 8 byte solution works in the following way:

Œ!ḋÐṀ¥@L - Main link. Takes A on the left and B on the right
¥   - Group the previous 2 links into a dyad f(B, A):
Œ!       -   All permutations of B
ÐṀ    -   Keep those which yield a maximal value under:
ḋ      -     Dot product with A
@  - Run f(B, A)
L - Length


The ¥@` is simply to compensate for inputs being in the wrong order. Of course, the 8 and 6 byte versions have complexity proportional to $$\\text{length}(B)!\$$, which grows very fast.