Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two values occurs.

From the cross-tabulations, we can derive a set of possible rows $R$ of $D$ and maximum frequencies for each possible row.

How can we reconstruct the original table $D$? If there is not enough information to do so, how can we construct a possible table $D'$ that has the same cross-tab frequencies? In this case, is it possible to count the number of possible tables?

(Edit: As Vor noted, define a table as an unordered collection of rows. A permutation of the rows of a table yields the same table.)

For example, if $D$ has rows:

X  A  j
Y  A  k
X  B  j
X  B  j

We have three sets of cross-tab frequencies:

X  A  1
X  B  2
Y  A  1
Y  B  0

X  j  3
X  k  0
Y  j  0
Y  k  1

A  j  1
A  k  1
B  j  2
B  k  2

I would like an algorithm which will take the cross-tab frequencies as input and output the original table or a possible original table.

  • $\begingroup$ My gut says it's NP-hard, but I don't see a reduction right now. $\endgroup$
    – Raphael
    Commented Sep 29, 2012 at 12:29
  • 2
    $\begingroup$ @Sarkom: I think that if you pick a permutation of the rows of the source table you get the same cross-table frequences, so in order make the unique solutions question more interesting you should add the constrain that all tables are presented in lexicographic order. $\endgroup$
    – Vor
    Commented Sep 29, 2012 at 12:43
  • $\begingroup$ You should specify the input as a list of (repeated) pairs or unarily encode the multiplicities otherwise the table may become exponentially large. $\endgroup$
    – frafl
    Commented Apr 6, 2013 at 13:15
  • $\begingroup$ @frafl: Can you clarify your comment? Are you suggesting that the input should be only pairs with no frequencies? If so, I don't understand how that would be more helpful. $\endgroup$
    – Sarkom
    Commented Apr 7, 2013 at 16:00
  • 1
    $\begingroup$ Of course each pair has to occur $k$ times if its frequency in the original table is $k$, so $(X,j,11_{2})$ becomes $(X,j)(X,j)(X,j)$. So the size of the input is $\approx \binom{M}{2}$ the size of the original table. $\endgroup$
    – frafl
    Commented Apr 7, 2013 at 16:47

1 Answer 1


We have $M$ columns $C_1, \dots, C_M$ in the original table, each with a finite set of distinct values $V_1, \dots, V_M$.

Given the cross-table frequencies $c_{i,j}(a,b)$ (frequency of $a$ in $V_i$ and $b$ in $V_j$ occurring together), proceed as follows:

  1. Determine $V_1, \dots, V_M$ and denote $V_i = \{v^{(i)}_j \mid j \in [1,n_i] \}$ where $n_i = |V_i|$.
  2. Solve the following integer program:

    $\qquad\displaystyle \min \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1,\dots,i_M)} \\ \qquad \begin{align} \text{s.t. } \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_{l-1} = 1}^{n_{l-1}} \sum_{i_{l+1} = 1}^{n_{l+1}} \cdots \sum_{i_{r-1} = 1}^{n_{r-1}} \sum_{i_{r+1} 1}^{n_{r+1}} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1, \dots, i_M)} &= c_{(l,r)}(i_l,i_r) \\ \qquad \text{for all } 1 \leq l < r \leq M, i_l \in [1,n_l], i_r \in [1,n_r], \\ x_{(i_1, \dots, i_M)} &\in \mathbb{N} \\ \qquad \text{for all } i_1 \in [1,n_1], \dots, i_M \in [1,n_M] \end{align}$

The $x_{(i_1, \dots, i_M)}$ now indicate which row should occur how often, and we get a solution with the minimum number of rows possible. If we can influence the search, we can abort as soon as we find any feasible solution.

This is not likely to be efficient, but there are honed solvers for integer programs around so it's simple to implement. It may be possible to use an LP-solver and round to a feasible solution.

  • $\begingroup$ How about $$\sum_{(i_1,\dots,i_M)\in V_1\times \dots \{i_l\}\dots\{i_r\}\dots \times V_M}$$? $\endgroup$
    – frafl
    Commented Apr 7, 2013 at 14:29
  • $\begingroup$ @frafl Not really prettier, isn't it? :/ I guess one could define some notatation like $\mathbf{V}[l\to\{i_l\}, r\to \{i_r\}]$ for $V_1 \times \dots \times V_M$ with update components at $l$ and $r$, but that would be hard to read in another way. $\endgroup$
    – Raphael
    Commented Apr 7, 2013 at 14:37
  • $\begingroup$ I don't know how "simple" it would be to implement ;) but I like this encoding using straightforward constraint satisfaction and don't see any better solution available. $\endgroup$
    – Sarkom
    Commented Nov 19, 2013 at 19:42

Your Answer

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

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