
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 4th, 2011, 08:46 AM  #1 
Newbie Joined: Aug 2011 Posts: 2 Thanks: 0  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 clearlydefined 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 mathematicallyminded folks out there, I do appreciate that what I am asking for might actually just be a straightforward 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/enus/vcsharp/aa336800.aspx 
August 4th, 2011, 10:11 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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. 
August 4th, 2011, 11:28 AM  #3  
Newbie Joined: Aug 2011 Posts: 2 Thanks: 0  Re: Cartesian Product...with a twist (remove "duplicates") Quote:
Cheers, pip  
August 4th, 2011, 12:08 PM  #4 
Global Moderator Joined: Nov 2009 From: Northwest Arkansas Posts: 2,766 Thanks: 4  Re: Cartesian Product...with a twist (remove "duplicates")
You're probably better off on a forum that CRG frequents! [/brownnosing] (which reminds me, where is Neo??), 

Tags 
cartesian, duplicates, productwith, remove, twist 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Can anyone help me finding this book "Evariste Galois "Toti"  johnmath  Math Books  6  January 27th, 2013 03:13 PM 
A "simple" application of dirac delta "shift theorem"...help  SedaKhold  Calculus  0  February 13th, 2012 11:45 AM 
"separate and integrate" or "Orangutang method"  The Chaz  Calculus  1  August 5th, 2011 09:03 PM 
sample exerimentneed help finding "statistic" and "result"  katie0127  Advanced Statistics  0  December 3rd, 2008 01:54 PM 
terms "nonincreasing" or "nondecreasing"  Ujjwal  Number Theory  2  September 29th, 2008 07:06 AM 