3

The following shows an example of X possible tables with constraints that will be specified shortly.

\documentclass[preview,border=12pt,12pt]{standalone}
\begin{document}
\begin{tabular}{ccc}
n & a & b\\
a & n & b\\
n & b & a\\ %<====== updated!
a & b & n\\
n & b & a\\
a & b & n\\
n & b & a
\end{tabular}
\end{document}

Image has been updated!

enter image description here

Constraints

  • There are only 3 columns.
  • There are only 3 characters n, a and b.
  • Two adjacent rows must not have character n in the same column. Note that the first and last row are not regarded as two adjacent rows. UPDATE: For each row other than the first one, the position of n is always below a.
  • The total number of characters other than n in the first column must always be 3.
  • The total number of characters other than n in the second column must always be 6.
  • The total number of characters other than n in the third column must always be 5.

How can I generate the X possible tables?

7
  • a and b don't play a part in the constraint so for every arrangement of the n there are 2^7 ways of adding ab or ba to each of the rows, do you need all those typesetting or is it enough to use an alphabet with n and two a. Jan 9, 2014 at 23:28
  • @StiffJokes OK but it's dull, there are 3 arrangements of the n, and then each of those has to be set 128 times with a and b swapped in each row. Jan 9, 2014 at 23:40
  • 3
    they may be important in the application but they are not important to the mathematics, mathematics is more important than real life. Jan 9, 2014 at 23:41
  • @StiffJokes yes but if you dropped the constraints and said print all the 3x7 tables with cells a b or n then there would be 21^3 different tables which would all mean something but it would be pointless to list them all. It's the same here, there are 3 different layouts with 128 copies of each layout by symmetry, showing the three layouts might be informative, typesetting 384 tables is not Jan 9, 2014 at 23:49
  • @StiffJokes yes, they do not involve a and b Jan 9, 2014 at 23:53

1 Answer 1

4

We can ignore the distinction between a and b (as they play no part in the constraint) any feasible layout will trivially have 2^7=128 variants by swapping the a and b on each row (or 4^7=16384 if a row may have 2 a or 2 b)

so there are these possible row types (call them 1 2 and 3)

n.. 1
n.. 1
n.. 1
n.. 1
.n. 2
..n 3
..n 3

you need to permute this collection so no row type appears in adjacent slots.

If you use all three types in the first three rows, then the remaining 4 rows have to be filled with 1113 which is impossible, so it is easy to see that the only possibilities are

1213131
1312131
1313121

that is

n.. 1
.n. 2
n.. 1
..n 3
n.. 1
..n 3
n.. 1

or

n.. 1
..n 3
n.. 1
.n. 2
n.. 1
..n 3
n.. 1

or

n.. 1
..n 3
n.. 1
..n 3
n.. 1
.n. 2
n.. 1

then each of those layouts copied 128 times if naa is not allowed or 16384 if it is) by replacing . . by a b and b a or by a a, a b, b a and b b depending.


With the updated question with the additional constraint the answer is as above except that there are just two copies rather than 128 of each layout, the . . on the last row being a b or b a every other row is determined as n is placed, a is forced by the n on the next row, and b has to go in the remaining slot (assuming the unstated constraint that there is an a and b in every row)

8
  • @StiffJokes well those were simple enough I just wrote them down, in general combinatoril problems usually have a simple solution that may be critically slow or a fast solution that depends on the exact nature of the constraint; for example you could easily even programming in tex, loop through all possible combinations of 1111233 and then check that there were no adjacent values. Coming up with a search path that generates valid results without having to backtrack or discard many invalid ones is harder, but may not be worth it if the search space is sufficiently small. Ask a sudoko player. Jan 10, 2014 at 1:04
  • @StiffJokes OK I updated the answer to match. Jan 10, 2014 at 1:16
  • 1
    True, but then it is no a TeX problem; it is a SAT problem, which is NP-complete. So you cannot expect to find an efficient solution
    – Aditya
    Jan 10, 2014 at 1:51
  • So you meant there are 6 tables? Jan 10, 2014 at 4:05
  • If {3,6,5} is changed to {3,3,4}, do you get 24 arrangements? Jan 10, 2014 at 7:54

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.