My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 4th, 2011, 08:46 AM   #1
pip
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
pip is offline  
 
August 4th, 2011, 10:11 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
August 4th, 2011, 11:28 AM   #3
pip
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
pip is offline  
August 4th, 2011, 12:08 PM   #4
Global Moderator
 
The Chaz's Avatar
 
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!

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

  My Math Forum > College Math Forum > Applied Math

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 exeriment-need help finding "statistic" and "result" katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM
terms "non-increasing" or "non-decreasing" Ujjwal Number Theory 2 September 29th, 2008 07:06 AM





Copyright © 2019 My Math Forum. All rights reserved.