Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. Pages: 1
#1 20110805 02:24:16
Cartesian Product...with a twist (need to remove duplicates)Hi folks, #2 20110805 03:21:04
Re: Cartesian Product...with a twist (need to remove duplicates)Hi pip; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #3 20110805 03:41:28
Re: Cartesian Product...with a twist (need to remove duplicates)
Cheers for the quick reply, #4 20110805 03:47:31
Re: Cartesian Product...with a twist (need to remove duplicates)Hi; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #5 20110805 05:20:24
Re: Cartesian Product...with a twist (need to remove duplicates)
Hi bobbym, Code:foreach(inputitem in inputset) sort the inputitem in ascending order end loop create a new set (outputset) while(inputset is not empty) remove first inputitem from inputset add it to outputset foreach(inputitem in inputset) compare the removeditem with inputitem if(the two items are equal) remove the matched item from inputset 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 brushup on my settheory knowledge is no bad thing. Last edited by pip (20110805 05:20:58) #6 20110805 05:31:25
Re: Cartesian Product...with a twist (need to remove duplicates)Okay, I will think on it. But it may be that the computationally expensive way is the only way, so hold on to what you have! What set commands does your language support? In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #7 20110805 16:51:19
Re: Cartesian Product...with a twist (need to remove duplicates)Yes  that's it  32 possible results in the resultset but there will only be 6 completely unique results if we take ordering out of the mix, i.e #8 20110805 17:46:16
Re: Cartesian Product...with a twist (need to remove duplicates)Hi; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #10 20110806 07:15:12
Re: Cartesian Product...with a twist (need to remove duplicates)Equijoin #11 20110806 07:24:56
Re: Cartesian Product...with a twist (need to remove duplicates)Hi René Descartes; Look at element 2 and element 3 {2,2,2,2,3} and {2,2,2,3,2} They are duplicates in structure of each but they are permutations of each other. They are not exactly the same. Notice the fact that the 2 is shifted over. Step 1) Sort each element of s, this can be expensive or not depending on your language. In mathematica it is not. Also, if I were you I would try to have each internal list ( { 2,2,2,3,2} )( element ) sorted on construction. Anyway, mathematica does it like this: Sort[#]& /@ s Notice the use of the lambda calculus ( pure function ) The output is: Call the above s1. Now notice all the duplicates are exact duplicates. We can now use the fact that each list of 5 is an element of s1. The set theoretic command Union is great for eliminating duplicates. We have the multiset { 1,2,2,3,3,4 } which we union with itself, the operation has removed all the duplicates. In mathematica Union[s1] or Union[s1, s1] This will yield: This is what you desire. In short what I have done is this. 1) Sort each list of lists, these elements can each be thought of as 1 x 5 vectors. The 5 elements in each of these must be sorted when they are created or after. Call this list of lists s1. 2) Union s1 with itself, this removes duplicates. At least in functional languages. What C# will do is unknown. You would have to experiment to see if your compiler supports commands that produce the desired effect. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #12 20110807 09:30:27
Re: Cartesian Product...with a twist (need to remove duplicates)Thanks for the help bobbym. Code:static void Main() { var sequences = new List<List<int>> { new List<int> { 2, 3 }, new List<int> { 2, 3 }, new List<int> { 2, 3 }, new List<int> { 2, 3 }, new List<int> { 2, 3 } }; var comparer = new UnorderedSequenceComparer(); var distinctOutput =CartesianProduct(sequences, true, comparer); distinctOutput.Dump(); } static IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences, bool removeDuplicates, IEqualityComparer<IEnumerable<T>> sequenceComparer) { IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; var resultsSet = sequences.Aggregate(emptyProduct, (accumulator, sequence) => from accseq in accumulator from item in sequence select accseq.Concat(new[] { item })); if (removeDuplicates) return resultsSet.Distinct(sequenceComparer); else return resultsSet; } class UnorderedSequenceComparer : IEqualityComparer<IEnumerable<int>> { public bool Equals(IEnumerable<int> x, IEnumerable<int> y) { return x.OrderBy(i => i).SequenceEqual(y.OrderBy(i => i)); } public int GetHashCode(IEnumerable<int> obj) { return obj.Sum(i => i * i); } } Last edited by pip (20110807 09:32:30) #13 20110807 10:39:18
Re: Cartesian Product...with a twist (need to remove duplicates)H pip; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. Pages: 1
