2
$\begingroup$

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$.

I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the function $f(i) > 0.5$ where:

$f(i)$ is the probability that a number chosen randomly from row $i$ will be greater than a number chosen randomly from row $P[i]$. ($i$'s corresponding row according to permutation.)

For an example, let $n=3$,$m=3$,$P=[3, 1, 2]$ and $M=$

2 6 7
3 4 8 
1 5 9

According to the given permutation, you will have to compare the number chosen from 1st row with 3rd row and similarly.

In the given matrix number are arranged in such a way that $f(1) = f(2) = f(3) = 5/9$. Observe that there are 5 pairs in the Cartesian product $\{2,6,7\}\times\{1,5,9\}$ which the first element is larger than the second.

My question is how to construct such a matrix provided $n,m,P$ as input?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Here are some ideas for you to start thinking.

First of all, the problem isn't always solvable. For example, if $P$ contains a fixed point or a cycle of length 2, there is no solution (why?).

More generally, For each $m,k$, either there is a $k \ldots m$ solution for a cycle of length $k$, or there isn't. Let $L_m$ be the set of $k$ such that a solution exists (so $1,2 \not\in L_m$ for all $m$, and $3 \in L_3$). Then for given $m,P$, there is a solution iff the sizes of all cycles in $P$ lie in $L_m$ (why?).

It remains to determine $L_m$. Let us know if you get stuck doing that. You can start with small $m$ such as $1,2,3$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ thanks a lot for your kind help....yes,for a cycle of length 1 or 2, it is not possible to satisfy the constraint for obvious reason..but what actually you mean by $L_{m}$? is it the set of cycle size for which solution exists? If so, then also how can I generate the matrix M efficiently? $\endgroup$
    – user3724568
    Jul 9, 2014 at 3:09
  • $\begingroup$ @user3724568 $L_m$ is the set of all $k$ such that a solution exists for $k = n$ and $P = 2\;3\;\cdots\;k\;1$. I suspect that you would be able to come up with a simple criterion for whether $k \in L_m$, a criterion that will come with an explicit construction. One you know how to solve single cycles, you should be able to solve the general case. $\endgroup$
    – Yuval Filmus
    Jul 9, 2014 at 3:38
  • $\begingroup$ So,is it like $L_{1}$ and $L_{2}$ are empty,then $L_{3}$=3,$L_{4}$=4,$L_{5}$=5.$L_{6}$={3,6},$L_{7}$={3,4,7} and so on...but what's next? $\endgroup$
    – user3724568
    Jul 9, 2014 at 3:58
  • $\begingroup$ @user3724568 I have no idea. Perhaps a pattern will emerge. $\endgroup$
    – Yuval Filmus
    Jul 9, 2014 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.