RxC Sudoku band counting algorithm

Everything about Sudoku that doesn't fit in one of the other sections

RxC Sudoku band counting algorithm

Postby kjellfp » Mon Jan 09, 2006 10:49 pm

As earlier mentioned, I have an algorithm for counting the RxC Sudoku bands which seems to be exponential in R but only polynomial in C. This is a generalized algorithm for the one used to find the 4xC-formula, and it also leads to the already known formulas for 2xC, 3xC and 4xC band counting.

The idea is to break a band into two subbands (by distributing the boxes) with specifications on which symbols to place in which rows within a subband, and count the parts separately. And so move on by breaking into smaller subbands etc. until we are down to one-box "subbands".

Some definitions:
- N is the set of all non-negative integers, i.e. {0,1,2,..}.
- For any R>=1, N_R is the set {1,2,3,..,R} (a bit inconsistent as 0 lies in N but not N_R, but we can handle that. It's not my fault that the majority of this world believes numbering starts at 1 and not 0).
- For any 1<=L<=R, we define E(L,R) to be the family of all L-size subsets of N_R.
- For any 1<=L<=R and C>=1, we define A(L,R,C) to be the set of functions

a:E(L,R) -> N

with the property that for any x in N_R, Sum_U a(U)=C*L, where the sum is over all U such that x lies in U.

We define an RxC L-subband configuration to be an RxL matrix where the entries are elements of E(C,R*C) with the property that any two entries on the same row or same column are disjoint.

This is connected to RxC L-subbands (bands with L boxes of size RxC following the rules of Sudoku): For an RxC L-subband, we can create its RxC L-subband configuration by letting entry number (i,j) in the RxL-matrix be the set of symbols in row i and box j. So the number of RxC L-subbands is the number of RxC L-subband configurations times C!^(RL), and finally the number of RxC bands is the number of RxC R-subband configurations times C!^(R^2).

If B is an RxC L-subband, we can define a mapping F(B):N_(R*C) -> E(L,R) by mapping a symbol to the set of rows in which it occurs (each row is represented by a number in N_R). For such a map F, this again defines a map a(F):E(L,R)->N by sending a set U to the number of elements x in N_(R*C) such that F(x)=U. Then a(F(B)) lies in A(L,R,C) because every row of B contains C*L different symbols.

For any mapping F:N_(R*C) -> E(L,R), we define Z(L,R,C,F) to be the family of RxC L-subbands B such that F(B)=F. For any a in A(L,R,C), Z(L,R,C,F) is the same for every F such that a(F)=a, and so we define Z(L,R,C,a)=Z(L,R,C,F) for any F such that a(F)=a. Finally we define N(L,R,C,a) to be the size of Z(L,R,C,a).

For the case L=R, there is only one element of A(R,R,C): E(R,R) contains one element, the set N_R, and it has to be mapped to R*C. We call this mapping a_0, and so we have
Code: Select all
(1)   The number of RxC bands is (C!)^(R^2) * N(R,R,C,a_0)

(Notice that this does not imply the stronger trivial fact that the number is divisible by (C!)^(R*(R-1)) * (RC)! * (R-1)!, so this division has to be carried out at the end of the algorithm. The (R-1)! factor hasn't been mentioned by others, but comes from the permutations of box 2,..,R)

We now need an algorithm to express N(L,R,C,a) in terms of lower values for L (that corresponds to breaking up an RxC L-subband configuration into smaller subband configurations), and in the other end of the algorithm, to find N(1,R,C,a).

The last part is trivial:
Code: Select all
(2)   N(1,R,C,a)=1.

That is because given an RxC 1-subband (i.e. box) configuration B, the mapping F(B) uniquely describes B, and so Z(1,R,C,F(B))={B}.

For the breaking-up part, we need more notations:

Given M such that 1<=M<L. Define E(M,L,R) to be the subset of E(M,R) x E(L,R) of pairs (V,U) such that V is a subset of U. Given a mapping b:E(M,L,R) -> N, we can define a new mapping ^b:E(L-M,L,R)->N by ^b(V,U)=b(U-V,U), and we can define a mapping a(b):E(M,R) -> N by

a(b)(V) = Sum_U b(V,U)

where the sum is over all U in E(L,R) such that U contains V.

Given a mapping a in A(L,R,C), we define the set A(M,L,R,C,a) to be the set of mappings


such that
1. For every U in E(L,R), Sum_V b(V,U)=a(U) where the sum is over all V in E(M,R) such that U contains V
2. a(b) lies in A(M,R,C)

It can now be proven (details left out) that a mapping b:E(M,L,R)->N lies in A(M,L,R,C,a) if and only if ^b lies in A(L-M,L,R,C,a).

b describes how many symbols go where, when we break up the RxC L-band into an RxC M-band and an RxC (L-M)-band.

The result for N(L,R,C,a) is now done by summing up for N(M,R,C,a(b)) and N(L-M,R,C,a(^b)), and the number of ways to choose which symbols go where as described by the b-mapping. More formally:
Code: Select all
                       [                                     Prod a(U)!   ]
(3)   N(L,R,C,a) = Sum [ N(M,R,C,a(b)) * N(L-M,R,C,a(^b)) * ------------  ]
                       [                                    Prod b(V,U)!  ]

- The sum is over all b in A(M,L,R,C,a)
- The first product is over all U in E(L,R)
- The second product is over all (V,U) in E(M,L,R)

For each step in the algorithm, the result when breaking up should be independent from the choice of M, but I'm pretty sure the fastest result is achieved by letting M be as close to L/2 as possible, i.e. M=L/2 for L even and (L-1)/2 for L odd.

For L=R, a simplification: Symmetries allow us to group the mappings of the first splitting into equivalence classes being orbits of the effect of permuting the elements in N_R. Two elements in the same equivalence class give the same counting result.

[Edit: I have removed another argument saying that for R even and L=R/2, there was a simplification through N(M,R,C,a(b))=N(M,R,C,a(^b)) for any b in A(L,R,R,C,a_0). It only holds for R=2,4, not for R>=6]

A good way to dig into the algorithm is to show that it leads to the 2xC, 3xC and 4xC formulas. (Eh... and also the C |-> C! formula for R=1)
Posts: 140
Joined: 04 October 2005

Proof of 4xC

Postby PatmaxDaddy » Thu Jan 12, 2006 9:51 pm

The following is a proof of the formula for the number of bands for a 4xC grid, which is a specialization of the general method posted above.

We divide band 1 into two subbands, with boxes 1 and 2 in the first and boxes 3 and 4 in the second. We define parameters (a,b,c) of a subband and show that these parameters must be the same for each subband. We show how to compute the number of subbands for any given (a,b,c), and how to compute the number of bands from the number of subbands. Generally we use unprimed symbols for sets or quantities of the first subband, and primed symbols for those of the second subband.

Code: Select all
X & Y         intersection of sets X and Y
X | Y         union of sets X and Y
|X|           size of set X

S             set of 4C symbols
Pij           set of symbols in row j of box i, 1 <= i,j <= 4
Qj            set of symbols in row j of boxes 1 and 2
              1 <= j <= 4; Qj = P1j | P2j
Qj'           set of symbols in row j of boxes 3 and 4
              1 <= j <= 4; Qj' = P3j | P4j

a             |Q1 & Q2|
b             |Q1 & Q3|
c             |Q1 & Q4|
kij           |P1i & P2j|, 1 <= i < j <= 4

a'            |Q1' & Q2'|
b'            |Q1' & Q3'|
c'            |Q1' & Q4'|
kij'          |P3i & P4j|, 1 <= i < j <= 4

sel(x,y)      number of ways to select y elements from a set of x elements,
               i.e. x!/[y! * (x-y)!]

N(C)          total number of band 1 permutations for a 4xC grid

Example (4x3)
Code: Select all
   subband 1     subband 2
  0 1 2  3 4 6  5 7 9  8 A B
  3 4 5  0 1 9  8 A B  2 6 7
  6 7 8  2 A B  0 1 3  4 5 9
  9 A B  5 7 8  2 4 6  0 1 3

  S   = {0,1,2,3,4,5,6,7,8,9,A,B}
  P23 = {2,A,B}
  Q2' = {2,6,7,8,A,B}

  a = |{0,1,3,4}| = 4       a' = |{7,8,A,B}| = 4
  b = |{2,6}|     = 2       b' = |{5,9}|     = 2
  c = |{}|        = 0       c' = |{}|        = 0

  k12 = 2                   k12' = 1
  k13 = 1                   k13' = 2
  k14 = 0                   k14' = 0
  k23 = 0                   k23' = 0
  k24 = 1                   k24' = 0
  k34 = 2                   k34' = 3

Trivial Lemmas
By the rules of Sudoku:
Code: Select all
    |S|            = 4C
    |Pij| = |Pij'| = C
    |Qj|  = |Qj'|  = 2C

Lemma 1: a = a'; b = b'; c = c'
By the rules of Sudoku, every symbol must appear twice in rows 1 and 2 of band 1. In the 4C cells of rows 1 and 2 of the first subband (corresponding to Q1 and Q2), (a) symbols appear twice, (4C - 2a) symbols appear once, and therefore [4C - a - (4C - 2a)] = a symbols do not appear. These (a) symbols that do not appear in the first subband must be exactly the ones that appear twice in rows 1 and 2 of the second subband, and so a' = |Q1' & Q2'| = a. A similar argument establishes that b = b' and c = c'.

Lemma 2: |Q3 & Q4| = a; |Q2 & Q4| = b; |Q2 & Q3| = c
By the rules of Sudoku, every symbol must appear twice in boxes 1 and 2. Lemma 2 is established following the same reasoning as for Lemma 1.

Lemma 3: a + b + c = 2C
By the rules of Sudoku, every symbol must appear twice in boxes 1 and 2. By definition, each of the 2C symbols in Q1 appears once in row 1. (a) of these symbols must appear a second time in row 2 but not in rows 3 and 4. (b) of these must appear a second time in row 3 but not in rows 2 and 4. (c) of these must appear a second time in row 4 but not in rows 2 and 3. These second appearances must total 2C, so a + b + c = 2C.

Lemma 4: k12, k34 <= a; k13, k24 <= b; k14, k23 <= c
By definition, k12 = |P11 & P22| and a = |Q1 & Q2|. Since P11 is a subset of Q1, and P22 is a subset of Q2, it follows that k12 <= a. Similarly, k34 = |P13 & P24|, and by lemma 2 a = |Q3 & Q4|. P13 is a subset of Q3 and P24 is a subset of Q4, so k34 <= a. Same argument for the other parameters.

Lemma 5: k12 + k13 + k14 = C
By the rules of Sudoku, every symbol must appear once in box 2, and the C symbols of P11 cannot appear in P21. Therefore they must appear once in P22, P23, or P24. The lemma then follows from the definition of k12, k3, and k14. More formally,
Code: Select all
k12 + k13 + k14 = |P11 & P22| + |P11 & P23| + |P11 & P24|       definition
                = |[(P11 & P22) | (P11 & P23) | (P11 & P24)]|   P22, P23, P24 are disjoint
                = |P11 & (P22 | P23 | P24)|                     property of sets
                = |P11|                                         rules of Sudoku
                = C                                             trivial lemma

Lemma 6: a-k12 + k23 + k24 = C
By the definitions of a and k12, (a-k12) of the symbols in P12 appear in P21. The reamining [C - (a-k12)] symbols in P12 appear in neither P21 nor P22, so they must appear once in P23 or P24. So |P12 & P23| + |P12 & P24| = k23 + k24 = C - (a-k2).

Lemma 7: b-k13 + c-k23 + k34 = C
(b-k13) of the symbols in P13 appear in P21. Using lemma 2, (c-k23) of the symbols in P13 appear in P22. Since P12 and P22 are disjoint, the (b-k13) symbols and the (c-k23) symbols are distinct. Therefore, C - (b-k13) - (c-k23) symbols from P13, which cannot appear in P23, must appear in P24. So |P13 & P24| = k34 = C - (b-k13) - (c-k23).

Lemma 8: c-k14 + b-k24 + a-k34 = C
This is a redundant constraint that follows from lemmas 5, 6, and 7. If we sum those three constraints we get (a + b + c) + (k14 + k24 + k34) = 3C. Since (a + b + c) = 2C (lemma 3), it follows that (k14 + k24 + k34) = C and (a + b + c) - (k14 + k24 + k34) = C, which is the lemma.

Lemma 9: For a given Q1, Q2, Q3, Q4, consistent with the rules of Sudoku, the number of 2-box subbands is given by D(a,b,c) = (C!)^8 * SUM[sel(a,k12) * sel(b,k13) * sel(c,k14) * sel(c,k23) * sel(b,k24) * sel(a,k34)], where the sum is over all kij consistent with the constraints of the above lemmas.
To make a subband from the given Qj, one needs first to decide for each Qj which of the 2C symbols are placed into P1j and which are placed into P2j. Following this placement, each of the 8 Pij sets can be permutted independently in C! ways.

For Q1, k12 of the (a) symbols in Q1 & Q2 must be placed in P11, and there are sel(a,k12) ways to do this. Similarly, k13 of the (b) symbols in Q1 & Q3 must be placed in P11 (sel(b,k13) ways), and k14 of the (c) symbols in Q1 & Q4 must be placed in P11 (sel(c,k14) ways). By the rules of Sudoku these symbols are all distinct, and since k12 + k13 + k14 = C (lemma 5), P11 is now filled. This means that P21 is also decided (from the remaining symbols of Q1).

For Q2, a-k12 symbols from Q1 & Q2 must be placed in P12 due to the prior placements of Q1. k23 of the (c) symbols in Q2 & Q3 must be placed in P12 (sel(c,k23) ways), and k24 of the (b) symbols in Q2 & Q4 must be placed in P12 (sel(b,k24) ways). By lemma 6 P12 and P22 are now filled.

For Q3, b-k13 symbols from Q1 & Q3, and c-k23 symbols from Q2 & Q3, must be placed in P13 due to the prior placements. k34 of the (a) symbols in Q3 & Q4 must be placed in P13 (sel(a,k34) ways). By lemma 7 P13 and P23 are now filled.

By lemma 8 P14 and P24 are now filled. Since every possible subband has a unique set of kij values, D(a,b,c) can be found by summing the number of ways of making the above placement decisions over all kij and then multiplying by the (C!)^8 Pij permutations. The result is lemma 9.

Theorem: N(C) = (4C)! * SUM[D(a,b,c) / (a! * b! * c!)]^2, where the sum is over all a,b,c, a+b+c=2C
Note that this is an equivalent form of Kjell's 4xC formula. By the rules of Sudoku, a given Q1, Q2, Q3, and Q4, fixes Q1', Q2', Q3', and Q4'. There are D(a,b,c) possible first subbands, and D(a',b',c') possible second subbands. By lemma 1 D(a',b',c') = D(a,b,c), so there are D(a,b,c)^2 possibilities for band 1 for the given Qj. Multiplying this by the number of possible ways G(a,b,c) to select the Qj gives the total number of bands for a given (a,b,c). Since every band has a unique (a,b,c), summing this over all (a,b,c) gives N(C). Thus we need to show that G(a,b,c) = (4C)! / (a! * b! * c!)^2.

First, any 2C symbols from S can be placed in Q1. There are sel(4C, 2C) ways to do this. (a) of the symbols from Q1 must also be placed in Q2, and there are sel(2C, a) ways to select them. The remaining 2C-a symbols in Q2 are chosen from the remaining 2C symbols of S, for sel(2C, 2C-a) = sel(2C, a) possibilities.

For Q3, we need (b) symbols taken from the 2C-a symbols of Q1 that are not also in Q2. There are sel(2C-a,b) ways to do this. We also need (c) symbols from the 2C-a symbols of Q2 that are not also in Q1, for sel(2C-a,c) ways. There are 2C-b-c = a (lemma 3) remaining symbols to be chosen for Q3, and these are the (a) symbols that must also appear in Q4 so they have not previously been chosen. We have so far chosen 2C + 2C-a distinct symbols from S, leaving (a) left to choose. Thus there is only one way to choose the remaining (a) symbols for Q3.

Q4 must have (c) symbols from Q1, (b) from Q2, and (a) from Q3, and since a + b + c = 2C there is only one way to choose Q4.

Reviewing the choices that have been made, it is clear that G(a,b,c) = sel(4C,2C) * sel(2C,a) * sel(2C,a) * sel(2C-a,b) * sel(2C-a,c). Substituting the formula for sel(x,y) and using lemma 3 shows that G(a,b,c) = (4C)! / (a! * b! * c!)^2.
Posts: 63
Joined: 18 October 2005

5xC band results

Postby PatmaxDaddy » Mon Jan 23, 2006 7:49 pm

Using Kjell's general RxC band counting method described above, I've derived a general 5xC formula and used it to confirm the results for 5x3 and 5x4 that I've previously posted (and which are on Wikipedia). I've also gotten the following new results:

Code: Select all
(5*5)! * (5!)^20 * 1,165,037,550,432,885,119,709,241,344
= 6928042180450972720240516448256634678593424862504020477110
= 6.92804e93

(5*6)! * (6!)^20 * 3,261,734,691,836,217,181,002,772,823,310,336
= 12127146844352548382441074390819055815670977528914163679181616287
= 1.21271e123

In addition, we can now use the KSP formula to estimate a full 5x5 Grid. The result is 4.36479e308.

I'll post the formula when I can figure out a good way to do it.

Following Kjell, I break up the 5-box band into a 2-box subband and a 3-box subband. The 3-box subband is further split into a 2-box subband and a 1-box subband. The 2-box subbands are easily counted and then combined with the number of ways of doing the splitting, although it was harder to figure out than it sounds. I use 2-box equivalence classes to speed things up by at least an order of magnitude.

The formula, which may not be the most efficient way to implement 5xC, has complexity O(C^21). This may sound like a very severe polynomial, and it is, but it is instructive to see just how much better any polynomial-time algorithm is compared to the exponential-time method I used to get 5x3 and 5x4. Here are the comparisons:

Code: Select all
    exponential   C^21 polynomial
5x3  90 sec           0.66 sec
5x4  68 hours        18    sec
5x5  10 years?      276    sec
5x6                3552    sec

Credit for these results should go primarily to Kjell, as it's entirely his method. Speaking for myself, there's no way I would have developed anything like it independently, nor did I contribute anything other than a decent implementation.
Posts: 63
Joined: 18 October 2005

Postby PatmaxDaddy » Tue Jan 24, 2006 1:42 am

I changed the attribution on Wikipedia to give primary credit to Kjell; this is much more his work than mine.
Posts: 63
Joined: 18 October 2005

Postby kjellfp » Tue Jan 24, 2006 9:23 am

Great! I had started an implementation, but didn't complete it. Istead, I have used my tiny spare time to find and write a different way of counting the 3x3-grids which currently completes in 30.2 milliseconds (3 GHZ), and that is before you have put your fingers on it. I'm sure you will bring it even further down if you have time. I wrote the majority of a posting about this result, but of course something went wrong, and the entire text was lost. I'll try to do it again this evening, and also send the code to you.

Back to RxC. As I see it, it's less work to change a 5xC-counter to a 6xC-counter than to just write the 5xC-counter. Any thoughts on this?
Posts: 140
Joined: 04 October 2005

Postby PatmaxDaddy » Wed Jan 25, 2006 4:11 am

kjellfp wrote:As I see it, it's less work to change a 5xC-counter to a 6xC-counter than to just write the 5xC-counter. Any thoughts on this?

Yes, I mostly agree that it will be easier to change the 5xC to a 6xC than it was to write the 5xC in the first place. Splitting the 6 boxes into two 3-box subbands is not quite the same as a 2-box/3-box split, but it's similar enough that much of what I had to understand will apply. The 5xC work on splitting and counting a 3-box subband (a 2-box/1-box split) should carry over (it will be interesting to see how much).

For me, the work needed to do the 5xC was about 80% math (getting a pencil-and-paper understanding of the method, from which I could derive the general 5xC formula), 10% programming, and 10% debugging. I expect for 6xC the math will be greatly reduced now that I have gotten my tiny mind around the method, and the programming will also be reduced because I now know how to implement these things. What I worry about, however, is debugging. It was very important to have the 5x3 and 5x4 results from the earlier brute-force counting method to check both the math and the code. I made some mistakes and had a few incorrect implementations before finally getting it to come out right. We currently don't have any 6xC results to use as checks, and the prospects for getting some are not good. Of course we can get 6x1 and maybe 6x2 to use as a check, but that may not be good enough. At one point I had a bug that made 5x4 come out wrong, but 5x3 was right.

Of course I worried that the posted 5x3 and 5x4 numbers I used as checks might be wrong, since the method and implementation used to compute them were complex and there was never any independent confirmation, but I felt confident that if the two very different methods agreed then they are both almost certainly correct. This suggests but does not guarantee confidence in the 5x5 and 5x6 results. For 6xC we will really need an independent imploementation to have much confidence.

I should mention that I ran 5x7 overnight (it took 9 hours) and got:

Code: Select all
(5*7)! * (7!)^20 * 10,664,509,989,209,199,533,282,539,525,535,793,414,144
= 1232492492769898213342873945393435879186452412857118087762318362696116776916615

= 1.23249e+154
[Edit: Value corrected 20 Feb 2006]

My experience with 5xC suggests that doing 6x6 (perhaps the most rewarding 6xC case) is going to take a very long time. Not impossibly long (like the 10 years I estimated for 5x5 with my old method), but probably measured in days. I keep wondering if there is a more efficient way to implement these methods than the one I used for 5xC, which is O(C^21). I know my code is pretty good, but reducing the algorithmic complexity is Kjell's specialty.

What I wonder most about right now is whether we can use a method inspired by Kjell's RxC band counting to count a complete 4x3 or 4x4 grid. I refer back to Kjell's posts in the 4x3 thread about superbands. It is clear that what he was talking about is very much in line with his ideas on RxC band counting, and now that I've been working to understand 4xC and 5xC I can see the wisdom in his superband ideas. The key is that the two superbands are not independent, they are intimately linked (just like the split subbands are linked) so that we need not count all combinations of both bands, but rather only the configurations of one superband. Perhaps the superbands can also be split into "superboxes". Maybe a 4x4 grid can be split into two 2-row superbands, and a superband can be split into two 2x2-box superboxes. A 4x4 grid would split very nicely. But this is just speculation, and is right now a far cry from a method.
Last edited by PatmaxDaddy on Mon Feb 20, 2006 8:09 pm, edited 1 time in total.
Posts: 63
Joined: 18 October 2005

Postby kjellfp » Wed Jan 25, 2006 10:03 pm

I'm impressed by what you have acheived by the implementations. I have tried to implement, but often find it hard, particularly to get the fast implementation.

I'm aware of the problem that we only have the 6x1-value to use as number-checking for 6xC (this is the number of 6x6 latin squares, which has been known for a long time). But combined with the experience and debugging done when you did 5xC, I would have confidence in your results. Maybe it's possible to do 6x2 by brute force too.

From what you wrote about the 5xC computation times for C<=6, I guessed 5x7 would take about 10 hours. And that 5x8 will take less than 4 days.

I still think 4x4 is undoable. Remember that 3x3 takes 0.03 seconds, while 4x3 is still estimated to take at least some months. Jumping to 4x4 is probably just as wild, but at least, I believe the number of loops can be calculated pretty accurately.

I don't think splitting the main grid in both row and column direction is practical. When I do the splitting, I always do it with only the column configurations, or only the row configurations given. Combining the two seems too messy. But who knows...

You're quite right that the ideas about superbands for 4x3-counting, and the splitting ideas that first lead to the 4xC formula, and later to the RxC-algorithm, are strongly related.

Btw, I have another fast counting algorithm for 3x3 which you might find interesting, posted here.
Posts: 140
Joined: 04 October 2005

Postby PatmaxDaddy » Fri Jan 27, 2006 4:50 am

The number of 5xC bands is given by

Let x be a 10-vector of integers, with components xij, 1 <= i < j <= 5, and subject to the following constraints:
Then p(x) is the number of 5xC 2-box subbands that can be made from a given assignment of symbols to rows, and is given by
where k is a 10-vector of integers with components kij subject to the constraints
b is a 30-vector of integers, with components bijr, 1 <= i < j <= 5 and r an element of {1,2,3,4,5} - {i,j}, and subject to the constraints
d(b) is given by
It can be shown that d satisfies the constraints required by p.

This formula is O(C^21) because the outer sum is O(C^5) (10 variables each O(C), 5 independent constraints) and the inner sum is O(C^16) (30 variables each O(C), 14 independent constraints because any one of the five formulas that sum to C can be derived from the other constraints). Note that all of the products are constant time, the factorials and binomials can be precomputed in O(C^2), and all of the p's can be precomputed in O(C^5) [Edit: That's wrong, it should be O(C^11)].

The set of x vectors (i.e. a and d) can be reduced to a relatively small set of equivalence classes. This speeds things up considerably, but doesn't change the O(C^21) complexity (at least I don't think it does). I'll say more about these classes in a subsequent post.

I hope the formulas are legible, I tried a new method.
Last edited by PatmaxDaddy on Sat Jan 28, 2006 7:02 pm, edited 1 time in total.
Posts: 63
Joined: 18 October 2005

Postby PatmaxDaddy » Sat Jan 28, 2006 9:14 pm

The following is an equivalent form of the 5xC formula.
The previous version reflects the way the formula is derived from the subband splitting and counting method of Kjell. This version is the one I use for computational purposes. One obvious difference is that certain constant factors are brought outside the summation, resulting is a formula that reflects the obvious symmerties of a band. The product in the inner sum is designed to guarantee that the divisions produce integers, and to keep the dynamic range small enough so that native arithmetic types can be used instead of resorting to aribtrary-precision arithmetic.

For any value of C, there is a specific set of possible values of 10-vectors consistent with the constraints of x. This set can be divided into equivalence classes for purposes of counting subbands. The 10-vector can be divided into two mutually-dependent sets of five elements. In the above post these sets are {x12, x23, x34, x45, x15}, and {x13, x35, x25, x24, x14}, although other equivalent divisions can be used. Either set can be derived from the other. Note that, considering the ij indicies, these sets have a ring structure. An equivalence class is defined as the vectors that can be reached by rotating either ring and then re-deriving the other ring, or by swapping the rings. A representative member of each class is obtained by putting a vector in canonical form, which can be reduced to a 5-element code that can easily fit in a 32-bit integer. Here are the number of equivalence classes for some values of C:

Code: Select all
1    3
2   19
3   69
4  208
5  505
6 1089
7 2106

In my program, the outer sum is taken over just the representative members of each class. In the inner sum the values of d are put in canonical form and then looked up in a sorterd table with a binary search. I just realized that this means that my implementation is actually O(C^21 * log(C)). Note that without precomputing and looking up the values, the computation would be O(C^26).

Please speak up if the formulas are not legible, since I'm using a new method to display them.
Posts: 63
Joined: 18 October 2005

Postby kjellfp » Sun Jan 29, 2006 3:08 pm

Just a thought if you are going to do 6xC:

If you are precomputing the 2-box subband numbers as for 5xC-counting, and then looking up the values at the final count, I think it will be faster if your first band-breaking will be in one subband of size 2 and one of size 4, instead of two 3-size subbands. Then you break the 4-subband into 2-subbands.

This takes more direct advantage of having 2-size subbands precalculated.

For the same reason, I think maybe the 4x3 grid counting is faster done band by band, than the superband method. I have submitted a post on this issue in the 4x3-thread.
Posts: 140
Joined: 04 October 2005

Postby kjellfp » Thu Feb 02, 2006 9:04 am

Some more thoughts...

Though the method is messy when we start studying it in details, it's still not very complex (in principle). What we are dealing with are

- Lots of integer variables
- Linear relations between the variables
- Inequalities to give bounds (all inequalities come from the fact that every variable must be non-negative)

Couldn't very much of this be done by computer (and so we are back to your idea about a program to output C-code)? Linear algebra is typically messy to handle by hand, and trivial to do by computer. The inequalities are also about working with linear relations.

RxC counting (for R fixed) has complexity O(C^N(R)) for some integer N(R). The rank of the matrix of all linear relations (which again is the number of free variables from which all other variables are explicitely given) is N(R). So I think it's an idea to let the computer do this part of the coding.

Some "hand-made" contributions will help as well, like using the advantage of symmetry during the "main" break, or doing the 2-size subband counting in advance.
Posts: 140
Joined: 04 October 2005

Postby PatmaxDaddy » Sat Feb 11, 2006 11:51 pm

I've got several results related to RxC band counting:

1) A vastly improved method of generating equivalence classes for subband state vectors, one that results in far fewer classes (probably optimally few), and which can be used for any K-box subband of an RxC band, not just a 2-box subband of 5xC. I've got a fully general implementation of this method that has been tested on 5xC and which will be used for 6xC and maybe higher values of R.

2) A general startegy for RxC band counting based on precomputing counts of successively larger subbands, using the above equivalence classes. The counts are stored in tables indexed by a representative member of each equivalence class of subband state vectors. The tables are sorted for O(log(C)) lookup. Note that this strategy is one possible way to implement Kjell's method, it is not a different method for band counting.

3) A general analysis of the algorithmic complexity of RxC band counting using my strategy for implementing Kjell's method. This analysis shows that the most efficient strategy is to split bands in half (as near as possible), as Kjell originally speculated:
kjellfp wrote:I'm pretty sure the fastest result is achieved by letting M be as close to L/2 as possible
; but contrary to his later suggestion:
kjellfp wrote:If you are precomputing the 2-box subband numbers as for 5xC-counting, and then looking up the values at the final count, I think it will be faster if your first band-breaking will be in one subband of size 2 and one of size 4, instead of two 3-size subbands. Then you break the 4-subband into 2-subbands.

4) The 5x8 band count, which I can now do in only 10 hours using the new equivalence classes.


In general an RxK subband (K RxC boxes) is described by a state vector with sel(R,K) integer components (sel is the binonial R!/(R-K)!K!), where each component corresponds to a selection of K rows from the R available, with the value equal to the number of symbols that are found in all K rows of the subband. All subbands with the same state vector have the same count. An equivalence class of state vectors can be defined as all vectors that can be generated by any permutation of the R rows. This is a far more comprehensive definition of equivalence classes than I used above in dividing the 10-vector for 5x2 subbands into a pair of 5-element rings, and it applies to any RxK subband. The difficulty in applying this definition is generating a canonical member of a class from any given vector very quickly, since this has to be done in the innermost loop. I finally implemented a reasonably efficient and completely general way to do this. One trick is to use C++ template classes. R and K are template parameters, so the compiler can generate code for any R and K, but R and K are compile-time constants so the compiler can do better optimization.

Here is a comparison of the old and new method:
Code: Select all
     previous method     current method
 C    classes   time     classes   time
 1         3      <1          2      <1
 2        19      <1          7      <1
 3        69      <1         16      <1
 4       208      18         37       5
 5       505     276         73      62
 6      1089    3552        140     680
 7      2106   32202        245
 8                          415   36375
 9                          664
10                         1031

Here is the 5x8 result:
Code: Select all
(5*8)! * (8!)^20 * 39119289737902332276642894251428026550280700096
= 4115726412595961837618972705021617780954992462923399713992174350142637439412909696
= 4.11573e+186
[Edit: Value corrected 20 Feb 2006]

The RxK state vector is subject to R independent constraints, so there are sel(R,K)-R degrees of freedom (DOF). Note that if K = 1, there are no degrees of freedom, as expected (there's only one way to do it: all of the sel(R,1) components of the state vector must be [Edit] C). To split an RxK subband into RxL and Rx(K-L) subbands (an RxKxL split), one must have sel(K,L) = sel(K,K-L) parameters for each of the sel(R,K) components of the RxK state vector, so the splitting is described by a [sel(R,K) * sel(K,L)]-component split vector. In my above post of 5xC, the 30-vector b describes a split where R = 5, K = 3, L = 2, which the reader can confirm has 30 components. A split vector is subject to sel(R,K) + R - 1 independent constraints, and so has sel(R,K) * (sel(K,L) - 1) - R + 1 DOFs.

Note that an RxK state vector is equivalent to an RxRxK split vector as one might expect. The number of components and the number of DOFs is the same. Thus we can consider state vectors to be just special cases of split vectors.

Now consider 6xC counting. First we compute the counts for each equivalence class of the 6x2 subbands and store them in a sorted table. This requires splitting the 6x2 subband into two 1-box subbands, so R = 6, K = 2, L = 1. The 6x2 state vector has 9 DOFs and the 6x2x1 split vector has 10 DOFs, so the table can be made in O(C^19). Next we compute the counts for each equivalence class of the 6x3 subbands and store them in another table. 6x3 state vectors have 14 DOFs, and 6x3x2 split vectors have 35 DOFs. Since the 6x2 counts can be looked up in O(log(c)), the 6x3 table can be made in O(C^49 * log(C)). Finally, each 6x3 subband in boxes 1 - 3 corresponds to a unique (but different) subband in boxes 4 - 6. Using the 6x3 lookup table, the final count can be done in O(C^14 * log(C)). Thus the overall complexity is O(C^49 * log(C)).

The method just described for 6xC can easily be generalized for any RxC, and the complexity can easily be determined.

As an alternative for 6xC, we could do a 4-2 split instead of a 3-3 split. We'd only need the 6x2 table, but the 6x4x2 split is very expensive, with 70 DOFs. Overall we'd have a complexity of O(C^79 * log(C)).

I'm planning to implement 6xC, possibly using both 3-3 and 4-2 splits so I can check one against the other. It will take some time, however, because my spare time is quite limited.
Last edited by PatmaxDaddy on Mon Feb 20, 2006 8:12 pm, edited 1 time in total.
Posts: 63
Joined: 18 October 2005

Postby deam3r » Mon Feb 13, 2006 5:04 am

Code: Select all
1    3
2   19
3   69
4  208
5  505
6 1089
7 2106

Yall would need it!
Posts: 10
Joined: 12 February 2006

Postby deam3r » Mon Feb 13, 2006 5:04 am

sorry, You allready posted the code..
Code: Select all
1    3
2   19
3   69
4  208
5  505
6 1089
7 2106
Posts: 10
Joined: 12 February 2006

Postby PatmaxDaddy » Sun Feb 19, 2006 3:25 am

Thought someone might find the following interesting. Define N(R,C) such that the RxC band 1 count is (R*C)! * (C!)^[R*(R-1)] * N(R,C). This is the conventional way we show the count. Here is a plot of log10(N) as a function of C for R=3 (blue), R=4 (yellow), and R=5 (magenta). The lines are best fit, but ignoring some of the low values of C.
The lines look straight on the plot, but they not quite for low values of C; the slope of the curve increases very slightly at each point. They do seem to converge to straight lines for large C, but they converge very slowly. I ran 3xC out to C=15000, and 4xC out to C=100. I couldn't quite tell if 4xC was going to converge, but 3xC seems to do so. The 3xC slope ends up around 0.9031, 4xC around 3.1, and 5xC is around 6.5 or so for the low values of C that I've been able to run.
Posts: 63
Joined: 18 October 2005


Return to General