Dear all,
I have a long list of ordered factor level combinations A = {a1...an}, .... E = {e1...ek} which is non-exhaustive (e.g. not full-factorial) e.g.:
A B C D E
...
a1 b1 c1 d1 e1
a1 b1 c1 d1 e2
a2 b1 c1 d1 e1
...
Now I want to merge all entries which differ only by 1 factor at a time (e.g. E) into a pattern. In the example this should lead to
A B C D E
...
a1 b1 c1 d1 {e1,e2}
a2 b1 c1 d1 e1
...
Now my problem is to do that for all factors. In the example keeping A fixed, one can not simple merge the two entries to:
{a1,a2} b1 c1 d1 {e1,e2}
since this implies that also the combination
a2 b1 c1 d1 e2
was part of the original factor combinations - which it wasn't.
My first try was to only merge entries where all levels of the fixed factor were present and replace the according pattern with a wildcard,e.g. for E = {e1,e2,e3}
a3 b2 c4 e1
a3 b2 c4 e2
a3 b2 c4 e3
becomes
a3 b2 c4 *
Since in this case I know that E is not important for the combination of factors A to C. But this approach is unsatisfactory since it leaves a lot of entries unmerged (e.g. the example in the beginning will not be merged).
So, could someone point me to a direction where a solution to this problem might be found (e.g. graph/subset reduction, also thought of bioinformatic methods treating the factor combinations somehow as strings).
Any help would be very welcome!
Greetings, David
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
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Bioinformatics