My Math Forum Cartesian Product...with a twist (remove "duplicates")

 Applied Math Applied Math Forum

 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 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
 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:
 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

 August 4th, 2011, 12:08 PM #4 Global Moderator     Joined: Nov 2009 From: Northwest Arkansas Posts: 2,767 Thanks: 5 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??),

 Tags cartesian, duplicates, productwith, remove, twist

### remove duplicates cartesian product

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post johnmath Math Books 6 January 27th, 2013 03:13 PM SedaKhold Calculus 0 February 13th, 2012 11:45 AM The Chaz Calculus 1 August 5th, 2011 09:03 PM katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM Ujjwal Number Theory 2 September 29th, 2008 07:06 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top