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