Langford Sequence - Utilize symmetry / Remove symmetry

user_5026265 0
Viewed 182

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

enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description here

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

graph-algorithm algorithm c++
2 Answers

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

user_116412780

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.

user_136426660
Related