Find Minimum of Matrix

lewismcdaniel · Apr 5, 2014

Im trying to find the minimum of a 4X4 matrix without a cell interfering another cell in its same row or column. For example,

1 2 3 4
12 14 16 17
6 5 2 1
2 3 4 2

If cell A1 is highlighted then you cant pick another cell in column A or row 1. For example, A1+B2+C3+D4=19 & A4+B1+C3+D2=23 then the minimum value is 19. But there are 4!=24 ways to do this and doing min(a1+b2+c3+d4,a2+...) is time consuming. Can someone please help!

mikerickson · Apr 5, 2014

Try
=MIN(A1:A4)+MIN(B1:B4)+MIN(C1:C4)+MIN(D1:D4)

lewismcdaniel · Apr 5, 2014

mikerickson said:
Try
=MIN(A1:A4)+MIN(B1:B4)+MIN(C1:C4)+MIN(D1:D4)

Remember what if the minimum of column 1 is in row 2, and the minimum of column 3 & 4 are in row 2 as well, they cant interfere with each other in terms of their row and column.

shg · Apr 5, 2014

UDF?

[Table="width:, class:grid"][tr][td] [/td][td]

A

[/td][td]

B

[/td][td]

C

[/td][td]

D

[/td][td]

E

[/td][td]

F

[/td][td]

G

[/td][/tr]
[tr][td]

1

[/td][td]

1

[/td][td]

2

[/td][td]

3

[/td][td]

4

[/td][td][/td][td]

18

[/td][td]F1: =RookMin(A1:D4)[/td][/tr]

[tr][td]

2

[/td][td]

12

[/td][td]

14

[/td][td]

16

[/td][td]

17

[/td][td][/td][td][/td][td][/td][/tr]

[tr][td]

3

[/td][td]

6

[/td][td]

5

[/td][td]

2

[/td][td]

1

[/td][td][/td][td][/td][td][/td][/tr]

[tr][td]

4

[/td][td]

2

[/td][td]

3

[/td][td]

4

[/td][td]

2

[/td][td][/td][td][/td][td][/td][/tr]
[/table]

Code:

Function RookMin(v As Variant) As Double
    Const n         As Long = 4
    Dim aiP(1 To n) As Long
    Dim iP          As Long
    Dim dSum        As Double

    aiP(1) = -1
    RookMin = 1.7E+308
    
    Do While bNextPermut(aiP)
        dSum = 0#
        For iP = 1 To n
            dSum = dSum + v(iP, aiP(iP) + 1)
        Next iP
        If dSum < RookMin Then RookMin = dSum
    Loop
End Function

Function bNextPermut(aiP() As Long) As Boolean
    ' VBA only

    ' Returns the next permutation in lexical order in aiP
    ' If aiP(1) < 0, returns the first permutation and True
    ' If aiP is the last permutation, returns aiP(1)= -1 and False

    ' Adapted from Applied Combinatorics/Tucker p. 224

    ' The first (0th) permutation is  {  0,   1, ..., n-2, n-1}
    ' The last (n!-1) permutation is {n-1, n-1, ...,   1,   0}

    ' shg 2009

    Dim aiTmp()     As Long
    Dim n           As Long
    Dim i           As Long
    Dim h           As Long
    Dim bWrap       As Boolean

    n = UBound(aiP)

    If aiP(1) < 0 Then
        ' initialize to first permutation
        For i = 1 To n
            aiP(i) = i - 1
        Next i
        bNextPermut = True

    Else
        aiTmp = aiP

        For i = n - 1 To 1 Step -1
            If aiP(i) < aiP(i + 1) Then Exit For
        Next i

        If i Then
            bNextPermut = True

            For h = n To i + 1 Step -1
                If aiP(i) < aiP(h) Then Exit For
            Next h

            aiP(i) = aiP(h)
            aiP(h) = aiTmp(i)
            aiTmp(h) = aiP(h)

            For h = i + 1 To n
                aiP(h) = aiTmp(n + i + 1 - h)
            Next h

        Else
            aiP(1) = -1

        End If
    End If
End Function

lewismcdaniel · Apr 5, 2014

That is exactly what I was looking for thank you so much. I needed this to do a 16X16 and 32X32 as well so this is helpful thank you again. But how do I put this into excel, Im not really sure on how to do coding in excel, only matlab and etc. Can you explain to me how you put this in excel?

shg said:

UDF?

[TABLE="class: grid"]
<tbody>[TR]
[TD][/TD]
[TD]

A

[/TD]
[TD]

B

[/TD]
[TD]

C

[/TD]
[TD]

D

[/TD]
[TD]

E

[/TD]
[TD]

F

[/TD]
[TD]

G

[/TD]
[/TR]
[TR]
[TD]

1

[/TD]
[TD]

1

[/TD]
[TD]

2

[/TD]
[TD]

3

[/TD]
[TD]

4

[/TD]
[TD][/TD]
[TD]

18

[/TD]
[TD]F1: =RookMin(A1:D4)[/TD]
[/TR]
[TR]
[TD]

2

[/TD]
[TD]

12

[/TD]
[TD]

14

[/TD]
[TD]

16

[/TD]
[TD]

17

[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]

3

[/TD]
[TD]

6

[/TD]
[TD]

5

[/TD]
[TD]

2

[/TD]
[TD]

1

[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]

4

[/TD]
[TD]

2

[/TD]
[TD]

3

[/TD]
[TD]

4

[/TD]
[TD]

2

[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
</tbody>[/TABLE]

Code:

Function RookMin(v As Variant) As Double
    Const n         As Long = 4
    Dim aiP(1 To n) As Long
    Dim iP          As Long
    Dim dSum        As Double

    aiP(1) = -1
    RookMin = 1.7E+308
    
    Do While bNextPermut(aiP)
        dSum = 0#
        For iP = 1 To n
            dSum = dSum + v(iP, aiP(iP) + 1)
        Next iP
        If dSum < RookMin Then RookMin = dSum
    Loop
End Function

Function bNextPermut(aiP() As Long) As Boolean
    ' VBA only

    ' Returns the next permutation in lexical order in aiP
    ' If aiP(1) < 0, returns the first permutation and True
    ' If aiP is the last permutation, returns aiP(1)= -1 and False

    ' Adapted from Applied Combinatorics/Tucker p. 224

    ' The first (0th) permutation is  {  0,   1, ..., n-2, n-1}
    ' The last (n!-1) permutation is {n-1, n-1, ...,   1,   0}

    ' shg 2009

    Dim aiTmp()     As Long
    Dim n           As Long
    Dim i           As Long
    Dim h           As Long
    Dim bWrap       As Boolean

    n = UBound(aiP)

    If aiP(1) < 0 Then
        ' initialize to first permutation
        For i = 1 To n
            aiP(i) = i - 1
        Next i
        bNextPermut = True

    Else
        aiTmp = aiP

        For i = n - 1 To 1 Step -1
            If aiP(i) < aiP(i + 1) Then Exit For
        Next i

        If i Then
            bNextPermut = True

            For h = n To i + 1 Step -1
                If aiP(i) < aiP(h) Then Exit For
            Next h

            aiP(i) = aiP(h)
            aiP(h) = aiTmp(i)
            aiTmp(h) = aiP(h)

            For h = i + 1 To n
                aiP(h) = aiTmp(n + i + 1 - h)
            Next h

        Else
            aiP(1) = -1

        End If
    End If
End Function

lewismcdaniel · Apr 5, 2014

I figured out how to put it in excel, I have one more question though, how can I get it to spit out which cells gave me that minimum value of 18?

shg said:

UDF?

[TABLE="class: grid"]
<tbody>[TR]
[TD][/TD]
[TD]

A

[/TD]
[TD]

B

[/TD]
[TD]

C

[/TD]
[TD]

D

[/TD]
[TD]

E

[/TD]
[TD]

F

[/TD]
[TD]

G

[/TD]
[/TR]
[TR]
[TD]

1

[/TD]
[TD]

1

[/TD]
[TD]

2

[/TD]
[TD]

3

[/TD]
[TD]

4

[/TD]
[TD][/TD]
[TD]

18

[/TD]
[TD]F1: =RookMin(A1:D4)[/TD]
[/TR]
[TR]
[TD]

2

[/TD]
[TD]

12

[/TD]
[TD]

14

[/TD]
[TD]

16

[/TD]
[TD]

17

[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]

3

[/TD]
[TD]

6

[/TD]
[TD]

5

[/TD]
[TD]

2

[/TD]
[TD]

1

[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]

4

[/TD]
[TD]

2

[/TD]
[TD]

3

[/TD]
[TD]

4

[/TD]
[TD]

2

[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
</tbody>[/TABLE]

Code:

Function RookMin(v As Variant) As Double
    Const n         As Long = 4
    Dim aiP(1 To n) As Long
    Dim iP          As Long
    Dim dSum        As Double

    aiP(1) = -1
    RookMin = 1.7E+308
    
    Do While bNextPermut(aiP)
        dSum = 0#
        For iP = 1 To n
            dSum = dSum + v(iP, aiP(iP) + 1)
        Next iP
        If dSum < RookMin Then RookMin = dSum
    Loop
End Function

Function bNextPermut(aiP() As Long) As Boolean
    ' VBA only

    ' Returns the next permutation in lexical order in aiP
    ' If aiP(1) < 0, returns the first permutation and True
    ' If aiP is the last permutation, returns aiP(1)= -1 and False

    ' Adapted from Applied Combinatorics/Tucker p. 224

    ' The first (0th) permutation is  {  0,   1, ..., n-2, n-1}
    ' The last (n!-1) permutation is {n-1, n-1, ...,   1,   0}

    ' shg 2009

    Dim aiTmp()     As Long
    Dim n           As Long
    Dim i           As Long
    Dim h           As Long
    Dim bWrap       As Boolean

    n = UBound(aiP)

    If aiP(1) < 0 Then
        ' initialize to first permutation
        For i = 1 To n
            aiP(i) = i - 1
        Next i
        bNextPermut = True

    Else
        aiTmp = aiP

        For i = n - 1 To 1 Step -1
            If aiP(i) < aiP(i + 1) Then Exit For
        Next i

        If i Then
            bNextPermut = True

            For h = n To i + 1 Step -1
                If aiP(i) < aiP(h) Then Exit For
            Next h

            aiP(i) = aiP(h)
            aiP(h) = aiTmp(i)
            aiTmp(h) = aiP(h)

            For h = i + 1 To n
                aiP(h) = aiTmp(n + i + 1 - h)
            Next h

        Else
            aiP(1) = -1

        End If
    End If
End Function

shg · Apr 5, 2014

"Spit out" out in what form?

lewismcdaniel · Apr 5, 2014

Lets use the same matrix from above. For example, if A1,B2,C3, and D4 gave use the value 18. Then it either highlights those cells in a certain color or highlights them however, or tells us which 4 cells gave us our minimum value. Just trying to find a way to get it to tell/show me in anyway possible what cells they are.

shg said:
"Spit out" out in what form?

shg · Apr 5, 2014

[Table="width:, class:grid"][tr][td] [/td][td]

A

[/td][td]

B

[/td][td]

C

[/td][td]

D

[/td][td]

E

[/td][td]

F

[/td][td]

G

[/td][/tr]
[tr][td]

1

[/td][td]

51

[/td][td]

42

[/td][td]

34

[/td][td]

28

[/td][td]

13

[/td][td][/td][td][/td][/tr]

[tr][td]

2

[/td][td]

35

[/td][td]

27

[/td][td]

56

[/td][td]

86

[/td][td]

78

[/td][td][/td][td][/td][/tr]

[tr][td]

3

[/td][td]

52

[/td][td]

61

[/td][td]

50

[/td][td]

93

[/td][td]

27

[/td][td][/td][td][/td][/tr]

[tr][td]

4

[/td][td]

28

[/td][td]

12

[/td][td]

47

[/td][td]

67

[/td][td]

31

[/td][td][/td][td][/td][/tr]

[tr][td]

5

[/td][td]

52

[/td][td]

41

[/td][td]

22

[/td][td]

48

[/td][td]

19

[/td][td][/td][td][/td][/tr]

[tr][td]

6

[/td][td][/td][td][/td][td][/td][td][/td][td][/td][td][/td][td][/td][/tr]

[tr][td]

7

[/td][td]

2

[/td][td]

4

[/td][td]

5

[/td][td]

1

[/td][td]

3

[/td][td]

124

[/td][td]A7:F7: {=RookMin(A1:E5)}[/td][/tr]
[/table]

That's a single array formula in A7:E7, column indices in the first n entries, sum in the last.

Code:

Function RookMin(v As Variant) As Variant
    Dim n           As Long
    Dim avd         As Variant
    Dim aiP()       As Long
    Dim iP          As Long
    Dim dSum        As Double
    Dim dSumMin     As Double
    Dim adOut()     As Double

    avd = v
    n = UBound(avd)
    ReDim adOut(1 To n + 1)
    ReDim aiP(1 To n)
    aiP(1) = -1
    dSumMin = 1.7E+308

    Do While bNextPermut(aiP)
        dSum = 0#
        For iP = 1 To n
            dSum = dSum + avd(aiP(iP) + 1, iP)
        Next iP
        If dSum < dSumMin Then
            dSumMin = dSum
            For iP = 1 To n
                adOut(iP) = aiP(iP) + 1
            Next iP
            adOut(iP) = dSum
        End If
    Loop

    RookMin = adOut
End Function

lewismcdaniel · Apr 5, 2014

For cell G7 in your example am I supposed to put a equals sign before everything because I am putting what you are putting in G7 but its not outputting anything?

shg said:
[TABLE="class: grid"]
<tbody>[TR]
[TD][/TD]
[TD]
A
[/TD]
[TD]
B
[/TD]
[TD]
C
[/TD]
[TD]
D
[/TD]
[TD]
E
[/TD]
[TD]
F
[/TD]
[TD]
G
[/TD]
[/TR]
[TR]
[TD]
1
[/TD]
[TD]
51
[/TD]
[TD]
42
[/TD]
[TD]
34
[/TD]
[TD]
28
[/TD]
[TD]
13
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]
2
[/TD]
[TD]
35
[/TD]
[TD]
27
[/TD]
[TD]
56
[/TD]
[TD]
86
[/TD]
[TD]
78
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]
3
[/TD]
[TD]
52
[/TD]
[TD]
61
[/TD]
[TD]
50
[/TD]
[TD]
93
[/TD]
[TD]
27
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]
4
[/TD]
[TD]
28
[/TD]
[TD]
12
[/TD]
[TD]
47
[/TD]
[TD]
67
[/TD]
[TD]
31
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]
5
[/TD]
[TD]
52
[/TD]
[TD]
41
[/TD]
[TD]
22
[/TD]
[TD]
48
[/TD]
[TD]
19
[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]
6
[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]
7
[/TD]
[TD]
2
[/TD]
[TD]
4
[/TD]
[TD]
5
[/TD]
[TD]
1
[/TD]
[TD]
3
[/TD]
[TD]
124
[/TD]
[TD]A7:F7: {=RookMin(A1:E5)}[/TD]
[/TR]
</tbody>[/TABLE]

That's a single array formula in A7:E7, column indices in the first n entries, sum in the last.

Code:

Function RookMin(v As Variant) As Variant Dim n As Long Dim avd As Variant Dim aiP() As Long Dim iP As Long Dim dSum As Double Dim dSumMin As Double Dim adOut() As Double avd = v n = UBound(avd) ReDim adOut(1 To n + 1) ReDim aiP(1 To n) aiP(1) = -1 dSumMin = 1.7E+308 Do While bNextPermut(aiP) dSum = 0# For iP = 1 To n dSum = dSum + avd(aiP(iP) + 1, iP) Next iP If dSum < dSumMin Then dSumMin = dSum For iP = 1 To n adOut(iP) = aiP(iP) + 1 Next iP adOut(iP) = dSum End If Loop RookMin = adOut End Function

Find Minimum of Matrix

lewismcdaniel

New Member

mikerickson

MrExcel MVP

lewismcdaniel

New Member

shg

MrExcel MVP

lewismcdaniel

New Member

lewismcdaniel

New Member

shg

MrExcel MVP

lewismcdaniel

New Member

shg

MrExcel MVP

lewismcdaniel

New Member

Similar threads

Share this page

Find Minimum of Matrix

New Member

MrExcel MVP

New Member

MrExcel MVP

New Member

New Member

MrExcel MVP

New Member

MrExcel MVP

New Member

Similar threads

Share this page

We've detected that you are using an adblocker.

Which adblocker are you using?

Disable AdBlock

Disable AdBlock Plus

Disable uBlock Origin

Disable uBlock