Upper Bounds on the Number of Indexes
=====================================

We obtained, by exhaustive search or by approximations, upper bounds on 
the number of indexes needed to implement wco algorithms in dimension 
up to d=8. In this file we leave a concrete sets of orders we found that 
work on each case. Remember that the letters mean:

W = worst-case (all)
C = circular
B = bidirectional
T = trie switching

These are the combinations and the upper bounds (the lower bounds in 
the paper come from the formulas given in Section 6). The numbers in 
brackets denote approximations, so the actual number of needed indexes
could be lower. The other numbers are exact. For W, CW, and TW, we
derived exact upper bounds in the paper, which we verified with our
program up to some value of d.

d	CBW	CW	W	CBTW	CTW	TW

1	1	1	1	1	1	1
2	1	1	2	1	1	2
3	1	2	6	1	2	6
4	2	6	24	2	4	12
5	5	24	120	5	8	30
6	10	120	720	7	12	60
7       [37]    720	5040	[13]    25	140
8       [168]   5040    40320   [25]    50    	280


Indexes CBW and CBTW
--------------------

d = 1: 1 order

1

d = 2: 1 order

1,2

d = 3: 1 order

1,2,3

d = 4: 2 orders

1,2,3,4
1,2,4,3

d = 5: 5 orders

1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,5,4,3
1,3,5,2,4

d = 6 for CBW: 10 orders

1,2,3,4,5,6
1,2,4,3,6,5
1,2,5,4,6,3
1,2,6,5,3,4
1,3,2,5,6,4
1,3,4,6,2,5
1,3,5,2,4,6
1,4,2,6,3,5
1,4,5,3,2,6
1,5,4,2,3,6

d = 6 for CBWT: 7 orders

1,2,3,4,5,6
1,2,3,5,6,4
1,2,4,5,6,3
1,2,6,4,3,5
1,3,4,2,6,5
1,4,3,6,2,5
1,4,5,2,3,6

d = 7 for CBW, approximation: 37 orders

1,3,6,4,5,2,7
1,4,6,2,5,3,7
1,2,3,6,7,5,4
1,3,4,2,6,7,5
1,2,7,4,5,3,6
1,5,3,2,4,7,6
1,4,3,7,2,5,6
1,2,3,7,6,4,5
1,2,6,3,4,7,5
1,4,2,3,6,5,7
1,3,5,4,2,7,6
1,2,5,7,3,4,6
1,3,7,2,6,5,4
1,6,5,3,4,2,7
1,2,6,5,3,7,4
1,5,2,4,6,3,7
1,5,2,3,7,4,6
1,3,2,7,5,6,4
1,5,4,3,2,6,7
1,3,5,2,4,6,7
1,2,5,4,7,6,3
1,4,3,2,7,6,5
1,4,7,5,3,2,6
1,2,4,6,3,5,7
1,2,4,5,6,7,3
1,3,4,7,5,2,6
1,2,7,5,4,3,6
1,3,6,5,2,4,7
1,4,2,6,3,7,5
1,5,3,4,7,2,6
1,6,3,2,5,4,7
1,3,2,6,4,7,5
1,2,5,6,4,3,7
1,2,6,3,5,4,7
1,3,7,4,2,6,5
1,5,3,4,6,2,7
1,2,7,3,6,5,4

d = 7 for CBWT, approximate: 13 orders

1,4,6,3,7,2,5
1,6,2,3,5,4,7
1,2,4,6,7,5,3
1,3,4,7,2,6,5
1,3,6,5,4,2,7
1,2,3,4,6,5,7
1,2,5,3,7,4,6
1,5,4,2,3,6,7
1,4,2,5,6,3,7
1,5,4,3,2,7,6
1,3,2,7,5,4,6
1,2,7,6,5,3,4
1,3,4,6,2,5,7

d = 8 for CBW, approximate: 168 orders

1,4,2,8,6,3,5,7
1,6,5,4,2,8,3,7
1,4,5,2,7,3,8,6
1,2,6,5,8,3,7,4
1,3,4,8,7,6,2,5
1,2,8,3,4,6,7,5
1,3,5,2,7,6,4,8
1,6,2,3,4,5,7,8
1,5,7,6,3,2,4,8
1,2,7,8,4,5,6,3
1,7,2,6,4,3,5,8
1,7,4,5,6,3,2,8
1,2,7,5,8,6,4,3
1,4,5,3,2,8,7,6
1,3,7,2,4,8,6,5
1,2,4,3,7,6,5,8
1,3,7,8,5,2,6,4
1,4,7,3,5,8,2,6
1,3,2,5,6,7,8,4
1,5,2,4,3,7,8,6
1,7,4,6,5,2,3,8
1,3,8,5,2,4,7,6
1,5,4,8,3,6,2,7
1,3,7,2,8,4,5,6
1,5,3,7,2,4,6,8
1,2,5,7,6,4,8,3
1,2,6,3,5,7,4,8
1,2,8,7,5,4,6,3
1,2,7,4,8,3,5,6
1,2,4,3,6,7,8,5
1,5,8,4,3,2,7,6
1,4,5,2,3,7,6,8
1,3,6,8,2,7,5,4
1,7,6,2,4,5,3,8
1,3,7,5,8,6,2,4
1,5,3,4,7,6,2,8
1,4,6,3,7,5,2,8
1,3,6,8,5,4,2,7
1,2,4,6,3,8,7,5
1,4,7,5,6,2,3,8
1,5,4,8,2,3,6,7
1,2,7,8,5,4,3,6
1,6,4,5,2,3,8,7
1,3,4,7,5,2,8,6
1,3,5,6,4,8,2,7
1,4,6,8,7,2,3,5
1,2,3,4,7,8,6,5
1,2,7,5,6,8,3,4
1,6,4,2,7,5,3,8
1,3,6,5,8,2,4,7
1,3,2,6,5,4,7,8
1,4,7,6,5,3,2,8
1,2,8,7,4,5,3,6
1,5,2,4,8,6,3,7
1,3,8,6,2,4,7,5
1,5,6,2,4,3,8,7
1,2,3,7,4,6,8,5
1,2,3,6,4,5,8,7
1,6,2,5,8,3,4,7
1,5,4,2,3,8,7,6
1,4,3,5,2,7,8,6
1,3,5,4,7,2,6,8
1,2,8,5,7,3,4,6
1,4,8,6,2,7,3,5
1,2,3,5,6,4,7,8
1,3,2,7,8,4,6,5
1,2,5,8,3,7,4,6
1,3,8,2,6,4,5,7
1,5,3,7,4,2,8,6
1,4,5,2,8,3,6,7
1,7,6,2,3,4,5,8
1,3,7,5,2,4,6,8
1,2,5,8,6,7,3,4
1,2,4,8,5,6,3,7
1,6,7,3,2,4,5,8
1,4,8,3,2,6,7,5
1,3,2,7,4,8,5,6
1,4,2,8,3,7,6,5
1,4,2,6,8,5,3,7
1,2,5,6,7,4,8,3
1,6,3,5,8,4,2,7
1,6,4,7,2,3,5,8
1,2,3,6,5,7,8,4
1,3,5,2,7,6,8,4
1,3,5,2,6,7,4,8
1,3,4,5,6,2,8,7
1,5,2,4,6,3,7,8
1,2,5,7,6,8,4,3
1,4,7,2,5,8,3,6
1,2,4,8,6,3,5,7
1,4,3,2,8,7,5,6
1,5,4,3,2,7,6,8
1,4,2,6,3,7,8,5
1,7,6,4,3,5,2,8
1,4,6,5,2,8,3,7
1,4,6,3,8,7,2,5
1,2,8,5,3,4,7,6
1,2,6,8,3,5,4,7
1,4,6,2,5,3,8,7
1,3,8,7,4,5,2,6
1,2,4,3,7,5,6,8
1,3,8,4,6,7,2,5
1,4,5,3,6,2,8,7
1,3,2,5,7,6,4,8
1,5,4,6,8,2,3,7
1,2,6,3,7,5,8,4
1,6,5,2,8,4,3,7
1,3,5,6,8,2,7,4
1,5,3,2,8,7,4,6
1,3,2,4,7,5,8,6
1,2,5,7,8,3,4,6
1,4,3,5,7,2,6,8
1,5,8,3,4,2,7,6
1,3,7,6,4,2,8,5
1,2,8,4,3,6,5,7
1,7,5,4,3,6,2,8
1,4,2,3,6,8,7,5
1,3,6,8,2,5,4,7
1,6,7,2,3,5,4,8
1,2,4,7,5,3,8,6
1,5,7,3,2,8,4,6
1,6,2,3,4,8,5,7
1,7,6,3,4,2,5,8
1,2,6,5,8,7,4,3
1,2,6,4,3,8,5,7
1,6,3,4,5,2,8,7
1,2,3,4,7,5,6,8
1,5,3,8,2,4,6,7
1,2,8,5,7,6,3,4
1,3,7,8,2,6,4,5
1,2,4,6,8,3,7,5
1,5,6,2,7,3,4,8
1,3,8,6,4,2,5,7
1,5,3,4,8,7,2,6
1,6,3,2,4,5,7,8
1,6,5,7,3,2,4,8
1,5,3,7,4,2,6,8
1,2,6,3,5,4,8,7
1,4,3,7,8,2,5,6
1,2,7,3,6,4,8,5
1,4,5,3,2,6,7,8
1,5,2,6,7,4,3,8
1,3,4,2,8,5,7,6
1,2,8,6,5,4,7,3
1,2,4,5,7,6,3,8
1,4,6,3,5,7,2,8
1,4,3,7,5,8,2,6
1,3,8,6,4,5,2,7
1,4,5,3,7,2,8,6
1,5,4,3,6,2,8,7
1,2,6,5,7,8,3,4
1,2,3,8,7,4,5,6
1,2,4,3,8,5,6,7
1,2,5,7,8,6,3,4
1,4,8,2,5,7,3,6
1,2,3,4,5,6,7,8
1,3,8,5,6,4,2,7
1,2,8,4,7,5,3,6
1,5,2,8,7,4,3,6
1,6,4,3,5,2,7,8
1,2,5,6,3,8,7,4
1,6,8,5,4,3,2,7
1,2,5,6,4,8,7,3
1,5,2,6,4,7,3,8
1,3,5,8,4,7,2,6
1,4,8,2,7,6,3,5
1,2,7,5,8,3,4,6
1,3,4,5,2,7,8,6

d = 8 for CBWT, approximate: 25 orders

1,3,6,7,8,4,2,5
1,2,3,7,5,4,6,8
1,4,3,8,5,6,2,7
1,4,7,8,2,3,5,6
1,5,8,2,6,4,3,7
1,6,2,3,4,5,8,7
1,4,2,7,5,6,3,8
1,2,6,8,7,3,5,4
1,5,6,7,4,2,3,8
1,3,2,5,8,4,6,7
1,3,8,7,5,2,4,6
1,2,8,4,6,3,7,5
1,4,5,6,3,2,7,8
1,3,5,8,7,6,2,4
1,6,5,2,3,7,4,8
1,2,3,4,8,6,5,7
1,2,6,8,3,7,4,5
1,3,2,5,4,7,8,6
1,3,4,6,5,2,8,7
1,2,7,6,3,4,5,8
1,4,6,8,3,2,5,7
1,5,3,8,2,4,7,6
1,5,4,3,8,7,2,6
1,3,7,6,4,8,2,5
1,4,7,3,2,6,8,5


CW and CTW
----------

d = 1: 1 order

1

d = 2: 1 order

1,2

d = 3: 2 orders

1,2,3
1,3,2

d = 4 for CW: 6 orders

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,3,2
1,4,2,3

d = 4 for CTW: 4 orders

1,2,3,4
1,2,4,3
1,3,4,2
1,4,3,2

d = 5 for CW: 24 orders

1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
1,2,5,4,3
1,2,5,3,4
1,3,2,4,5
1,3,2,5,4
1,3,4,2,5
1,3,4,5,2
1,3,5,4,2
1,3,5,2,4
1,4,3,2,5
1,4,3,5,2
1,4,2,3,5
1,4,2,5,3
1,4,5,2,3
1,4,5,3,2
1,5,3,4,2
1,5,3,2,4
1,5,4,3,2
1,5,4,2,3
1,5,2,4,3
1,5,2,3,4

d = 5 for CTW: 8 orders

1,2,3,4,5
1,2,3,5,4
1,2,4,5,3
1,3,4,2,5
1,3,5,2,4
1,4,5,2,3
1,5,4,3,2
1,5,2,4,3

d > 5 for CW omitted (exact formula known, verified up to d=5)

d = 6 for CTW, approximate: 12 orders (CW needs 5! = 120 orders)

1,6,2,3,4,5
1,5,2,6,4,3
1,3,2,5,4,6
1,2,4,6,3,5
1,4,6,5,2,3
1,5,6,3,2,4
1,5,4,2,3,6
1,4,3,2,6,5
1,6,4,5,3,2
1,2,3,5,6,4
1,5,3,4,6,2
1,3,6,4,2,5

d = 7 for CTW, approximate: 25 orders (CW needs 6! = 720 orders)

1,4,6,5,7,3,2
1,5,2,7,6,3,4
1,3,6,2,4,7,5
1,7,4,2,3,5,6
1,6,7,2,5,4,3
1,2,6,4,5,3,7
1,2,7,3,5,4,6
1,6,5,2,3,4,7
1,5,7,4,6,2,3
1,3,7,6,5,4,2
1,3,4,2,5,6,7
1,5,4,6,3,7,2
1,6,7,4,3,5,2
1,3,5,4,7,2,6
1,4,7,3,2,6,5
1,5,6,3,2,7,4
1,4,2,5,7,3,6
1,3,2,6,7,4,5
1,5,2,3,4,6,7
1,4,6,3,5,7,2
1,3,7,5,6,2,4
1,7,5,6,3,4,2
1,7,4,2,6,3,5
1,2,5,3,7,4,6
1,4,7,5,3,2,6

d = 8 for CTW, approximate: 50 orders (CW needs 7! = 5040 orders)

1,3,6,7,8,4,2,5
1,2,3,7,5,4,6,8
1,4,3,8,5,6,2,7
1,4,7,8,2,3,5,6
1,5,8,2,6,4,3,7
1,6,2,3,4,5,8,7
1,4,2,7,5,6,3,8
1,2,6,8,7,3,5,4
1,5,6,7,4,2,3,8
1,3,2,5,8,4,6,7
1,3,8,7,5,2,4,6
1,2,8,4,6,3,7,5
1,4,5,6,3,2,7,8
1,3,5,8,7,6,2,4
1,6,5,2,3,7,4,8
1,2,3,4,8,6,5,7
1,2,6,8,3,7,4,5
1,3,2,5,4,7,8,6
1,3,4,6,5,2,8,7
1,2,7,6,3,4,5,8
1,4,6,8,3,2,5,7
1,5,3,8,2,4,7,6
1,5,4,3,8,7,2,6
1,3,7,6,4,8,2,5
1,4,7,3,2,6,8,5
5,2,4,8,7,6,3,1
8,6,4,5,7,3,2,1
7,2,6,5,8,3,4,1
6,5,3,2,8,7,4,1
7,3,4,6,2,8,5,1
7,8,5,4,3,2,6,1
8,3,6,5,7,2,4,1
4,5,3,7,8,6,2,1
8,3,2,4,7,6,5,1
7,6,4,8,5,2,3,1
6,4,2,5,7,8,3,1
5,7,3,6,4,8,2,1
8,7,2,3,6,5,4,1
4,2,6,7,8,5,3,1
8,4,7,3,2,5,6,1
7,5,6,8,4,3,2,1
5,4,7,3,8,6,2,1
6,8,7,4,5,2,3,1
7,8,2,5,6,4,3,1
8,5,4,3,6,7,2,1
7,5,2,3,8,6,4,1
6,7,4,2,8,3,5,1
6,2,7,8,3,4,5,1
5,2,8,4,6,7,3,1
5,8,6,2,3,7,4,1


W and TW
--------

W is always d!, that is, all permutations

TW is always ceil(n/2) binomial(n,floor(n/2)); we verify this formula:

d = 1: 1 order

1

d = 2: 2 orders

1,2
2,1

d = 3: 6 orders

1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2

d = 4: 12 orders

1,2,3,4
1,3,2,4
1,4,3,2
2,1,4,3
2,3,1,4
2,4,3,1
3,2,4,1
3,1,4,2
3,4,1,2
4,2,1,3
4,3,2,1
4,1,2,3

d = 5: 30 orders

2,3,4,1,5
5,4,3,2,1
1,2,5,3,4
4,5,2,1,3
3,1,4,5,2
1,5,4,3,2
5,3,2,4,1
4,1,2,3,5
4,2,3,5,1
2,5,3,1,4
3,5,1,2,4
1,4,3,2,5
4,3,5,1,2
5,2,4,3,1
5,1,3,4,2
2,1,3,4,5
3,2,1,5,4
2,4,1,5,3
1,5,2,4,3
1,3,2,4,5
3,4,2,1,5
1,4,5,2,3
3,5,4,2,1
5,4,1,3,2
5,2,1,3,4
3,4,1,5,2
2,4,5,3,1
3,1,5,4,2
2,1,4,5,3
2,3,5,4,1

d = 6: 60 orders

3,1,2,4,5,6
4,5,6,3,1,2
5,6,2,4,1,3
2,3,5,1,6,4
6,2,3,4,1,5
5,4,2,6,3,1
1,2,6,4,5,3
1,3,4,6,5,2
2,6,1,5,3,4
3,2,6,1,5,4
5,2,6,3,1,4
3,4,5,6,2,1
5,1,3,6,4,2
3,5,1,2,4,6
1,4,2,6,3,5
5,3,4,2,1,6
6,4,3,2,5,1
1,6,5,4,2,3
6,3,1,2,4,5
6,5,3,2,4,1
4,3,2,1,6,5
2,1,5,4,6,3
4,1,5,6,3,2
1,5,4,3,6,2
4,6,1,3,2,5
2,4,1,5,3,6
4,2,5,3,6,1
2,5,1,6,4,3
3,6,5,1,2,4
6,1,4,2,3,5
4,1,3,5,2,6
5,1,2,3,4,6
1,3,6,5,4,2
2,3,1,6,5,4
5,6,1,2,4,3
3,1,5,4,6,2
2,4,6,3,5,1
1,4,6,5,3,2
6,4,2,5,3,1
5,3,2,4,6,1
2,4,3,5,1,6
2,6,5,1,4,3
4,3,6,1,5,2
3,2,4,6,1,5
3,6,4,5,2,1
5,3,6,4,1,2
4,5,1,2,3,6
2,1,4,3,5,6
6,4,5,2,1,3
2,5,4,1,6,3
6,3,2,5,4,1
1,5,6,3,2,4
6,1,2,3,4,5
4,3,1,2,6,5
6,5,4,1,3,2
5,2,3,6,4,1
2,1,3,5,6,4
1,6,3,4,5,2
2,6,4,1,3,5
4,5,3,1,6,2

d = 7: 140 orders

3,6,5,2,1,4,7
1,6,2,4,7,3,5
7,5,3,2,4,1,6
2,1,5,3,7,6,4
5,2,1,6,4,7,3
4,6,5,7,1,3,2
7,2,5,4,6,3,1
1,5,4,3,2,6,7
1,4,2,7,3,6,5
4,2,7,5,1,6,3
3,4,2,5,7,6,1
3,5,6,4,2,1,7
2,6,7,4,5,1,3
6,5,1,3,7,4,2
5,1,2,4,3,7,6
2,7,4,3,6,5,1
1,3,5,4,7,2,6
4,5,7,1,3,6,2
1,2,4,6,5,3,7
4,1,5,6,7,2,3
6,4,3,7,2,1,5
3,1,2,6,7,5,4
3,7,4,6,1,5,2
7,4,3,5,6,1,2
6,3,1,5,4,2,7
5,6,3,7,2,4,1
2,3,6,1,5,7,4
5,7,1,2,6,3,4
7,3,6,5,4,2,1
2,4,1,5,7,3,6
1,7,6,2,5,4,3
6,1,3,4,5,7,2
3,2,4,1,6,7,5
4,3,1,6,7,2,5
2,5,7,6,3,1,4
7,1,3,4,2,5,6
4,7,2,1,6,5,3
7,6,2,3,1,4,5
5,3,2,7,1,4,6
6,3,4,1,2,5,7
5,4,2,7,3,6,1
7,3,5,1,2,6,4
2,1,3,4,5,7,6
5,7,6,2,1,3,4
2,4,6,1,3,5,7
2,1,7,6,4,3,5
5,6,4,3,7,2,1
6,4,7,3,5,2,1
3,5,7,4,1,2,6
2,7,1,3,5,6,4
4,7,6,1,5,3,2
4,5,6,1,2,7,3
2,3,7,6,4,1,5
4,7,5,6,3,2,1
3,1,4,7,5,2,6
5,6,2,4,7,3,1
5,2,3,4,6,1,7
6,1,4,7,2,5,3
2,3,5,1,6,7,4
5,1,3,7,6,4,2
4,5,1,7,6,3,2
5,4,3,2,1,6,7
6,2,1,3,4,7,5
3,4,7,1,6,5,2
4,7,1,6,3,5,2
6,5,7,3,1,4,2
3,4,5,1,6,7,2
2,3,1,7,4,6,5
7,6,5,4,2,1,3
7,3,2,4,5,6,1
3,1,6,7,5,4,2
2,7,6,5,4,3,1
1,5,7,6,2,3,4
3,6,2,4,1,5,7
3,7,1,6,4,2,5
1,5,6,2,7,4,3
3,6,7,1,2,5,4
1,2,6,5,3,7,4
7,5,2,1,3,6,4
1,3,7,5,4,6,2
4,1,7,2,5,6,3
6,2,3,7,5,4,1
1,6,5,4,3,2,7
4,3,6,2,7,1,5
5,3,4,6,1,7,2
6,2,4,5,1,7,3
5,2,4,1,6,3,7
2,4,3,7,1,6,5
6,7,4,2,3,1,5
4,1,3,2,7,5,6
5,3,1,2,4,6,7
2,7,3,1,6,5,4
7,1,2,5,4,3,6
4,6,2,3,5,1,7
7,1,4,5,2,3,6
7,5,4,3,2,1,6
4,2,5,6,3,7,1
1,6,7,5,4,2,3
2,5,6,3,7,1,4
1,4,6,2,7,5,3
3,5,6,1,2,7,4
7,6,3,2,1,5,4
7,1,5,3,6,4,2
5,2,7,3,6,4,1
1,2,6,7,3,5,4
4,6,1,5,2,7,3
2,4,6,7,1,5,3
4,3,5,7,1,2,6
2,3,6,5,1,4,7
1,5,3,6,4,7,2
2,6,5,7,4,1,3
5,1,6,7,3,2,4
4,7,3,2,6,1,5
2,5,1,7,4,3,6
5,2,4,3,7,1,6
7,3,6,4,1,5,2
6,1,4,3,5,2,7
6,1,3,2,5,4,7
4,6,5,2,1,3,7
4,2,7,6,3,5,1
5,2,3,6,4,7,1
7,4,6,5,1,3,2
2,1,4,3,5,6,7
2,3,7,5,1,6,4
2,4,3,6,1,5,7
7,6,1,3,4,5,2
1,7,4,3,5,6,2
5,1,7,4,2,3,6
6,4,3,5,7,2,1
4,1,5,2,7,6,3
1,7,2,4,5,3,6
7,5,3,6,2,1,4
4,5,7,2,6,3,1
5,2,6,1,4,3,7
7,6,5,1,3,4,2
6,1,7,4,5,2,3
3,1,7,2,4,5,6
3,4,1,5,6,7,2
2,6,7,1,4,3,5
2,1,3,5,7,4,6

d = 8: 280 orders per the formula, not verified