Langford Sequence - Utilize symmetry / Remove symmetry

Question

i've written a Programm that can calculate the Number of Possible Langford sequences (https://en.wikipedia.org/wiki/Langford_pairing).

---

TL;DR Langfordsequences are defined by L(s,n) where s is the amount of occurences of a certain number

and n is the amount of possible numbers/colors the numbers define how many positions they have to be aport of each other

The Picture would be L(2, 4) ==> each Number has 2 occurances and there are 4 Distinct Numbers. The Amount of |L(2,4)| would be 1 because theres only one possible permutation that satisfies the constraints

---

The Idea behind calculating the Amount of possible Permutation is as followed. L(2,4) We start with a Bitset[s*n] of all 0 as Root

at each Depth we get all Possible Permutations where all occurences of the curret Number (= n-depth) are excellent n-depth positions apart.

in depth 1 we get all possible positions for 4 =>

10000100

01000010

00100001

Per Possible Permutation i check if theres a collision (if one of the positions used is already in use by another number). i did this by counting the amount of bits that are 1 and compared them with the parent bits. if (currentPos xor Parent).count() == Parent.count() + s then there was no collision and i can get in one depth deeper. (check all possible permutations for 3 that statisfie the constraints)

if all bits are equal to one [(currentPos xor Parent).count() == s*n] we reached a Possible Permutation where each Number is its value apart from each other for each Number.

This is working so far, but ive got each Number doubled compared to what i should get as a result, because i didnt took the symmetry into consideration. (for L(s,n) i always get 2*L(s,n))

I was wondering on how to utilize the symmetry of the tree to get the right results.

---

My initial Idea was to just use just use first to ceil(len(Permutation) / 2) Permutations (Red-Selection on the following image). But this resulted in every worse results.

---

im not really sure what i should poste here to let you guys help me - but i hope somebody could give me a hint or something

Ty in advcanded

---

Answer 1

L(s, n) is "up to reversal of the order" see e.g. https://oeis.org/A014552 . This means e.g. that for |L(2, 4)| we have

4 1 3 1 2 4 3 2

and

2 3 4 2 1 3 1 4

are both satisfying the property, but one is just the reverse of the other so |L(2, 4)| = 1.

To take this into account in your algorithm, you can check e.g. at the very first level that there are more free bits to the left than to the right.

NB: your algorithm enumerates all solutions, so the complexity is > L(2, n) and for n = 20 this is already more than 2^41. You probably won't reach this. As mentionned on the Wikipedia page:

for large n the number of solutions can be calculated more efficiently by algebraic methods

Answer 2

You can delete half of the permutations on level/depth 1 as soon as N is odd. If N is even, delete half of the permutation on level/depth 2.

I hope I could help you.