C# set algorithm

[AstroDrabb]

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

 

[Jon Skeet [C# MVP]]

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".

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

 

[AstroDrabb]

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

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

 

[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

 

[Jon Skeet [C# MVP]]

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));
}
}
}

 

[AstroDrabb]

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.

 

[Jon Skeet [C# MVP]]

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

 

[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?

Thanks for all the help,

AstroDrabb

 

[Jon Skeet [C# MVP]]

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.)

 

[Ben Voigt [C++ MVP]]

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;
}

 

[AstroDrabb]

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.

 

[jake]

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.

 

[AstroDrabb]

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

 

[Arne Vajhøj]

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".

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 + 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); });
}
}
}

 

[Michael A. Covington]

Does anyone have any tips on creating an efficient set algorithm?
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.