[GAP Forum] introduction to backtrack algorithm with ordered partitions

[Christopher Jefferson]

Just to extend on Leonard's comments,

The paper New refiners for permutation group search [Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker] gives a brief overview of partitions, while extending it. "Permutation group algorithms based on directed graphs" gives a new, more general framework, which uses directed graphs.

If you are happy looking at code, https://www.github.com/gap-packages/ferret gives a (reasonably) clean reimplementation in C++, while https://github.com/peal/backtrackkit gives a simple, very low-performance implementation (it aims to produce the "right partitions", but does so in a very simple but inefficient way).

I also recently gave a brief overview on the topic at the Newtown Institute: https://www.newton.ac.uk/seminar/20200131113012201 , which you may (or may not) find helpful. I'm also happy to answer any questions, particularly about Leon's paper which myself and my co-authors are fairly sure we understand.

Chris

-----Original Message-----
From: Leonard Soicher <l.h.soicher at qmul.ac.uk> 
Sent: Thursday, September 17, 2020 1:20 PM
To: Bill Allombert <Bill.Allombert at math.u-bordeaux.fr>; GAP Forum <forum at gap-system.org>
Subject: Re: [GAP Forum] introduction to backtrack algorithm with ordered partitions

Dear Bill, Dear Forum,

You might like to look at Chapter 9 (Backtrack Methods) in A. Seress, "Permutation Group Algorithms", Cambridge University Press, 2003.

For recent research in this area, see:

C. Jefferson, M. Pfeiffer, R. Waldecker, W.A. Wilson, Permutation group algorithms based on directed graphs,
arXiv:1911.04783 [math.GR], 2019.

Best,
Leonard


________________________________________
From: Bill Allombert <Bill.Allombert at math.u-bordeaux.fr>
Sent: 14 September 2020 11:49
To: GAP Forum
Subject: [GAP Forum] introduction to backtrack algorithm with ordered   partitions

Dear Forum,

I am interested in an introduction to the concept of backtrack algorithm with ordered partitions.
(which is mentionned in the last section of the GAP manual)

So far I have found Leon paper
Permutation Group Algorithms Based on Partitions, I:
              Theory and Algorithms

Is there something else I missed ?

Cheers,
Bill

_______________________________________________
Forum mailing list
Forum at gap-system.org
https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmail.gap-system.org%2Fmailman%2Flistinfo%2Fforum&amp;data=02%7C01%7C%7Cc6707e89319e4124be1208d8589bfc30%7C569df091b01340e386eebd9cb9e25814%7C0%7C1%7C637356774264126640&amp;sdata=e8LKw5CfuD5%2Bf6RKvIaCl1tf29januOsvfbXq8MjEMs%3D&amp;reserved=0

_______________________________________________
Forum mailing list
Forum at gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum