Algorithm for multi combination

[Guest]

I have a collection of groups: Group1, Group2, ...
In each group there are a number of items.
I need to produce a list of all possible item combinations where one item is
picked from each group.

What would be the best algorithm for this? Recursive or iterative?
What would be the best datatypes to use?
Readability is more important than speed.

Example:
Group1: Item1, Item2
Group2: Item3, Item4, Item5
Group3: Item6, Item7

This would produce the following list:
Item1, Item3, Item6
Item1, Item3, Item7
Item1, Item4, Item6
Item1, Item4, Item7
Item1, Item5, Item6
Item1, Item5, Item7
Item2, Item3, Item6
Item2, Item3, Item7
Item2, Item4, Item6
Item2, Item4, Item7
Item2, Item5, Item6
Item2, Item5, Item7

 

[RobinS]

Wouldn't 3 nested loops take care of it?

For each grp1 As Group1Item in Group1
For each grp2 as Group2Item in Group2
For each grp3 as Group3Item in Group3
Console.WriteLine (grp1 & ", " & grp2 & ", " & grp3)
Next
Next
Next

I'd probably use Generics to do this.

Robin S.

 

[Kevin Yu [MSFT]]

Hi,

In my opinion, a nested loop will do this for you. A recursive loop will be
more complex in this case.

Kevin Yu
Microsoft Online Community Support

==================================================
Get notification to my posts through email? Please refer to
http://msdn.microsoft.com/subscriptions/managednewsgroups/default.aspx#notif
ications.
Note: The MSDN Managed Newsgroup support offering is for non-urgent issues
where an initial response from the community or a Microsoft Support
Engineer within 1 business day is acceptable. Please note that each follow
up response may take approximately 2 business days as the support
professional working with you may need further investigation to reach the
most efficient resolution. The offering is not appropriate for situations
that require urgent, real-time or phone-based interactions or complex
project analysis and dump analysis issues. Issues of this nature are best
handled working with a dedicated Microsoft Support Engineer by contacting
Microsoft Customer Support Services (CSS) at
http://msdn.microsoft.com/subscriptions/support/default.aspx.
==================================================

(This posting is provided "AS IS", with no warranties, and confers no
rights.)

 

[Guest]

The number of groups is dynamic.

 

[RobinS]

If the groups are in generic lists, it's okay that the number of them be
dynamic.
The For Each will work. A Generic List is a collection of objects that are
the
same type.

Dim Group1 as New List(Of Integer)
Group1.Add(1)
Group1.Add(2)
Group1.Add(3)
Dim Group2 as New List(Of Integer)
Group2.Add(4)
Group2.Add(5)
Group2.Add(6)
Dim Group3 As New List(Of Integer)
Group3.Add(7)
Group3.Add(8)
Group3.Add(9)

For Each gr1 As Integer In Group1
For Each gr2 as Integer In Group2
For Each gr3 as Integer in Group 3
Console.WriteLine(gr1.ToString & ", " & _
gr2.ToString & ", " & gr3.ToString)
Next
Next
Next

should give you this:
1, 4, 7
1, 4, 8
1, 4, 9
1, 5, 7
1, 5, 8
1, 5, 9
1, 6, 7
1, 6, 8
1, 6, 9
2, 4, 7
2, 4, 8
2, 4, 9
(etc.)

For generic lists, you can use any type you want. I've used
Integer. You can have generic lists of objects, like
Dim Group1 as List(Of Product)

Robin S.

 

[Guest]

In your examples there is a dynamic number of items in each group. Fine. That
has never been the problem.
My point is that the number of GROUPS is dynamic.
I don't know how many groups I will have, there can be 3 like in my first
example but it can also be 4, 5 ......

 

[RobinS]

Yikes. I think you could use some kind of recursion, with the groups
being in an arraylist. I'm going to think about it for a bit, and I'll
see if I can come up with an algorithm for you.

Robin S.

 

[RobinS]

If you're doing VB, you might want to post this in
microsoft.public.dotnet.languages.vb.

If you're doing C#, you might want to post this in
microsoft.public.dotnet.languages.csharp.

Someone else might have a solution to this already.
If I come up with something, I'll post it. I'm busy
and am going to have to think about it a little, and
write some test code.

Robin S.
--------------------------------------

 

[Oliver Sturm]

Hello Jakob,

Just a bit of a recursion...

class Program {
static void Main(string[] args) {
List<string> group1 = new List<string>(new string[] { "Item 1", "Item
2" });
List<string> group2 = new List<string>(new string[] { "Item 3", "Item
4", "Item 5" });
List<string> group3 = new List<string>(new string[] { "Item 6", "Item
7" });

List<List<string>> groups = new List<List<string>>(
new List<string>[] { group1, group2, group3 });

Iterate(groups, 0, "");
Console.ReadLine( );
}

static void Iterate(List<List<string>> groups, int currentGroup, string
completeString) {
List<string> group = groups[currentGroup];
foreach (string element in group) {
if (currentGroup < groups.Count - 1)
Iterate(groups, currentGroup + 1, AppendToString(completeString,
element));
else
Console.WriteLine(AppendToString(completeString, element));
}
}

static string AppendToString(string stringSoFar, string newElement) {
if (!(string.IsNullOrEmpty(stringSoFar)))
stringSoFar += ", ";
return stringSoFar + newElement;
}
}


Oliver Sturm

 

[Rad [Visual C# MVP]]

I have a collection of groups: Group1, Group2, ...
In each group there are a number of items.
I need to produce a list of all possible item combinations where one item is
picked from each group.

What would be the best algorithm for this? Recursive or iterative?
What would be the best datatypes to use?
Readability is more important than speed.

If you don't know the number of items or the number of groups, I would say
store the items in a collection of some sort, and then the groups would be
in a collection of collections.

Yikes!

So for instance you could store your items in an array and then those
arrays in an array of arrays, if you get my drift.

That way you can loop through each element in an array and then each array
in the containing array

Positively makes your head spin, doesn't it?

 

[Rad [Visual C# MVP]]

If you don't know the number of items or the number of groups, I would say
store the items in a collection of some sort, and then the groups would be
in a collection of collections.

Yikes!

So for instance you could store your items in an array and then those
arrays in an array of arrays, if you get my drift.

That way you can loop through each element in an array and then each array
in the containing array

Positively makes your head spin, doesn't it?

Other valid collections would be array lists and, if you know the types,
generic lists