# Need an algorithm to create a so called factorial design (not permutations, but sort of combinations)

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?
###### Who is Participating?

Commented:
Well ok, I'll rewirte my solution in vb.net too:

'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
0

Commented:
0

Author Commented:
Hi sunnycoder,

As you can read NO PERMUTATIONS
0

Commented:
From what I understand you don't want to genrate permutation at all (in fact you consider differnet permutation of same factor as identical).
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]==cardinaliy[i])
if(carry) factor[i++]=0
loop while (carry and i<n)
loop while not carry

0

Middle School Assistant TeacherCommented:
>> Can anyone give me a start or a link to a good example?

What language are you working in?

Idle_Mind
0

Author Commented:
Dear Ibertacco,

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
0

Author Commented:
Dear Idle_Mind

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!
0

Commented:
kostermw, my second example should work fine. Why don't you think so?
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?
0

Middle School Assistant TeacherCommented:
kostermw,

Do you only pick one value from each factor for each combination?

Idle_Mind
0

Commented:
Here's some very simple code to show how you might do it with arbitrary vectors of terms.  This one uses a fixed array, so you'd have to change the fixed dimension array to a vector of vectors.  The only change would be to the first parameter of "ExpandTerms".  Also, I used strings for illustration.  You could easily use numeric values instead.  To experiment, change the array line to:

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(term)
End If
End Sub
0

Commented:
Here's a slightly modified version using vector of vectors.  I still use simple logic to create equal-length vectors, but they can be arbitrary length in this case.

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(GetType(Array), M)
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(GetType(String), N)
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).GetUpperBound(0)
Dim nextTerm As String = term + "*" + factors(level)(i)
ExpandTerms(factors, nextTerm, level + 1)
Next
Else
System.Console.WriteLine(term)
End If
End Sub
End Class
0

Author Commented:
lbertacco,

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

0

Author Commented:
drichards,

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

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

Commented:
kostermw,
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.
0

Commented:
If you just order found the factors smallest to largest.
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
0

Author Commented:
Ibertacco, Drichards

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

Middle School Assistant TeacherCommented:
Ibertacco, Drichards and kostermw,

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

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)
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.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
combinations = combinations * factor.Count
Next

For i = 0 To combinations - 1
combination = New ArrayList
For j = 1 To factors.Count
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 - 1).Item(remainder)
For j = (sizes.Count - 2) To 0 Step -1
combination.Item(j) = factors.Item(j).Item(quotient Mod sizes.Item(j))
quotient = quotient \ sizes.Item(j) ' Integer Division
Next
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.IContainer

'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.Button
Friend WithEvents TextBox1 As System.Windows.Forms.TextBox
Friend WithEvents ListBox1 As System.Windows.Forms.ListBox
Friend WithEvents ProgressBar1 As System.Windows.Forms.ProgressBar
Friend WithEvents Button2 As System.Windows.Forms.Button
<System.Diagnostics.DebuggerStepThrough()> Private Sub InitializeComponent()
Me.Button1 = New System.Windows.Forms.Button
Me.TextBox1 = New System.Windows.Forms.TextBox
Me.ListBox1 = New System.Windows.Forms.ListBox
Me.ProgressBar1 = New System.Windows.Forms.ProgressBar
Me.Button2 = New System.Windows.Forms.Button
Me.SuspendLayout()
'
'Button1
'
Me.Button1.Anchor = CType((System.Windows.Forms.AnchorStyles.Top Or System.Windows.Forms.AnchorStyles.Right), System.Windows.Forms.AnchorStyles)
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.Forms.AnchorStyles.Top Or System.Windows.Forms.AnchorStyles.Left) _
Or System.Windows.Forms.AnchorStyles.Right), System.Windows.Forms.AnchorStyles)
Me.TextBox1.Location = New System.Drawing.Point(8, 8)
Me.TextBox1.Multiline = True
Me.TextBox1.Name = "TextBox1"
Me.TextBox1.ScrollBars = System.Windows.Forms.ScrollBars.Both
Me.TextBox1.Size = New System.Drawing.Size(360, 112)
Me.TextBox1.TabIndex = 1
Me.TextBox1.Text = ""
'
'ListBox1
'
Me.ListBox1.Anchor = CType((((System.Windows.Forms.AnchorStyles.Top Or System.Windows.Forms.AnchorStyles.Bottom) _
Or System.Windows.Forms.AnchorStyles.Left) _
Or System.Windows.Forms.AnchorStyles.Right), System.Windows.Forms.AnchorStyles)
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.Forms.AnchorStyles.Top Or System.Windows.Forms.AnchorStyles.Right), System.Windows.Forms.AnchorStyles)
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.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(strValue))
Catch ex As Exception
MsgBox(factor & vbCrLf & vbCrLf & ex.Message, MsgBoxStyle.Critical, "Invalid Input")
Exit Sub
End Try
Next
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.ArrayList) Handles fc.combinations
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
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.CancelEventArgs) Handles MyBase.Closing
If fc.inProgress Then
fc.abort()
End If
End Sub

End Class
0

Commented:
This function will get the prime factors of any number. There is only one combination of prime factors for any number.
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(iNumberToFactor)
Exit For
End If
Next i

End Function
0

Author Commented:
Ibertacco,
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!

0

Middle School Assistant TeacherCommented:
kostermw,

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
0

Author Commented:
Hi 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
0

Middle School Assistant TeacherCommented:
No hard feelings at all!

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

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

Commented:
kostermw
I think I was confused by the term "factor", to me a factor is a whole number that divides into another number leaving no remainder.
I'm still not really the wiser as to what your "factors" mean. Is it some branch of mathematics?
JR
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.