bobbym wrote:

Hi pip;

Welcome to the forum!

If you were asking for the number of something then that is a math problem but it seems to me that you are asking for how to prune the list further. This is a programming problem don't you think.

Cheers for the quick reply,


I see your point, and I have in fact managed to do this pruning programatically but my current solution is really a brute-force approach with many iterations and I was hoping there would be some set-operation that I am unaware of that could help do this more elegantly...us programmers are all about finding the elegant solution whenever we can.

bobbym wrote:

Hi;

You have a partial example of 5 elements. Can you provide a full example? I mean all the sets and each steps output. From beginning to end.
If that is too large how about sets with 4 elements. What I need is one problem completely solved with nothing left out.

It has been my experience that explanations of a process using words only is inaccurate.

Hi bobbym,

The example I give is actually complete - I do apologise though, as I just re-read my original post and I should state that the maximum number of lists within the ListOfLists is 5.

As stated in the original post though the minimum size of each inner list is 1, with a maximum size of 2. That is, the worst-case scenario from a combination point of view would be {{2,3}, {2,3}, {2,3}, {2,3}, {2,3}}, i.e. a list containing inner lists of the maximum size, and in this case there would obviously be 32 results in the Cartesian Product result-set, but the pruned result-set that I am trying to get at would just be:-

2,2,2,2,2
2,2,2,2,3  <-- all other results with four 2's and one 3 (in any order) are suppressed
2,2,2,3,3  <-- all other results with three 2's and two 3's are suppressed, etc
2,2,3,3,3
2,3,3,3,3
3,3,3,3,3

What i can't know until run-time of the program, is how many inner lists there will be, and how many of them will contain this choice of a 2 or 3, and that's why I (think) I need to compute the Cartesian product, then prune duplicates.

I hope I have explained that OK - the program I am working on has a seemingly infinite number of combinatorial quirks but this one has me stumped....technically, I have resolved the issue but I am essentially having to take each result in the cartesian product result-set, order it (in ascending order) for comparison, then take the first result from the result-set and compare it to all the others (that involves checking for a complete intersection of the two), add the current result being compared into a new result-set, delete the duplicates from the original result-set, then iterate from the start again, .....it works, it's just computationally intensive. I've tried to quickly pseudo-code this below....

foreach(input-item in input-set)
    sort the input-item in ascending order
end loop

create a new set (output-set)

while(input-set is not empty)
    remove first input-item from input-set
    add it to output-set
    
    foreach(input-item in input-set)
        compare the removed-item with input-item
        if(the two items are equal)
            remove the matched item from input-set

As I say, I have a working solution, but that pain in the math part of my brain just "knows" there is a more efficient way of doing this. If there is no mathematical way you know of, then no problem, I just wanted to satisfy my own curiosity, and a brush-up on my set-theory knowledge is no bad thing.

Last edited by pip (2011-08-05 05:20:58)

Yes - that's it - 32 possible results in the result-set but there will only be 6 completely unique results if we take ordering out of the mix, i.e

2,2,2,2,2
2,2,2,2,3
2,2,2,3,3
2,2,3,3,3
2,3,3,3,3
3,3,3,3,3

The language I am using is C# under .NET3.5 and so I have access to all the set commands of LINQ, i.e. SELECT, WHERE, INTERSECT, UNION.....pretty much any set operation that is needed would be supported. I have asked this same question on a dedicated LINQ forum and quite a few programmatical answers have been posted - but I tend to be the sort of person who just HAS to know what is going on under the hood, so if you know what set operations can be used to resolve this I would still love to know.

Cheers,

Phil

bobbym,

I been reading more into linq today and it really does seem that it can do any set operations.

I'm intrigued by the whole two-commands-to-do-the-whole-thing statement - ok, what u got?

Cheers,

pip

Hi René Descartes;

Welcome to the forum! Please do not do that. Terse answers like that cause much confusion. If you have an idea that can help pip please take the time to explain it in detail.


Hi pip;

Yes there is a two step method that uses a set command but it may be of very little use to you. Lisp is unusually rich in list manipulating commands. Mathematica which is a functional language like lisp is what I use now. Procedural languages may not be able to easily duplicate this idea.

The list of lists that we are working on is:

H pip;

Glad you found a solution! Good luck with the project.