Factoring a multiset into a product of two multisets Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that
$$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$
or prove that there are none?
For example, if I give you $S=\{6,8,15,15,20,20\}, m=2,n=3$, you will tell me $A=\{3,4\}$, $B=\{2,5,5\}$.
I used the vague word "numbers" to mean anything you like.  Choose "positive integers", "integers", "real numbers", "elements of my favourite quasigroup" as you please.  Personally I think "real numbers" grabs the essence of the problem, as the subtask of factoring integers is a distraction.  Assume you can do exact arithmetic in constant time per basic operation.
If you are working in a ring, the task looks the same as that of arranging the $mn$ numbers in an $m\times n$ matrix so that the rank is 1. 
If your numbers are "positive reals", then you can take logarithms to convert the multiplication into addition, in which case the question is a bit like this one.  But I don't care about finding all factorizations, just whether there is none or more than none.
I don't any more have an application for this.  I just thought it might disturb your sleep like it disturbed mine. 
 A: I assume the positive integers case and rely on existence of unique prime factorizations and linear order for them.
Let $P$ be the product of all elements of $S$.
Assuming we can find prime factorization of each element of $S$ (and thus $P$), here are some quick tests for the "None" answer:


*

*Test whether we can represent $P$ as the product of $m$-th and $n$-th powers. That is, the answer is "None" if for some prime $p\mid P$, we cannot represent $\nu_p(P)$ as a linear combination of $m$ and $n$ with nonnegative integer coefficients. 

*Let $k_p$ be the number of elements of $S$ divisible by $p$. For each prime $p\mid P$, the number $mn-k_p$ must be equal to $x\cdot y$, where $x$ and $y$ would be the number of elements not divisible by $p$ in $A$ and $B$, respectively. That is, $mn-k_p$ must be the product of two numbers below $n$ and $m$, respectively. If not, the answer is "None".
Now, let me describe a simple backtracking algorithm that tries to fill up an empty $m\times n$ table $M$ with the elements of $S$ to turn it into a multiplication table. We assume that the elements of $S$ are sorted in non-decreasing order.


*

*We place the first (smallest) element of $S$ to $M_{1,1}$.

*For each subsequent element $s$ of $S$, we will try to place it to empty cells that are adjacent to the occupied ones (e.g., we can place the second element of $S$ either to $M_{1,2}$ and $M_{2,1}$), subject to the following constraints.

*Placing an element $s$ to $M_{i,j}$ is allowed only if the following conditions hold:
(i) $s$ must divide
$$\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})\cdot \gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j});$$
 and 
(ii) if $\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}},s)<\gcd(M_{i,1},M_{i,2},\dots,M_{i,{j-1}})$, then we re-test as in (i) that each $M_{i,k}$ remains allowed at its position with $s$ placed at $M_{i,j}$; and 
(iii) similarly we check the inequality $\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j},s)<\gcd(M_{1,j},M_{2,j},\dots,M_{i-1,j})$ and that all these elements remain allowed at their positions.

*If conditions (i)-(iii) hold, we place $s$ to $M_{i,j}$ and iterate to step 2. If not, we go to the next potential placement for $s$. If all placements are exhausted, we return to the previous element and try to find it a new placement, etc. If this way we ever return to the first element of $S$, the answer is "None".
When the whole table is filled, we try to recover the elements of $A$ and $B$ from linear algebra on the prime exponents for each prime $p\mid P$ (perhaps, something can be done here even if we cannot factor $P$). Notice that $\gcd$'s of rows and columns give multiples of the corresponding elements of $A$ and $B$ (if they exist). If the product of $\gcd$ of $i$-th row and $\gcd$ of $j$-th column give $M_{i,j}$, then these $\gcd$'s are the elements of $A$ and $B$.
