Thank you for the encouragement. I am pleased that my concept of how to do this is not without merit but I am still not convinced that it is the optimal solution.

The method outlined in my last post is certainly not the most efficient way to creating all possible subsets in lexical order. The potential benefit of the method arises when incompatible pairs are removed. For instance if 1 is incompatible with 0.

Both extended_sets[] and last_added_elements[] are smaller than when the full set is traversed because the 0,1 pair was tested but not created. For the next branch level.Code:// creation of branch level 1 (pairs) 0,1 // fails because 1 is not compatible with 0 0,2 0,3 0,4 // 4 total checks, 3 extended sets created extended_sets[] 0,2 0,3 0,4 last_added_elements[] {2,3,4}

Code:// creation of branch level 2 (triples) // no subsets starting with 0,1 need are examined 0,2 add 2 // fails 2 is already a member of 0,2 0,2 add 3 0,2 add 4 0,3 add 2 // fails 2 is smaller than 3 0,3 add 3 // fails 3 is already a member of 0,3 0,3 add 4 0,4 add 2 // fails 2 is smaller than 4 0,4 add 3 // fails 3 is smaller than 4 0,4 add 4 // fails 4 is already a member of 0,4 // 9 total checks, 3 extended sets created extended_sets[] 0,2,3 0,2,4 0,3,4 last_added_elements[] {3,4}Code:// creation of branch level 3 (quads) 0,2,3 add 3 // fails 3 is already a member of 0,2,3 0,2,3 add 4 0,2,4 add 3 // fails 3 is smaller than 4 0,2,4 add 4 // fails 4 is already a member of 0,2,4 0,3,4 add 3 // fails 3 is smaller than 4 0,3,4 add 4 // fails 4 is already a member of 0,2,4 // 6 total checks, 1 extended set created extended_sets[] 0,2,3,4 last_added_elements[] {4}Code:// creation of branch level 4 (quints) 0,2,3,4 add 4 // fails 4 is already a member of 0,2,3,4 // 1 total check, 0 extended sets created extended_sets[] last_added_elements[] {}

The algorithm quits here because last_added_elements[] is empty so no larger subsets can be created. The final list of legal substes when 0 and 1 are incompatible is,

Code:0 0,2 0,3 0,4 0,2,3 0,2,4 0,3,4 0,2,3,4

Only 7 of the theoretical 16 subsets are created. I believe that a brief analysis of the example above shows that problems still remain with this method. For small sets such as this with only one incompatible pair, you can see that 20 checks are required. There are only 16 theoretical pairs, so in this case it would have been faster to create all the pairs and check them. For problems like N=40 with many incompatible pairs, you see that only 3,708,590 of the theoretical 1,099,511,627,776 combinations need to be examined to produce the surviving 178,211 legal subsets. This works much better for very large problems than for small ones.

There are many checks being made that are probably not necessary. For instance, after the pairs are created, all the checks fail when trying to extend the last set in root_elements[]. The pair 0,4 is never extended, the triple 0,3,4 is never extended, etc. Also, the first element in elements_to_add[] is never added to any root_elements[] set. In all cases, it is already in the set or smaller then the last number in the set.

I thought I should be able to come up with a more clever looping scheme here that would address that. this can be done when all subsets are created because the creation pattern is known in advance. There is a problem when pairs are removed because of incompatibility in that there is no way to know how many elements will be in the elements_to_add[] list for the next iteration.

This algorithm could be additionally enhanced if the number of checks could be reduced but I couldn't see how to do that right away so I just wrote the code in a way I knew would work. I have attached the code which was just built with,

The code is set up to process the N=40 problem 10 times and on this system, that takes about 3.5 seconds. The output is minimal. A full list of the subsets found can be printed by changing the print bool to true, but that makes the runtime substantially longer.Code:c++ -c -Wall -O2 APS_3.cpp; c++ -o APS_3.exe APS_3.o

I am interested in improving that algorithm, but also at looking at others that have been mentioned that process the same problem. It would still be nice to have it faster, but I also don't think it is very safe the way it is written.

Suggestions are very much appreciated,

LMHmedchem