Rearrangement Inequality

Question

Background

The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x₀, x₁, x₂...x_n-1 and y₀, y₁, y₂...y_n-1 of the same length, where I am allowed to rearrange the numbers in the list, a way to maximize the sum x₀y₀+x₁y₁+x₂y₂+...+x_n-1y_n-1 is to sort the 2 lists in non-decreasing order.

Read the Wikipedia article here.

Task

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 [1₀, 2₁, 2₂, 3₃, 3₄] (indices for clarity),

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

[1₀, 2₁, 2₂, 3₄, 3₃], (swap the two 3's)

[1₀, 2₂, 2₁, 3₃, 3₄] (swap the two 2's)

[1₀, 2₂, 2₁, 3₄, 3₃] (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 10⁹+7 (from 0 to 10⁹+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.

Answer 1

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 r₁, … r_n are the length of the runs of the sorted A, there are ∏r_k! different rearrangements of the elements of A that still result in ascending order.

Likewise, if s₁, … s_n are the length of the runs of the sorted B, there are ∏s_k! 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 t₁, … t_n as the length of the runs of the resulting array, ∏t_k! is the aforementioned multiplier.

Thus, the desired result is (∏r_k!) × (∏s_k!) ÷ (∏t_k!).

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.
    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.

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.
    s             Add the products.
                  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

Answer 2

CJam, 30 26 bytes

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

Try it online in the CJam interpreter.

It completes this test case in less than a second:

$ time cjam <(echo 'q~](/:$_za+{e`0f=: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 r₁, … r_n are the length of the runs of the sorted A, there are ∏r_k! different rearrangements of the elements of A that still result in ascending order.

Likewise, if s₁, … s_n are the length of the runs of the sorted B, there are ∏s_k! 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 t₁, … t_n as the length of the runs of the resulting array, ∏t_k! is the aforementioned multiplier.

Thus, the desired result is (∏r_k!) × (∏s_k!) ÷ (∏t_k!).

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.

Answer 3

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

Answer 4

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

Answer 5

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.