 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
.NET Forum / Languages / C# / March 2008C# set algorithm
Does anyone have any tips on creating an efficient set algorithm? I have the following set {a, b, c, d, e}. I need to combine them in all possible ways: a ab ac ad ae abc b bc bd be ... ace ... Get the picture? Thanks for any help. Note, the combinations need to be unique. For instance, I don't need "ab" in addition to "ba". Thanks for any help, AstroDrabb > Does anyone have any tips on creating an efficient set algorithm? > [quoted text clipped - 19 lines] > Thanks for any help. Note, the combinations need to be unique. For > instance, I don't need "ab" in addition to "ba". How many elements will you have within the original set? If it's 64 or less, it's very easy - use a long, and one bit per entry in the original set. Count from 0 to (2^n)-1 where n is the number of elements, and write out every element whose bit is on :)  SignatureJon Skeet - <skeet@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet World class .NET training in the UK: http://iterativetraining.co.uk > > Does anyone have any tips on creating an efficient set algorithm? > > [quoted text clipped - 24 lines] > original set. Count from 0 to (2^n)-1 where n is the number of > elements, and write out every element whose bit is on :) There are five items that represent products. For example {cod, flounder, crab, shrimp, lobster} I have to come up all possible combinations for the produts to insert into a table. When I insert the product combinations I combine the price of each combination and store that as well. So the records would look something like: "Cod, 10.49" "Cod/Flounder, 22.55" ... "Flounder/Lobster, 75.49" ... etc The reason is there are times we get payments with just a price and no products ordered sheet. Yeah, that is my next big thing to fix. However, for now, my boss wanst to be able to do a query on a price. I would look up that total and display the item or items that combine to come to that total. One other thing I will do when I generate the static price table is check for price collisions. If there are any, I will notify my boss and a products price will be raised or lowered by a penny so that all price combinations are unique. I need to do this with many different product sets, so I have been trying to think up a way to do a nice algorithm that I just plug in the product set and get all possible combinations from it. I know this is a broken system. However, for now I just need to get the hack up so that business will flow better, thus giving me time to write a _new_ system. Thanks, AstroDrabb <snip> One thing I don't think I mentiond is that duplicate based on PRICE need to be removed. For example: cod/shrimp, 55.50 is the same as shrimp/cod 55.50 Thanks, AstroDrabb > There are five items that represent products. For example > > {cod, flounder, crab, shrimp, lobster} > > I have to come up all possible combinations for the produts to insert into > a table. Okay, we can do that. We can do it reasonably amusingly using iterator blocks. Have a look at this :) using System; using System.Collections.Generic; using System.Linq; class Test { static IEnumerable<IEnumerable<T>> FindCombinations<T>(T[] items) { if (items.Length > 64) { throw new ArgumentOutOfRangeException ("Can't deal with more than 64 items"); } for (long combination = 0; combination < (1L << items.Length); combination++) { List<T> list = new List<T>(); for (int candidate=0; candidate < items.Length; candidate++) { if ((combination & (1L << candidate)) != 0) { list.Add(items[candidate]); } } yield return list; } } static void Main() { string[] products = { "cod", "flounder", "crab", "shrimp", "lobster"}; foreach (var combination in FindCombinations(products)) { string[] items = combination.ToArray(); Console.WriteLine(string.Join("/", items)); } } } SignatureJon Skeet - <skeet@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet World class .NET training in the UK: http://iterativetraining.co.uk > > There are five items that represent products. For example > > [quoted text clipped - 5 lines] > Okay, we can do that. We can do it reasonably amusingly using iterator > blocks. Have a look at this :) <snip> Thanks Jon. I will play around with it. I forgot to mention that I am using .Net 2.0. IEnumerable<string> doesn't have a definition for ToArray(). I have been wanting to update to .Net 3.x though. Thanks again. > Thanks Jon. I will play around with it. I forgot to mention that I am > using .Net 2.0. IEnumerable<string> doesn't have a definition for ToArray(). > I have been wanting to update to .Net 3.x though. That's an extension method in .NET 3.5 - but there are other ways of stringing the things together. Apart from anything else, if you change the declaration to return IEnumerable<List<string>> then you can use .ToArray on List<T>. SignatureJon Skeet - <skeet@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet World class .NET training in the UK: http://iterativetraining.co.uk > > Thanks Jon. I will play around with it. I forgot to mention that I am > > using .Net 2.0. IEnumerable<string> doesn't have a definition for ToArray(). > > I have been wanting to update to .Net 3.x though. > > That's an extension method in .NET 3.5 - but there are other ways of > stringing the things together. I have 3.5 installed and the correct <compilers> entries, I am using VS 2008. Are there extenstions to 3.5 that I need to download and install? Thanks for all the help, AstroDrabb > > That's an extension method in .NET 3.5 - but there are other ways of > > stringing the things together. > > I have 3.5 installed and the correct <compilers> entries, I am using VS > 2008. Are there extenstions to 3.5 that I need to download and install? Nope. Does your application target .NET 3.5 though? (It's in the project properties.) SignatureJon Skeet - <skeet@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet World class .NET training in the UK: http://iterativetraining.co.uk > Nope. Does your application target .NET 3.5 though? (It's in the > project properties.) It does now. I originally used "Create web site", and there was no project option there. After creating a new project of type web site, I was able to target 3.5. Thanks. Just an after-thought. How would you handle an occasion where more than one combination total to the same price? I am actually curious (not being sarcastic). Thanks. > Just an after-thought. How would you handle an occasion where more > than one combination total to the same price? I am actually curious > (not being sarcastic). Thanks. As I generate the combinations, I put the price and the combo description, i.e. "Crab/Shrimp", "55.49" into a Dictionary. I just check that for a dupe before I insert any description/value combination into the DB. Once that is done, I can easily call a stored procedure to do all the inserts knowing that each value is unique. However, one objective is that I need to flag all collisions of price. So if I find a collision, where the prices are the same, yet the products are different, I insert a record into a "collision" table that shows what combo/price is causing the collision. For example: "Crab/Shrimp", 55.95 "Flounder/Shrimp", 55.95 The products that produce the price don't matter. What matters is that the final price _needs_ to be unique. This would cause a record to be entered in the Collisions table and also send out an email to the people that need to fix this. Management/finance people look at that table and make the cost changes to prevent the collision. I cannot change the price of products. Gee I wish I could ;-) The current system here (at a BIG company that won't be named) is pretty messed up. Yeah, I know, the system is total crap. Why can't grouped offerings have the same price? No big deal to me. However, it is a legacy problem from the dude who built most of their "systems" when they were starting out as a small subsidiary of a large corp. The biggest challenge for me is that I _cannot_ kill the band-aid system they have now. I have to add this feature and make sure it still works. After that, I get to finally create a new system that can handle some basic things like having product GROUPS with the same price. The previous guy didn't use any primary keys, or even any indexes, so the only way to _currently_ tell one product group from another is by the total price. Damn, if the guy just knew about a primary key... Jon provided some good stuff. After a few little tweaks, it is working well (thanks again Jon). Best, AstroDrabb >> There are five items that represent products. For example >> [quoted text clipped - 5 lines] > Okay, we can do that. We can do it reasonably amusingly using iterator > blocks. Have a look at this :) Too bad IEnumerator<T> doesn't implement Clone. Otherwise (and this would be easily modified to keep a total price alongside and return KeyValuePair<string, float>): IEnumerable<string> MakeAllCombinations<T>(IEnumerable<T> list) { using (IEnumerator<T> enum = list.GetEnumerator()) { while (enum.MoveNext()) { using (IEnumerator<T> enum2 = enum.Clone) { foreach (string combo in Descend(enum.Current.ToString(), enum2)) yield return combo; } } } } IEnumerable<string> Descend<T>(string prefix, IEnumerator<T> enum) { if (!enum.MoveNext()) { yield return prefix; return; } using (IEnumerator<T> enum2 = enum.Clone) { foreach (string combo in Descend(prefix, enum2)) yield return combo; } foreach (string combo in Descend(prefix + "/" + enum.Current.ToString(), enum)) yield return combo; } > Does anyone have any tips on creating an efficient set algorithm? > [quoted text clipped - 19 lines] > Thanks for any help. Note, the combinations need to be unique. For > instance, I don't need "ab" in addition to "ba". A recursive solution is attached below. Arne ============================================ using System; namespace E { public class Combiner { public delegate void Process(string comb); private static void Combine(string[] elms, int len, Process p, string comb, int start, int ix) { if(ix < len) { for(int i = start; i < elms.Length; i++) { Combine(elms, len, p, comb + elms[i], i + 1, ix + 1); } } else { p(comb); } } public static void Combine(string[] elms, int len, Process p) { Combine(elms, len, p, "", 0, 0); } public static void Combine(string[] elms, Process p) { for(int i = 1; i <= elms.Length; i++) { Combine(elms, i, p); } } public static void Main(string[] args) { Combiner.Combine(new string[] { "a", "b", "c", "d", "e" }, delegate(string comb) { Console.WriteLine(comb); }); } } } >> Does anyone have any tips on creating an efficient set algorithm? >> [quoted text clipped - 19 lines] >> Thanks for any help. Note, the combinations need to be unique. For >> instance, I don't need "ab" in addition to "ba". If you don't have to get them in exactly the order you specified: Count from 00001 to 11111 in binary. For each value, generate a set with members corresponding to 1's.
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.