5
$\begingroup$

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).

e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

To solve the problem, I have to find the row-wise sum of it's transpose.

i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

Can it be achieved in less than O(n*m)?

$\endgroup$
  • $\begingroup$ In other words, you are looking for an algorithm that conjugates a partition. $\endgroup$ – Yuval Filmus Jun 1 at 12:58
4
$\begingroup$

A non-increasing sequence of integers is known as a partition. The operation you are describing is known as conjugation. Given a partition $\lambda_1,\ldots,\lambda_n$, you can compute its conjugate $\lambda'_1,\ldots,\lambda'_m$ as follows:

  • Initialize a pointer $i$ at $n$.
  • Set $\lambda'_1 = i$.
  • Advance $i$ backwards until $\lambda_i \geq 2$.
  • Set $\lambda'_2 = i$.
  • Advance $i$ backwards until $\lambda_i \geq 3$.
  • Set $\lambda'_3 = i$.
  • ...
  • Stop once $i = 1$.

As an example, here is how you apply this algorithm on $4,3,2,2,1$. $$ \begin{align*} &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ &&&& \uparrow \\ &&&& 5 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ &&& \uparrow \\ &&& 4 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ \uparrow \\ 1 \end{array} \end{align*} $$ It might happen that at some point $i$ doesn't advance at all. This is what happens if we apply this algorithm on $5,4,2,1$: $$ \begin{align*} &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ &&& \uparrow \\ &&& 4 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ && \uparrow \\ && 3 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ \uparrow \\ 1 \end{array} \end{align*} $$

$\endgroup$
  • $\begingroup$ Why did you stop at 4 twice in the second example? $\endgroup$ – Vishal Sharma Jun 1 at 16:55
  • $\begingroup$ Oh.. it's because it satisfied the condition for 3 as well as 4 right? $\endgroup$ – Vishal Sharma Jun 1 at 16:57
  • 1
    $\begingroup$ Right, this is why I included this example. $\endgroup$ – Yuval Filmus Jun 1 at 17:17
3
$\begingroup$

The row-wise sum of the transpose is just the column-wise sum of the original matrix. So, for inputs $a_1 \cdots a_n$ and outputs $b_1 \cdots b_m$, it looks something like this: $$ \begin{array}{c|c&c&c&lcr} & b_1=4 & b_2=2 & b_3=1 \\ \hline a_1=3 & 1 & 1 & 1 \\ a_2=2 & 1 & 1 & 0 \\ a_3=1 & 1 & 0 & 0 \\ a_4=1 & 1 & 0 & 0 \end{array} $$

Each output is equal to the number of rows long enough to reach it. Therefore, a value $a_k$ affects the first $a_k$ outputs.


Algorithm description

First, initialize a vector of length $m$ called $b$, setting all elements to $0$. Next, for each element $a_i$ in $a$, increment $b_{a_i}$ by one. (this is the last element to be affected by $a_i$.)

Next, we will iterate backward over $b$, adding the next element and storing the result back into $b$. This effectively sums all higher elements in the old $b$.

Pseudocode:

conjugate(array a, int n, int m)
  b = new Array length m (all zeros)

  for i = 1 to n
    b[a[i]] += 1

  for i = m-1 downto 1
    b[i] += b[i+1]

  return b

Ruby Implementation

def conjugate(a)
  b = Array.new(a[0], 0)
  a.each do |x|
    b[x-1] += 1
  end
  (a[0]-2).downto 0 do |i|
    b[i] += b[i+1]
  end
  b
end

Try it online!

Efficiency

We have one loop over $a$ and one loop over $b$, giving $\Theta(n+m)$.

$\endgroup$
  • $\begingroup$ In the pseudo-code, shouldn't array b be of length m? And btw, m = a[0], right? $\endgroup$ – Vishal Sharma Jun 3 at 6:10
  • $\begingroup$ *(a[0] is the first element of a) $\endgroup$ – Vishal Sharma Jun 3 at 6:24
  • $\begingroup$ @VishalSharma Yes, the length of b should be m not n. If I can assume that m is equal to the first element of a then I can make this code a bit simpler... Let me do just that. $\endgroup$ – MegaTom Jun 9 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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