My Math Forum (http://mymathforum.com/math-forums.php)
-   Applied Math (http://mymathforum.com/applied-math/)
-   -   Cartesian Product...with a twist (remove "duplicates") (http://mymathforum.com/applied-math/20401-cartesian-product-twist-remove-duplicates.html)

 pip August 4th, 2011 08:46 AM

Cartesian Product...with a twist (remove "duplicates")

Hi folks,

I hope someone is able to help me with what is, at least to me, quite a tricky algorithm.

===========
The Problem
===========

I have a List (of unknown size) of Lists (1<=size<=2) that I need to permute (or possibly combine.....forgive me, I am a programmer, not a mathematician). Here is an example of what I am looking at:-

ListOfLists = { {1}, {2,3}, {2,3}, {4}, {2,3} }

To give this some context, the ListOfLists is actually a list of hotel rooms. Each hotel room has a particular Occupancy (number of adults and children) and this Occupancy maps to a particular OccupancyID (which is what is contained inside each inner list. The only problem here is that a room with 2 adults maps to 2 different occupancyID's (2=twin room, 3=double room). So, what I am saying in the example ListOfLists above is that I am looking for 5 rooms, 3 of which have 2 possible occupancyID's (2 or 3), the other 2 have clearly-defined occupancyID...

So, there are 2 stages to what I need to do:-

(1). I need to combine the inner lists in such a way that any combination has exactly ONE item from each, that is, the possible combinations in the result set here would be:-

1,2,2,4,2
1,2,2,4,3
1,2,3,4,2
1,2,3,4,3
1,3,2,4,2
1,3,2,4,3
1,3,3,4,2
1,3,3,4,3

I have actually managed to find a solution to this stage using some of the excellent tutorials and blogs around the net (see below) - the Cartesian Product, as the title of this question might suggest.....now, here comes the twist which I can't figure out.

(2). I then need to filter out any duplicate results from this Cartesian Product. A "duplicate" in this case constitutes any line in the result set with the same frequency of occurrence as another line, that is,

1,2,2,4,3 is the "same" as 1,3,2,4,2

because each item within the first list occurs the same number of times in the second list (1 occurs once in each list, 2 appears twice in each list, ....)

The final result set should therefore look like this...

1,2,2,4,2
1,2,2,4,3
--
1,2,3,4,3
--
--
--
1,3,3,4,3

OR, more simply
1,2,2,4,2
1,2,2,4,3
1,2,3,4,3
1,3,3,4,3

To any mathematically-minded folks out there, I do appreciate that what I am asking for might actually just be a straight-forward combination or permutation, but I have not been able to find an answer to this particular situation and don't have enough knowledge of set theory. I hope someone is able to help.

Some resources used
http://blogs.msdn.com/b/ericlippert/arc ... -linq.aspx
http://stackoverflow.com/questions/7106 ... arraylists
http://msdn.microsoft.com/en-us/vcsharp/aa336800.aspx

 CRGreathouse August 4th, 2011 10:11 AM

Re: Cartesian Product...with a twist (remove "duplicates")

What you're making is called a multiset, which is the most common name among programmers as well as mathematicians (some programmers prefer "bag"). It's like a set in that it disregards order but retains multiple elements.

The usual way of handling it in cases like this (not too many repetitions for any given element) is to sort each list then sort the list of lists, removing adjacent duplicates.

 pip August 4th, 2011 11:28 AM

Re: Cartesian Product...with a twist (remove "duplicates")

Quote:
 Originally Posted by CRGreathouse What you're making is called a multiset, which is the most common name among programmers as well as mathematicians (some programmers prefer "bag"). It's like a set in that it disregards order but retains multiple elements. The usual way of handling it in cases like this (not too many repetitions for any given element) is to sort each list then sort the list of lists, removing adjacent duplicates.
Cheers for that - this has been bending my brain this afternoon - I have actually managed to solve the problem, but it is a real brute-force way of doing things that is more computationally-intensive than i really want. There will be some really neat LINQ way of doing this.....I'm probably better posting on a LINQ forum actually, but I appreciate the quick reply mate.

Cheers,

pip :)

 The Chaz August 4th, 2011 12:08 PM

Re: Cartesian Product...with a twist (remove "duplicates")

You're probably better off on a forum that CRG frequents!

[/brown-nosing] (which reminds me, where is Neo??),

 All times are GMT -8. The time now is 08:52 AM.