Dear David,

I am not experienced in pattern problems, but could an increase in the dimensionality of the object used to store merges be of some help?

In your example {a1,a2} b1 c1 d1 {e1,e2}

if you used a matrix and wrote it instead as

 {{a1},{a2}} b1 c1 d1 {{e1,e2}}

(what I am trying to write (not sure about the Matrix notation) is one first matrix on the left of just one column with two rows with elements a1 and a2 and one second matrix on the right with just one row with two columns with elements e1 and e2)

You can build your matrix so that valid combinations are the ones where the elements are in the same row or the same column (I did so)

So valid combinations in this case would be:

- a1 with e1 or e2  (same row)

or

-a2 with  e1 (same column)

and nothing else.

Maybe this is what you want from what I understood.

This is just an idea of something to try, but maybe it works if you keep adding dimensions...

Good luck

Kind regards

Fernando Pimentel 

I'm afraid you haven't fully specified the problem.  I understand you're looking for an algorithm whose input is a set of fixed-length tuples (5-tuples in your examples) and output is a set of patterns that cover the input set exactly, that is, every input matches some pattern and no pattern matches a tuple that's not in the input.  However, you haven't stated what other conditions must be met nor how to compare the goodness of two potential candidates.  For instance, are all of the following solutions to your first example acceptable?

1:

a1 b1 c1 d1 {e1, e2}

{a1, a2) b1 c1 d1 e1

2:

a1 b1 c1 d1 e2

{a1, a2} b1 c1 d1 e1

3:

a1 b1 c1 d1 {e1, e2}

a2 b1 c1 d1 e1

If you want to exclude overlapping patterns, suggestion 1 has to be rejected.  If you want all your patterns to be maximal independently of any others, suggestions 2 and 3 must be rejected.  Maybe you have some other requirement in mind.

Anyway, chances are that in a more complicated example, you still have several acceptable choices.  Do you have some criteria for choosing the best one?  For example, you might want to minimize the number of patterns, and choose among the solutions with the same number of patterns by maximizing the number of wildcards.

Finally, it might help if you give a rough estimate of the actual size of the problem you want to solve.  There may be an algorithm that works fine if the input  contains at most a few thousand elements but won't finish in your lifetime if there are millions of them.  The same applies to the sizes of the sets A, B, C, D, E.  (Are there actually 5 of them?)

I don't nearly always have the time to participate in ResearchGate, but I hope someone else will be able to help you further.

Hello David et alii,

Seen as a theoretical formula : " How to reduce a list of factors ..." could sound as thinking to build general types of computing as pattern processes in a nearly neuronal way. But you introduce the question in a more analytical manner when we admit that " reducing a list " could not only be the economical part of the work but also  finding a processing solution.

Practically I remember about LISP a language thougnt for manipulating lists you could be interrested in. Could a neural network process achieve the task as you wish?

You can also ask your question to people interrested in Set Operads related to combinatorics for example a book : Set Operads in Combinatorics and Computer Sciences. By Miguel A. Mendez. Springer briefs in mathematics. Springer.

But it seems to me aslo true that your question as a specific practical and direct problem could largely progress in your mind if better defined. and more deeply explanable for any further help.

Best wishes.

Jean-Yves Tallet

Dear all!

Thanks for your comments! I see that I have not fully specified the problem.

In total I have 5 factors (||A||=8, ||B||=4, ||C||=2, ||D||=7, ||E||=3; summing to 1344 unique 5-tuples, e.g. factor combinations). Each tuple is assigned to between 1 to around 100 classes of an outcome variable G (||G||~=384) based on a real valued performance score. Each class assigned to a tuple is considered similar, but may slightly differ in their score. Since this "similarity" is a soft measure, the exact number of classes per factor combination is not known in advance (median 10 classes/tuple). Similarly each class is assigned to 0 to 228 tuples (median 26 tuples/class). Although some of the classes are not used at all, there are still 335 valid classes.

As stated in the beginning, my problem is to reduce the list of tuples per class to the minimum amount. This is, as Taneli remarked, the constraint of minimizing the total number of patterns by maximizing the number of wildcards (e.g. by finding the most general patterns for each class). Ultimately, each class should contain as few "patterns" as possible. Since I want to generate a decision tree in the end, overlapping patterns are not preferred. Patterns with the same amount of wildcards can be differentiated by their performance score if necessary.

As the number of factor combinations per class is rather small, it seems that the runtime constraint on the "reduction" step is not very tight.

As Jean-Yves said, I am also interested in a practical solution (which I will implementing in Matlab R15b) but since I could not come up with even a good theoretical background for the problem (despite that there must be "some" solution" in set theory), understanding the problem from some other viewpoint is my first concern.

The concept of operads sounds interesting - I will have a look at it!

Thanks again for your help! Greetings, David