Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

VBA permutation of arrays

Status
Not open for further replies.

Katto

Technical User
Apr 6, 2005
42
US
Hello,

I have the following Table

Name Min Max Nvals
A -5 6.7 6
B -10 23 4
C 2 15 3

I am looking for a code that generates all the sets of [A B C] that include all the possible variatiosn as defined in the Table
The cath is that the code has to be able to cope with an apriori unknown number of variables , so nested loopes option seems to me unusable

Thank you
 
Well, with no further constraints, there are infinite possibilities for each.
 
You may also present your data correctly.
Is it:
[pre]
Name Min Max Nvals
A -5 6.7 6
B -10 23 4
C 2 15 3
[/pre]
or
[pre]
Name Min Max Nvals
A -5 6.7 6
B -10 23 4
C 2 15 3
[/pre]
[pre]
Name Min Max Nvals
A -5 6.7 6
B -10 23 4
C 2 15 3
[/pre]
[pre]
Name Min Max Nvals
A -5 6.7 6
B -10 23 4
C 2 15 3
[/pre]
[ponder]

---- Andy

"Hmm...they have the internet on computers now"--Homer Simpson
 
What do you mean with "all the sets of [A B C] that include all the possible variations" ?
Something like this or something else ?
Code:
Name	Min	Max	Nvals
A	-5	6.7	6
B	-10	23	4
C	2	15	3
			
A	-5	6.7	6
C	2	15	3
B	-10	23	4
			
B	-10	23	4
A	-5	6.7	6
C	2	15	3
			
B	-10	23	4
C	2	15	3
A	-5	6.7	6
			
C	2	15	3
A	-5	6.7	6
B	-10	23	4
			
C	2	15	3
B	-10	23	4
A	-5	6.7	6
 
Here is a more detailed presentation of the question:

I have 3 variables A,B,C which can have repectively 6,4 and 3 possible values.

I need to create SETS of [A B C] that cover all the possible combinations of A, B and C values.

All this in VBA where the input is the NUMBER of VARIABLES (here 3) and the VARIABLES VALUES.

The INPUT data ---------------------------------------------------

Name Min Max Nvals
A -5 6.7 6 i.e. A=[5 11.7 18.4 25.1 31.8 38.5]
B -10 23 4 i.e. B=[10 33 56 79]
C 2 15 3 i.e. C=[2 17 32]

The total number of combinations(permutations) is 6x4x3=72

The output data (Comnination Sets) ------------------------------

no. A B C
1 5 10 2
2 5 33 2
3 5 56 2
4 5 79 2
5 11.7 10 2
6 11.7 33 2
.
.
.
72 38.5 79 32
 
So,
A can have the values of 5 11.7 18.4 25.1 31.8 38.5
B can have the values of 10 33 56 79
C can have the values of 2 17 32
and the outcome you want is:
[pre]
1-5-10-2
2-5-10-17
3-5-10-32
4-5-33-2
5-5-33-17
6-5-33-32
7-5-56-2
8-5-56-17
9-5-56-32
10-5-79-2
11-5-79-17
12-5-79-32
13-11.7-10-2
14-11.7-10-17
15-11.7-10-32
16-11.7-33-2
17-11.7-33-17
18-11.7-33-32
19-11.7-56-2
20-11.7-56-17
21-11.7-56-32
22-11.7-79-2
23-11.7-79-17
24-11.7-79-32
25-18.4-10-2
26-18.4-10-17
27-18.4-10-32
28-18.4-33-2
29-18.4-33-17
30-18.4-33-32
31-18.4-56-2
32-18.4-56-17
33-18.4-56-32
34-18.4-79-2
35-18.4-79-17
36-18.4-79-32
37-25.1-10-2
38-25.1-10-17
39-25.1-10-32
40-25.1-33-2
41-25.1-33-17
42-25.1-33-32
43-25.1-56-2
44-25.1-56-17
45-25.1-56-32
46-25.1-79-2
47-25.1-79-17
48-25.1-79-32
49-31.8-10-2
50-31.8-10-17
51-31.8-10-32
52-31.8-33-2
53-31.8-33-17
54-31.8-33-32
55-31.8-56-2
56-31.8-56-17
57-31.8-56-32
58-31.8-79-2
59-31.8-79-17
60-31.8-79-32
61-38.5-10-2
62-38.5-10-17
63-38.5-10-32
64-38.5-33-2
65-38.5-33-17
66-38.5-33-32
67-38.5-56-2
68-38.5-56-17
69-38.5-56-32
70-38.5-79-2
71-38.5-79-17
72-38.5-79-32
[/pre]

then you can simply do:

Code:
Option Explicit

Sub Katto()
Dim A() As String
Dim B() As String
Dim C() As String
Dim iA As Integer
Dim iB As Integer
Dim iC As Integer
Dim x As Integer

A = Split("5 11.7 18.4 25.1 31.8 38.5", " ")
B = Split("10 33 56 79", " ")
C = Split("2 17 32", " ")

For iA = 0 To UBound(A)
    For iB = 0 To UBound(B)
        For iC = 0 To UBound(C)
            x = x + 1
            Debug.Print x & "-" & A(iA) & "-" & B(iB) & "-" & C(iC)
        Next iC
    Next iB
Next iA

End Sub

---- Andy

"Hmm...they have the internet on computers now"--Homer Simpson
 
Thanks, but, as I mentioned before, I need a script where the NUMBER OF Variables can be a variable ITSELF
In your code, there are 3 nested loops.
If another case requires 10 variable, I need to rewrite the code to accomodate 10 nested loops.
No big deal but, it limites the generality of the code.

I think, I need some kind of a recursive method. Not in expert in this
 
What is the business requirement for this?
Or it is strictly 'academic' (homework) exercise?

---- Andy

"Hmm...they have the internet on computers now"--Homer Simpson
 
no business requirement. it's just a problem that I had before and can't stop trying to get an answer to it
 
So now you have an example that can be easily modified to include more than 3 loops, for an application that is "just a problem that I had before and can't stop trying to get an answer to it."

Skip,
[sub]
[glasses]Just traded in my OLD subtlety...
for a NUance![tongue][/sub]
"The most incomprehensible thing about the universe is that it is comprehensible" A. Einstein

You Matter...
unless you multiply yourself by the speed of light squared, then...
You Energy!
 
you do understand that your solution is the trivial solution to the problem I stated, right?
It's not quite what I was looking for
 
If we guess that Min is the minimum value of each set, Max is the maximum value of each set and Nvals the number of members in each set then every one of your examples fails your criteria.

Name Min Max Nvals
A -5 6.7 6 i.e. A=[5 11.7 18.4 25.1 31.8 38.5]
Min is not a member. Max is not a member. Five out of six values are larger than Max

B -10 23 4 i.e. B=[10 33 56 79]
Min is not a member. Max is not a member. Three out of four values are larger than Max

C 2 15 3 i.e. C=[2 17 32]
Max is not a member. Two out of three values are larger than Max

You do understand that coding is the systematic solution of a fully defined problem, right?
 
This is called Cartesian Product
To make the implementation universal - i.e. without need to have 3 loops for 3 arrays, 4 loops for 4 arrays,..etc - we can create 2 procedures:

1) procedure product_of_two:
which will have on input two 1D arrays and returns an array of arrays
This procedure computes only product of two arrays

2) procedure product_of_n
which will have on input array of arrays and will return other array of arrays
This procedure will use the previous procedure to process compound array given on input.

Unfortunatelly, i don't have now Windows machine by my hands, so i have done proof of concept on Linux using python, which uses lists instead of arrays.

katto.py
Code:
def product_of_two(list_1, list_2):
  # input : two lists
  # output: list of lists
  lists = []
  for x in list_1:
    for y in list_2:
      if type(x) == list:
        # create new list from list x and element y
        list_new = [e for e in x]
        list_new.append(y)
        lists.append(list_new)
      else:
        lists.append([x, y])
  #
  return lists

def product_of_n(input_lists):
  # input : list of lists
  # output: list of lists
  lists = product_of_two(input_lists[0], input_lists[1])
  for sublist in input_lists[2:]:
    lists = product_of_two(lists, sublist)
  #
  return lists

if __name__ == "__main__":
  a=[5, 11.7, 18.4, 25.1, 31.8, 38.5]
  b=[10, 33, 56, 79]
  c=[2, 17, 32]
  d=[100, 200]

  input_lists = [a, b, c] 
  #input_lists = [a, b, c, d] 

  output_lists = product_of_n(input_lists)
  
  # print result
  n = 0
  for sublist in output_lists:
    n += 1
    print("%2d: %s" % (n, sublist))

With the data given above it delivers the same result as posted by Andrzejek
Code:
$ python3 katto.py 
 1: [5, 10, 2]
 2: [5, 10, 17]
 3: [5, 10, 32]
 4: [5, 33, 2]
...
...
69: [38.5, 56, 32]
70: [38.5, 79, 2]
71: [38.5, 79, 17]
72: [38.5, 79, 32]

if you uncomment
Code:
input_lists = [a, b, c, d]
you will get Cartesian Product of 4 arrays without need to implement additional loop:
Code:
 1: [5, 10, 2, 100]
 2: [5, 10, 2, 200]
 3: [5, 10, 17, 100]
 4: [5, 10, 17, 200]
...
...
140: [38.5, 79, 2, 200]
141: [38.5, 79, 17, 100]
142: [38.5, 79, 17, 200]
143: [38.5, 79, 32, 100]
144: [38.5, 79, 32, 200]
 
I was thinking to suggest Python Itertools.Product, which would do this in no time.

But Katto is constrained to VBA.
 
@mintjulep,
That's why I tried to do it without itertools so that it could then be written in VBA in the similar way.
 
@mikrom

Have you looked inside iteertools, to see how they do it?

Edit:
Ok, I just peaked. Iteertools is implemented in c.

 
Out of curiosity, I rewrote into VBA the python code posted before

Code:
' Cartesian Product

Function join_collection(list As Collection, separator As String) As String
  join_collection = ""
  For i = 1 To list.Count - 1
    join_collection = join_collection & list.Item(i) & separator
  Next i
  join_collection = join_collection & list.Item(list.Count)
End Function

Function product_of_two(list_1 As Collection, list_2 As Collection) As Collection
   'input : two lists
   'output: list of lists
   Set product_of_two = New Collection
   For Each x In list_1
     For Each y In list_2
       'create new list from list x and element y
       Set list_new = New Collection
       If (TypeOf x Is Collection) Then
         For Each e In x
           list_new.Add e
         Next e
         list_new.Add y
         product_of_two.Add list_new
       Else
         list_new.Add x
         list_new.Add y
         product_of_two.Add list_new
       End If
     Next y
   Next x
   'return list of lists
End Function

Function product_of_n(input_lists As Collection) As Collection
  'input : list of lists
  'output: list of lists
  
  Dim lists As Collection
  Set lists = product_of_two(input_lists.Item(1), input_lists.Item(2))
  For i = 3 To input_lists.Count
    Set lists = product_of_two(lists, input_lists.Item(i))
  Next i
  Set product_of_n = lists
End Function

Sub test()
  Debug.Print "Test: Cartesian Product" & vbCrLf
  
  Dim values() As Variant
  Dim a As New Collection
  Dim b As New Collection
  Dim c As New Collection
  Dim d As New Collection
  Dim input_lists As New Collection
  Dim output_lists As New Collection
   
  values = Array(5, 11.7, 18.4, 25.1, 31.8, 38.5)
  
  For Each Item In values
    a.Add Item
  Next Item
  
  values = Array(10, 33, 56, 79)
  
  For Each Item In values
    b.Add Item
  Next Item
  
  values = Array(2, 17, 32)
  
  For Each Item In values
    c.Add Item
  Next Item
  
  values = Array(100, 200)
  
  For Each Item In values
    d.Add Item
  Next Item
  
  input_lists.Add a
  input_lists.Add b
  input_lists.Add c
  'input_lists.Add d
  Set output_lists = product_of_n(input_lists)
   
  'print result
  n = 0
  Dim sublist As Collection
  For Each sublist In output_lists
    n = n + 1
    Debug.Print Right("   " & n, 3) & ": [" & join_collection(sublist, ", ") & "]"
  Next sublist
End Sub

Running the test makro prints in the immediate window the same result as before
Code:
Test: Cartesian Product

  1: [5, 10, 2]
  2: [5, 10, 17]
  3: [5, 10, 32]
  4: [5, 33, 2]
...
...
 69: [38.5, 56, 32]
 70: [38.5, 79, 2]
 71: [38.5, 79, 17]
 72: [38.5, 79, 32]
 
Wow,

Thank you all for your responses

I'll try the VBA code suggested
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top