With monday.comâ€™s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

Imagine having a number of factors (e.g. X,Y,Z) each having a set of values. As an example:

X1,X2,X3,X4 (factor 1 having 4 values)

Y1,Y2 (factor 2 having 2 values)

Z1,Z2,Z3 (factor 3 having 3 values)

This means we can have 4 x 2 x 3 = 24 different combinations. To give the first 6:

X1,Y1,Z1

X1,Y2,Z1

X1,Y1,Z2

X1,Y2,Z2

X1,Y1,Z3

X1,Y2,Z3 etc.etc.

Also Z1,X1,Y1 is regarded the same as X1,Y1,Z1 thus I am looking for unique combinations (I think that this is called 'no permutations')

Now, I tried to devise a generic algorithm that creates the full design set. So the number of Factors and Values is differntly every time. It seemed simple at first glance, but I can't get a grip on it. There's plenty of (statistical and scientific) background material on the subject, but I cannot find a practical example anywhere ...

Can anyone give me a start or a link to a good example?

X1,X2,X3,X4 (factor 1 having 4 values)

Y1,Y2 (factor 2 having 2 values)

Z1,Z2,Z3 (factor 3 having 3 values)

This means we can have 4 x 2 x 3 = 24 different combinations. To give the first 6:

X1,Y1,Z1

X1,Y2,Z1

X1,Y1,Z2

X1,Y2,Z2

X1,Y1,Z3

X1,Y2,Z3 etc.etc.

Also Z1,X1,Y1 is regarded the same as X1,Y1,Z1 thus I am looking for unique combinations (I think that this is called 'no permutations')

Now, I tried to devise a generic algorithm that creates the full design set. So the number of Factors and Values is differntly every time. It seemed simple at first glance, but I can't get a grip on it. There's plenty of (statistical and scientific) background material on the subject, but I cannot find a practical example anywhere ...

Can anyone give me a start or a link to a good example?

http://www.cs.sunysb.edu/~algorith/files/generating-permutations.shtml

http://www.merriampark.com/perm.htm

http://www2.toki.or.id/boohttp://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE151.HTMk/AlgDesignManual/BOOK/BOOK4/NODE151.HTM

http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20987823.html

Sunnycoder

So, just to udnerstand the problem better, why simple nested loops are not satisfactory to you?

for x=1 to 4

for y=1 to 2

for z=1 to 3

print x,y,z

endfor

endfor

endfor

Or supposing you have a variable number n of factors, and, say, cardinality[0..n-1] express how many values are possible for each factor, you can do the following.

Initialize a vector factor[] of size n to 0 (assuming you count values starting form 0 to cardinality[i]-1)

do

print array factor

i=0

do

factor[i]++

bool carry=(factor[i]==cardinal

if(carry) factor[i++]=0

loop while (carry and i<n)

loop while not carry

What language are you working in?

Idle_Mind

In your example the iterations indeed have a fixed number of factors wheraeas in my problem, both the number of factors and the number of values is variable. Thus thus it would require a construct with a variable number of loops and the loopcounter is variable too.

The latter will definitely cause "late binding" errors, as you cannot have a variable as a loop-counter e.g.

dim a, b as integer

a = Cint(textbox1.text) 'user input

for a = 1 to b

print a*b

next a

My language of preference is Visual Basic.Net, but any language (even plain English) will take me closer to a solution. Pseudo code would also be very usefull here!

In this case I just start taking the first value of each factor (the "Initialize a vector factor[] of size n to 0" part), then for each loop iteration, I move to the next value of the first factor. When I complete the first factor, I move to the enxt value of the second factor and start again with the first value for the first factor. And so on. What do you mean with "late binding errors" ?

Myabe my pseudo code is not clear enough?

As a side question: what do you want to print/generate? Just the product of all the values?

Dim Factors(,) As String = {{"I1", "I2", "I3"}, {"J1", "J2", "J3"}}

to see the difference in the output.

--------------------------

Private Sub Terms()

' This is just the driver for "ExpandTerms" which does the real work.

Dim Factors(,) As String = {{"I1", "I2"}, {"J1", "J2"}, {"K1", "K2"}, {"L1", "L2"}}

Dim term As String = New String("")

ExpandTerms(Factors, term, 0)

End Sub

Private Sub ExpandTerms(ByVal factors(,) As String, ByVal term As String, ByVal level As Integer)

If level <= factors.GetUpperBound(0) Then

For i As Integer = 0 To factors.GetUpperBound(1)

Dim nextTerm As String = term + "*" + factors(level, i)

ExpandTerms(factors, nextTerm, level + 1)

Next

Else

System.Console.WriteLine(t

End If

End Sub

Private Sub Terms()

Dim M As Integer = 3

Dim N As Integer = 2

Dim names() As String = {"I", "J", "K", "L"}

Dim Factors() As Array

Factors = Array.CreateInstance(GetTy

For i As Integer = 0 To M - 1 ' Change the implementation of this loop to create different length arrays of values

Factors(i) = Array.CreateInstance(GetTy

For j As Integer = 0 To N - 1

Factors(i)(j) = names(i) + j.ToString()

Next

Next

Dim term As String = New String("")

ExpandTerms(Factors, term, 0)

End Sub

Private Sub ExpandTerms(ByVal factors() As Array, ByVal term As String, ByVal level As Integer)

If level <= factors.GetUpperBound(0) Then

For i As Integer = 0 To factors(level).GetUpperBou

Dim nextTerm As String = term + "*" + factors(level)(i)

ExpandTerms(factors, nextTerm, level + 1)

Next

Else

System.Console.WriteLine(t

End If

End Sub

End Class

Im looking into your second example, and indeed do not fully understand your (pseudo) code yet. It's probably the syntax. Also I do not now the word Cardinality (I am Dutch) Can you elaborate a bit on it?

Late binding errors occur if you compile VB code with option strict on, which simply disallows late binding. The compiler wants to now the upper and lower bound values of the loop variable in advance.

for x = [lowbound] to [highbound]

next

but this can be solved by either setting option strict off, or using a do/loop construct which allows to use a comparison with variables

do

loop until [lowbound] = [highbound]

>>As a side question: what do you want to print/generate? Just the product of all the values?

Yes, the product. These are so called (factorial) experimental designs. E.g you have factor Temperature (40,60) and factor Pressure (100,110,120). Then you do experiments using the design and measure e.g. Rinse Effect.

Exp1= Temp 40, Pressure 100

Exp2= Temp 60, Pressure 100

Exp3= Temp 40, Pressure 110 etc. etc.

My experiment sets are however a bit bigger (hundreds of experiments) because having many factors with a few values (it is factorial!)

Your code looks promising. I need to adapt to your coding style (declarations mixed with statements ...)

2 comments for now:

-This uses recursion. Dont' say it is bad, but it may be risky giving the sizes of my collections (overflow)

-Late binding (another thing I try to avoid)

My first reaction is that this code will achieve what I want. Also instead of arrays, I could use ArrayLists which have a dynamic size by design

2 things:

a) cardinality means "number of elements". So if e.g. our second factor can have two values (say 40 and 100) then it has cardinality = 2

b) My algorithm, as I presented it, doesn't print e.g. "Exp2= Temp 60, Pressure 100" but only "Combination 2: 1, 0" meaning take the second value (index 1) for the first factor , and the first value (index 0) for the second factor. Of course you can change it to use these indices to take values from arrays and obtain output you want.

The difference between my algorithm and drichards is that mine is itertative while his is recursive. In general terms, recursive solutions are usually simpler while iterative are faster.

e.g.

5 * 3 * 2 * 4 would go to: 2 * 3 * 4 * 5

Do a sort on all the factors

e.g.

1 * 3 * 5

2 * 3 * 4 * 5

2 * 3 * 4 * 5

2 * 3 * 4 * 5

4 * 5 * 6

Remove duplicates.

1 * 3 * 5

2 * 3 * 4 * 5

4 * 5 * 6

You have te result you want

Well, Drichards solution is pretty elegant, but indeed runs into memory trouble. E.g. 10 factors with only 3 values for each factor gives about 60,000 combinations (3^10). Add an extra value and it goes bang! The recursion is so memory expensive that it causes out-of-memory pretty quickly (have 1 Gig of [virtual] memory and it runs out). Nevertheless, the algorithm does what it must do!

I haven't looked into Ibertacco's iterative example yet, but will come back on that tomorrow soon, as I have to go now. If it fits my problem he will earn the points, but I will also reward Drichards with some points because his code is very instructive and inspiring.

I stared at lbertacco's code for the longest time and couldn't figure out what he was doing...until I realized that he was counting "backwards".

This REALLY bothered my brain, thus inspiring me to figure out to count "forwards"; that is, sequencing the least significant digits before the most significant digits. (Thanks for the inspiration lbertacco!)

The result is probably not as fast as lbertacco's algorithm since it uses the Mod function and Integer divsion instead of simply incrementing a counter...but at least now I can understand the code. =)

My solution consists of a Class called FactorCombinations and a simple user interface. The FactorCombinations class allows you to add as many "factors" as you want by passing in each factor as an ArrayList of values to the addFactor() sub. A call to the generateCombos() sub will start the combination generation process in a separate thread. The class uses events to return the result and give progress updates. The result comes in the form of an ArrayList of ArrayLists representing all the combinations of the factors contained in the class. The user interface then processes these lists to produce the product of each combination.

Simply enter each factor on a seperate line in the textbox, seperating each value by a comma. You can add spaces after the comma if you like. There is a small test data set preloaded in the textbox as an example.

I hope the user interface is simple enough that you can figure out how to use the FactorCombinations class in your own application.

Since I have "loosely" based my solution upon Ibertacco's initial work, I will not at all be offended if you give him the points. I found this to be an intriguing exercise and thoroughly enjoyed solving it.

Below is the class and the user interface.

Regards,

Idle_Mind

' --------------------------

' Class FactorCombinations

' --------------------------

Public Class FactorCombinations

Private factors As ArrayList = New ArrayList

Private t As System.Threading.Thread = New System.Threading.Thread(Ad

Public Event combinations(ByVal combos As ArrayList)

Public Event progress(ByVal percentageComplete As Byte)

Public Event stillInProgress()

Public Event aborted()

Public Sub addFactor(ByVal factor As ArrayList)

factors.Add(factor)

End Sub

Public Sub clearFactors()

factors.Clear()

End Sub

Public ReadOnly Property inProgress() As Boolean

Get

Return t.IsAlive()

End Get

End Property

Public Sub abort()

If t.IsAlive Then

t.Abort()

While t.IsAlive

Application.DoEvents()

End While

RaiseEvent aborted()

End If

End Sub

Public Sub generateCombos()

If t.IsAlive Then

RaiseEvent stillInProgress()

Else

t = New System.Threading.Thread(Ad

t.Start()

End If

End Sub

Private Sub generating()

Dim factor As ArrayList

Dim sizes As ArrayList = New ArrayList

Dim combinations As Integer

Dim i As Integer

Dim j As Integer

Dim remainder As Integer

Dim quotient As Integer

Dim combination As ArrayList

Dim combos As ArrayList = New ArrayList

If factors.Count > 0 Then

combinations = 1

For Each factor In factors

sizes.Add(factor.Count)

combinations = combinations * factor.Count

Next

For i = 0 To combinations - 1

combination = New ArrayList

For j = 1 To factors.Count

combination.Add(Nothing)

Next

quotient = i \ sizes.Item(sizes.Count - 1) ' Integer Division

remainder = i Mod sizes.Item(sizes.Count - 1)

combination(factors.Count - 1) = factors.Item(factors.Count

For j = (sizes.Count - 2) To 0 Step -1

combination.Item(j) = factors.Item(j).Item(quoti

quotient = quotient \ sizes.Item(j) ' Integer Division

Next

combos.Add(combination)

RaiseEvent progress(CInt((i + 1) / combinations * 100))

Next

RaiseEvent combinations(combos)

End If

End Sub

End Class

' --------------------------

' Form1

' --------------------------

Public Class Form1

Inherits System.Windows.Forms.Form

#Region " Windows Form Designer generated code "

Public Sub New()

MyBase.New()

'This call is required by the Windows Form Designer.

InitializeComponent()

'Add any initialization after the InitializeComponent() call

End Sub

'Form overrides dispose to clean up the component list.

Protected Overloads Overrides Sub Dispose(ByVal disposing As Boolean)

If disposing Then

If Not (components Is Nothing) Then

components.Dispose()

End If

End If

MyBase.Dispose(disposing)

End Sub

'Required by the Windows Form Designer

Private components As System.ComponentModel.ICon

'NOTE: The following procedure is required by the Windows Form Designer

'It can be modified using the Windows Form Designer.

'Do not modify it using the code editor.

Friend WithEvents Button1 As System.Windows.Forms.Butto

Friend WithEvents TextBox1 As System.Windows.Forms.TextB

Friend WithEvents ListBox1 As System.Windows.Forms.ListB

Friend WithEvents ProgressBar1 As System.Windows.Forms.Progr

Friend WithEvents Button2 As System.Windows.Forms.Butto

<System.Diagnostics.Debugg

Me.Button1 = New System.Windows.Forms.Butto

Me.TextBox1 = New System.Windows.Forms.TextB

Me.ListBox1 = New System.Windows.Forms.ListB

Me.ProgressBar1 = New System.Windows.Forms.Progr

Me.Button2 = New System.Windows.Forms.Butto

Me.SuspendLayout()

'

'Button1

'

Me.Button1.Anchor = CType((System.Windows.Form

Me.Button1.Location = New System.Drawing.Point(376, 64)

Me.Button1.Name = "Button1"

Me.Button1.Size = New System.Drawing.Size(80, 24)

Me.Button1.TabIndex = 0

Me.Button1.Text = "Start"

'

'TextBox1

'

Me.TextBox1.Anchor = CType(((System.Windows.For

Or System.Windows.Forms.Ancho

Me.TextBox1.Location = New System.Drawing.Point(8, 8)

Me.TextBox1.Multiline = True

Me.TextBox1.Name = "TextBox1"

Me.TextBox1.ScrollBars = System.Windows.Forms.Scrol

Me.TextBox1.Size = New System.Drawing.Size(360, 112)

Me.TextBox1.TabIndex = 1

Me.TextBox1.Text = ""

'

'ListBox1

'

Me.ListBox1.Anchor = CType((((System.Windows.Fo

Or System.Windows.Forms.Ancho

Or System.Windows.Forms.Ancho

Me.ListBox1.Location = New System.Drawing.Point(8, 144)

Me.ListBox1.Name = "ListBox1"

Me.ListBox1.Size = New System.Drawing.Size(448, 238)

Me.ListBox1.TabIndex = 2

'

'ProgressBar1

'

Me.ProgressBar1.Location = New System.Drawing.Point(8, 128)

Me.ProgressBar1.Name = "ProgressBar1"

Me.ProgressBar1.Size = New System.Drawing.Size(448, 8)

Me.ProgressBar1.TabIndex = 3

'

'Button2

'

Me.Button2.Anchor = CType((System.Windows.Form

Me.Button2.Location = New System.Drawing.Point(376, 96)

Me.Button2.Name = "Button2"

Me.Button2.Size = New System.Drawing.Size(80, 24)

Me.Button2.TabIndex = 4

Me.Button2.Text = "Stop!"

'

'Form1

'

Me.AutoScaleBaseSize = New System.Drawing.Size(5, 13)

Me.ClientSize = New System.Drawing.Size(464, 390)

Me.Controls.Add(Me.Button2

Me.Controls.Add(Me.Progres

Me.Controls.Add(Me.ListBox

Me.Controls.Add(Me.TextBox

Me.Controls.Add(Me.Button1

Me.Name = "Form1"

Me.Text = "Enter your factor values"

Me.ResumeLayout(False)

End Sub

#End Region

Private WithEvents fc As FactorCombinations = New FactorCombinations

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Dim testData As String

testData = "1, 2, 3, 4" & vbCrLf & _

"5, 6" & vbCrLf & _

"7, 8, 9"

TextBox1.Text = testData

End Sub

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

Dim factorList As ArrayList

Dim factor As String

Dim factors() As String

Dim values() As String

Dim strValue As String

Dim value As Integer

fc.clearFactors()

factors = Split(TextBox1.Text, vbCrLf)

For Each factor In factors

If factor.Length > 0 Then

factorList = New ArrayList

values = Split(factor, ",")

For Each strValue In values

Try

value = Integer.Parse(Trim(strValu

factorList.Add(value)

Catch ex As Exception

MsgBox(factor & vbCrLf & vbCrLf & ex.Message, MsgBoxStyle.Critical, "Invalid Input")

Exit Sub

End Try

Next

fc.addFactor(factorList)

End If

Next

ListBox1.Items.Clear()

Me.Text = "Generating Combinations..."

fc.generateCombos()

End Sub

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click

fc.abort()

End Sub

Private Sub fc_combinations(ByVal combos As System.Collections.ArrayLi

Dim combo As ArrayList

Dim value As Integer

Dim strFactor As String

Dim product As Integer

Dim i As Integer

Me.Text = "Processing Results.."

ProgressBar1.Value = 0

ListBox1.BeginUpdate()

ListBox1.Items.Clear()

For Each combo In combos

strFactor = ""

product = 1

For Each value In combo

product = product * value

If strFactor = "" Then

strFactor = CStr(value)

Else

strFactor = strFactor & " * " & CStr(value)

End If

Next

strFactor = strFactor & " = " & product

ListBox1.Items.Add(strFact

i = i + 1

ProgressBar1.Value = CInt(i / combos.Count * 100)

Next

ListBox1.EndUpdate()

ProgressBar1.Value = 0

Me.Text = "Enter your combo values"

MsgBox("Processing complete", MsgBoxStyle.Information, "Done")

End Sub

Private Sub fc_progress(ByVal percentageComplete As Byte) Handles fc.progress

ProgressBar1.Value = percentageComplete

End Sub

Private Sub fc_aborted() Handles fc.aborted

MsgBox("Operation Aborted", MsgBoxStyle.Exclamation, "Stopped")

ProgressBar1.Value = 0

Me.Text = "Enter your factor values"

End Sub

Private Sub fc_stillInProgress() Handles fc.stillInProgress

MsgBox("I'm still working on your last request...", MsgBoxStyle.Information, "Patience...")

End Sub

Private Sub Form1_Closing(ByVal sender As Object, ByVal e As System.ComponentModel.Canc

If fc.inProgress Then

fc.abort()

End If

End Sub

End Class

Once you have the prime factors other factors can be found by just multiplying some of the prime factors together.

JR

Private Function PrimeFactor(ByVal iNumberToFactor As Long) As String

Dim i As Long

PrimeFactor = iNumberToFactor 'Initialise

For i = 2 To Fix(Sqr(iNumberToFactor))

If iNumberToFactor Mod i = 0 Then

iNumberToFactor = iNumberToFactor / i

PrimeFactor = i & " * " & PrimeFactor(iNumberToFacto

Exit For

End If

Next i

End Function

Mind boggling at first, your approach is slick and ingenious. The code is indeed not self explaining (as Idle_Mind already observed). However, I do not understand his remark about you counting back.

For me it took a while to grasp that, i = index to the factor, and factor(i) = index to value of that factor. Once I understood that indexing mechanism, it was clear that this code is versatile. And it is fast!

Idle_Mind's solution is a little less usable for me, as it assumes that the factor values are numeric. Nevertheless, I see a few clever ideas in his (neat) code which can be of use.

JR2003,

You sorting trick is not a straight forward approach but more a sort of work-around of factorial mathematics. Also I don't get what you want me to do with the PrimeFactor function.

Point rewarding:

So I like to reward Ibertacco 350 points, and give 75 to both Idle_Mind and Drichards (seems 500 is the max I can give away ...) All of you, thanks for your inspiring help!

I purposely wrote the FactorCombinations class so that it only returns combinations of whatever was placed in the ArrayLists contained within. You can put anything in them, simple data types or instances of classes, and the result will be those same objects in all the possible combinations. All the calculations are done outside the class at the form level, seperating the combination generation from the data manipulation.

I realize your acutal problem is probably much more complex than what you have presented here which is why I wrote the FactorCombinations class with simply generating the combos in mind.

Idle_Mind

Agree, I jumped into conclusions too quickly. It's simply the user interface (input part) that dictated me to enter integers. Changing the type of 'value' into string bypasses this. What I like is that you have build in events. With larger sets it can take a while for the algorithm to do it's work. Then the events come in very handy!

Your solution is as good as Ibertacco's but I have a small preference for his approach. Mostly becaue I find the double loop construction with the carry so clever (and efficient).

Can only give the points away once, and thought this was a fair distribution (350,75,75). No hard feelings I hope?

Martin Koster

Ibertacco's method is definitely the most compact and effiecient. Perhaps you could place his algorithm into my framework...

Just noticed your comment about the counting direction:

>> However, I do not understand his remark about you counting back. (wards)

Lets say we are couting in binary.

000 = 0

001 = 1

010 = 2

011 = 3

100 = 4

101 = 5

110 = 6

111 = 7

Notice that the rightmost digits (the least significant) change before the leftmost (most significant bits). This is how we count normally.

Ibertacco's algorithm changes the leftmost digits before the rightmost, producing this sequence instead:

000 = 0

100 = 4

010 = 2

110 = 6

001 = 1

101 = 5

011 = 3

111 = 7

It produces the same set of combinations, just in a different order. The resulting numbers are not technically "backards" per say, just the way in which he sequences the digits and propogates the "carry over" is backwards.

As the difference in algorithms shows, it is much simpler to count as Ibertacco has done. His method is completely counter-intuitive to everything we are taught in grade school about what each digit in a number represents however. This is why I think it was so hard to understand the code at first.

What planet did you learn to count on Ibertacco? =)

Regards,

Idle_Mind

All Courses

From novice to tech pro — start learning today.

'set n to the nubmer of facors

'and cardinality(i) to the number of values for the i-th factor

'e.g. n=4 with values 3,2,4,2

Dim n As Integer =4

Dim cardinality(4) As Integer

cardinality(0) = 3

cardinality(1) = 2

cardinality(2) = 4

cardinality(3) = 2

'generate combintions

Dim factors(n) As Integer

Dim i As Integer

Dim c As Integer

Dim msg As String

Dim carry As Boolean

For i = 0 To n - 1

factors(i) = 0

Next

Do

c = c + 1 'count combinations

'print combination

msg = "Combination " & c & ": "

For i = 0 To n - 1

msg = msg & factors(i) & " "

Next

MsgBox(msg)

'calculate next combination

i = 0

Do

factors(i) = factors(i) + 1

carry = factors(i) = cardinality(i)

If carry Then

factors(i) = 0

i = i + 1

End If

Loop While carry And i < n

Loop While Not carry