Complex Combinatorial sort VBA/Macro

[4petris]

Hi everyone,

I have a tricky task Let me clarify that step by step below.

Input

• table with 5 columns
• columns are: combination, place1, place2, place3, income
• column combination represents a number of each combination (combination of 3 places)
• place1, 2, 3 are basically points where a car needs to go
• income says how much we get paid to drive in a specific combination (way)

e.g. we can say that combination #6 brings 13628.40 income and the car needs to go through places A, O & M.

First of all, I need to find out the way how I specify: Let's say that formula will go from combination 1 to 197. We currently know that all combinations are sort from the biggest price to the lowest one.

Secondly, I need to set up the rule saying, once you drove through a specific place, DO NOT drive through that point again.
e.g. We take the combination #1 F, A, O and we know that cannot drive again to those points. So a formula looks for other combinations the next possible combination is #1 3 since M, K, N do not match with previous combination F, A, O. Now we have already 6 places where the car cannot drive anymore. F, A, O, M, K, N. Then the next available combination is E, I, J. And it goes like that until it does not have all possible combinations found.

We can say that all found combinations are below:

combination	place1	place2	place3	income
1	F	A	O	16556
13	M	K	N	12126
19	E	I	J	10610
74	Q	T	R	5500
93	G	H	C	4695

<tbody>
</tbody>

TOTAL Income is 49549. This result is based on the fact, that formula goes from combination #1 to #1 97 where biggest incomes are first. What if the table is sort in a different way? How many combinations can be there? 197 factorial? How can find the best distribution in order to get the highest income value?

 

[4petris]

https://docs.google.com/spreadsheets/d/145u25mcU3uTOFtwRV2b9ksFU3ZwjLmpIZIua_XOqFX0/edit?usp=sharing

 

[StephenCrump]

The number of combinations to test should be manageable, because of the constraints about not visiting the same location twice.

But a question first ...

Your result shows the income for five trips = 15 locations, but you actually have 20 locations (A, B ... T).

Do you need to visit all 20 locations (in which case there will necessarily be at least one duplicate)?

Or are you looking to maximise the income for a general N trips, minimising the number of duplicates, where N in this case happens to be 5?

 

[shg]

Here's how I would do it.

1. Write code that starts with a forward compatibility list for each node (combo) (i.e., node 13 is on the list for 1; node 1 is not on the list for 13).

2. Then do a depth-first search starting with node 1 to get all sequences that start from there (i.e., traverse the entire tree having node 1 as its root) and capture the total income for each. When you arrive at node 13 from node 1, for example, the next choice must be common to the lists for both nodes; when you arrive at the third, the next choice must be common to all three. At each leaf node, backtrack to the next higher node that offers a different path than you have taken so far.

3. Repeat step 2 for every other node as the starting point.

My sense is that each tree winnows quickly, so there are a reasonable number of leaf nodes. That makes it doable in finite time, but the code would take (me at least) a day or more to write.

Sounds like a fun problem for someone that has the time.

 

[shg]

Here's some rows of the compatibility list:

A​

B​

C​

D​

E​

F​

G​

H​

I​

J​

K​

L​

M​

N​

O​

P​

Q​

R​

S​

T​

U​

V​

W​

X​

Y​

Z​

AA​

AB​

AC​

AD​

AE​

AF​

AG​

AH​

AI​

AJ​

AK​

AL​

AM​

AN​

AO​

AP​

AQ​

AR​

AS​

AT​

AU​

AV​

AW​

AX​

AY​

AZ​

BA​

BB​

BC​

BD​

BE​

BF​

BG​

BH​

BI​

BJ​

BK​

BL​

BM​

BN​

BO​

BP​

BQ​

BR​

BS​

BT​

BU​

BV​

BW​

BX​

BY​

BZ​

CA​

CB​

CC​

CD​

CE​

CF​

CG​

CH​

CI​

CJ​

CK​

CL​

CM​

CN​

CO​

1​

Node​

Loca​

Loc2​

Loc3​

Value​

2​

1​

F​

A​

O​

16,566.87​

13​

15​

19​

22​

24​

31​

35​

39​

42​

46​

47​

53​

57​

59​

66​

67​

68​

70​

73​

74​

76​

80​

81​

83​

93​

102​

107​

108​

110​

112​

114​

120​

125​

126​

127​

131​

133​

135​

137​

144​

149​

150​

151​

159​

160​

161​

164​

165​

169​

172​

174​

177​

178​

179​

187​

189​

193​

196​

197​

14​

13​

M​

K​

N​

12,126.41​

14​

17​

19​

20​

23​

25​

26​

28​

29​

38​

42​

43​

45​

49​

50​

56​

58​

59​

72​

74​

75​

77​

83​

84​

85​

86​

87​

90​

92​

93​

94​

97​

98​

99​

100​

101​

102​

103​

104​

105​

106​

109​

110​

115​

116​

117​

118​

119​

120​

121​

122​

129​

130​

132​

134​

135​

136​

138​

139​

140​

141​

145​

150​

152​

154​

155​

156​

158​

159​

165​

168​

169​

171​

173​

176​

178​

180​

181​

182​

183​

184​

186​

190​

192​

194​

20​

19​

E​

I​

J​

10,610.69​

20​

21​

25​

26​

27​

30​

32​

33​

36​

37​

44​

45​

47​

48​

51​

52​

54​

56​

57​

58​

61​

62​

63​

64​

65​

69​

74​

75​

76​

77​

78​

82​

84​

86​

87​

89​

90​

91​

93​

96​

98​

99​

105​

109​

114​

115​

116​

121​

124​

125​

127​

128​

129​

130​

131​

132​

137​

138​

139​

140​

142​

148​

149​

151​

153​

155​

158​

159​

160​

162​

167​

168​

171​

175​

179​

180​

183​

184​

185​

186​

188​

189​

191​

193​

194​

195​

197​

75​

74​

Q​

T​

R​

5,550.24​

75​

79​

81​

82​

83​

85​

88​

89​

90​

91​

93​

94​

95​

96​

100​

101​

102​

103​

104​

105​

106​

107​

108​

109​

110​

111​

112​

113​

114​

118​

120​

121​

122​

123​

126​

127​

129​

130​

131​

133​

134​

135​

136​

138​

139​

141​

143​

144​

145​

146​

147​

148​

149​

150​

152​

153​

154​

156​

157​

158​

160​

161​

163​

164​

166​

170​

172​

173​

174​

175​

176​

177​

181​

182​

183​

188​

192​

194​

195​

196​

94​

93​

G​

H​

C​

4,695.31​

94​

95​

97​

98​

99​

100​

101​

106​

107​

108​

109​

110​

111​

113​

115​

116​

117​

118​

119​

122​

123​

124​

125​

126​

128​

132​

133​

136​

137​

138​

140​

142​

143​

144​

145​

146​

147​

148​

149​

151​

152​

154​

155​

157​

159​

162​

163​

165​

166​

167​

168​

169​

170​

172​

176​

178​

180​

181​

185​

186​

187​

188​

189​

190​

191​

193​

194​

195​

197​

The highlights on row 13 are the choices available after node 1 > node 13, and on row 19 the choices available after node 1 > node 13 > node 19.

 

[4petris]

Hello Stephen,

I am sorry, I did not clarify that. I do not need to visit all 20 locations, the main idea is to find the biggest total income regardless on how many locations is visited. Thank you.

The number of combinations to test should be manageable, because of the constraints about not visiting the same location twice.

But a question first ...

Your result shows the income for five trips = 15 locations, but you actually have 20 locations (A, B ... T).

Do you need to visit all 20 locations (in which case there will necessarily be at least one duplicate)?

Or are you looking to maximise the income for a general N trips, minimising the number of duplicates, where N in this case happens to be 5?

 

[4petris]

Hi shg,

Thank you for your input, it's a good overview and actually interesting idea how to approach this problem However, do you think it can be solver somehow e.g. imagine that node are sort in a different way it means that node 1 will be changed to number 6 not combination F, A, O will not be anymore marked as node 1 but as node 6, just an example. Because now I have all nodes sort by the highest value but it is not mandatory it can be sort however. It can be also said that it does not matter how it is sort but I am looking for the best sort which will lead to getting the biggest total income (value)

I know I have been actually struggling with this problem for a week but unfortunately, I am not so skillful in Excel in order to figure it out

Here's some rows of the compatibility list:

A​

B​

C​

D​

E​

F​

G​

H​

I​

J​

K​

L​

M​

N​

O​

P​

Q​

R​

S​

T​

U​

V​

W​

X​

Y​

Z​

AA​

AB​

AC​

AD​

AE​

AF​

AG​

AH​

AI​

AJ​

AK​

AL​

AM​

AN​

AO​

AP​

AQ​

AR​

AS​

AT​

AU​

AV​

AW​

AX​

AY​

AZ​

BA​

BB​

BC​

BD​

BE​

BF​

BG​

BH​

BI​

BJ​

BK​

BL​

BM​

BN​

BO​

BP​

BQ​

BR​

BS​

BT​

BU​

BV​

BW​

BX​

BY​

BZ​

CA​

CB​

CC​

CD​

CE​

CF​

CG​

CH​

CI​

CJ​

CK​

CL​

CM​

CN​

CO​

1​

Node​

Loca​

Loc2​

Loc3​

Value​

2​

1​

F​

A​

O​

16,566.87​

13​

15​

19​

22​

24​

31​

35​

39​

42​

46​

47​

53​

57​

59​

66​

67​

68​

70​

73​

74​

76​

80​

81​

83​

93​

102​

107​

108​

110​

112​

114​

120​

125​

126​

127​

131​

133​

135​

137​

144​

149​

150​

151​

159​

160​

161​

164​

165​

169​

172​

174​

177​

178​

179​

187​

189​

193​

196​

197​

14​

13​

M​

K​

N​

12,126.41​

14​

17​

19​

20​

23​

25​

26​

28​

29​

38​

42​

43​

45​

49​

50​

56​

58​

59​

72​

74​

75​

77​

83​

84​

85​

86​

87​

90​

92​

93​

94​

97​

98​

99​

100​

101​

102​

103​

104​

105​

106​

109​

110​

115​

116​

117​

118​

119​

120​

121​

122​

129​

130​

132​

134​

135​

136​

138​

139​

140​

141​

145​

150​

152​

154​

155​

156​

158​

159​

165​

168​

169​

171​

173​

176​

178​

180​

181​

182​

183​

184​

186​

190​

192​

194​

20​

19​

E​

I​

J​

10,610.69​

20​

21​

25​

26​

27​

30​

32​

33​

36​

37​

44​

45​

47​

48​

51​

52​

54​

56​

57​

58​

61​

62​

63​

64​

65​

69​

74​

75​

76​

77​

78​

82​

84​

86​

87​

89​

90​

91​

93​

96​

98​

99​

105​

109​

114​

115​

116​

121​

124​

125​

127​

128​

129​

130​

131​

132​

137​

138​

139​

140​

142​

148​

149​

151​

153​

155​

158​

159​

160​

162​

167​

168​

171​

175​

179​

180​

183​

184​

185​

186​

188​

189​

191​

193​

194​

195​

197​

75​

74​

Q​

T​

R​

5,550.24​

75​

79​

81​

82​

83​

85​

88​

89​

90​

91​

93​

94​

95​

96​

100​

101​

102​

103​

104​

105​

106​

107​

108​

109​

110​

111​

112​

113​

114​

118​

120​

121​

122​

123​

126​

127​

129​

130​

131​

133​

134​

135​

136​

138​

139​

141​

143​

144​

145​

146​

147​

148​

149​

150​

152​

153​

154​

156​

157​

158​

160​

161​

163​

164​

166​

170​

172​

173​

174​

175​

176​

177​

181​

182​

183​

188​

192​

194​

195​

196​

94​

93​

G​

H​

C​

4,695.31​

94​

95​

97​

98​

99​

100​

101​

106​

107​

108​

109​

110​

111​

113​

115​

116​

117​

118​

119​

122​

123​

124​

125​

126​

128​

132​

133​

136​

137​

138​

140​

142​

143​

144​

145​

146​

147​

148​

149​

151​

152​

154​

155​

157​

159​

162​

163​

165​

166​

167​

168​

169​

170​

172​

176​

178​

180​

181​

185​

186​

187​

188​

189​

190​

191​

193​

194​

195​

197​

<tbody>
</tbody>

The highlights on row 13 are the choices available after node 1 > node 13, and on row 19 the choices available after node 1 > node 13 > node 19.

 

[Fluff]

Cross posted https://www.excelforum.com/excel-pr...005-complex-combinatorial-sort-vba-macro.html

Cross-Posting
While we do not prohibit Cross-Posting on this site, we do ask that you please mention you are doing so and provide links in each of the threads pointing to the other thread (see rule 13 here along with the explanation: Forum Rules).
This way, other members can see what has already been done in regards to a question, and do not waste time working on a question that may already be answered.

 

[StephenCrump]

Using a Boolean tree, along shg's lines, it doesn't matter how your data is sorted:

Workbook: https://app.box.com/s/1j9osr2lbobb1sml21ujjnpo0wtttbnj

Dim vIncome As Variant
Dim dMax As Double
Dim lCombination() As Long, lOptimum() As Long, lNoRoutes As Long, lNoTrips As Long
Dim bPossible() As Boolean
Dim bCompatible() As Boolean
Sub Test()

    Dim lNoPlaces  As Long, i As Long, j As Long, k As Long, m As Long
    Dim vRoutes As Variant
        
    vRoutes = [Routes]
    vIncome = [Income]
    lNoRoutes = UBound(vRoutes)
    lNoPlaces = UBound(vRoutes, 2)
    lNoTrips = [N]
    ReDim bPossible(1 To lNoRoutes, 1 To lNoRoutes)
    ReDim bCompatible(1 To lNoTrips, 1 To lNoRoutes)
    ReDim lCombination(1 To lNoTrips)
    ReDim lOptimum(1 To lNoTrips)
    dMax = 0
    
    For i = 1 To lNoRoutes
        For j = i To lNoRoutes
            For k = 1 To lNoPlaces
                For m = 1 To lNoPlaces
                    If vRoutes(i, k) = vRoutes(j, m) Then GoTo Fail
                Next m
            Next k
        bPossible(i, j) = True
Fail:
        Next j
    Next i

    Select Case lNoTrips
    Case 1
        dMax = Application.Max(vIncome)
        lOptimum(1) = Application.Match(dMax, vIncome, 0)
    Case Is > 1
        For i = 1 To lNoRoutes
            For j = 1 To lNoRoutes
                bCompatible(1, j) = bPossible(i, j)
            Next j
            lCombination(1) = i
            Call GetPossibles(i, 2)
        Next i
    End Select
    
    With Range("N7")
        .Resize(2, 8).ClearContents
        If dMax > 0 Then
            .Resize(, lNoTrips).Value = lOptimum
            .Offset(1).Value = dMax
        Else
            MsgBox "No Solutions"
        End If
    End With

End Sub
Sub GetPossibles(lStart As Long, lIteration As Long)
    
    Dim i As Long, j As Long
    Dim dAmount As Double
    
    For i = lStart + 1 To lNoRoutes
        bCompatible(lIteration, i) = bCompatible(lIteration - 1, i) And bPossible(lStart, i)
    Next i
    For i = lStart + 1 To lNoRoutes
        If bCompatible(lIteration, i) Then
            lCombination(lIteration) = i
            If lIteration = lNoTrips Then
                dAmount = 0
                For j = 1 To lNoTrips
                    dAmount = dAmount + vIncome(lCombination(j), 1)
                Next j
                If dAmount > dMax Then
                    lOptimum = lCombination
                    dMax = dAmount
                End If
            Else
                Call GetPossibles(i, lIteration + 1)
            End If
        End If
    Next i
    
End Sub

 

[StephenCrump]

Routes: =G2:I198 {=MATCH(B2:D198,Locations,)}
Locations: K2:K21
N: = N6
Income: =E2:E198

Book1
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R
1	COMBO	PLACE1	PLACE2	PLACE3	Income		Routes				Locations
2	1	F	A	O	16,566.87		6	1	15		A
3	2	F	A	P	16,462.11		6	1	16		B
4	3	A	O	K	14,773.89		1	15	11		C
5	4	F	A	N	14,465.60		6	1	14		D
6	5	A	O	P	14,000.70		1	15	16		E		N	5
7	6	A	O	M	13,628.40		1	15	13		F		Solution	1	13	19	74	93
8	7	A	E	O	13,380.02		1	5	15		G		Sum	49,549.52
9	8	F	E	A	13,175.27		6	5	1		H
10	9	F	A	M	13,042.10		6	1	13		I
11	10	A	O	Q	12,907.62		1	15	17		J
12	11	A	M	N	12,651.02		1	13	14		K
13	12	A	O	N	12,580.33		1	15	14		L
14	13	M	K	N	12,126.41		13	11	14		M
15	14	F	Q	P	12,005.78		6	17	16		N
16	15	I	M	K	11,646.22		9	13	11		O
17	16	A	E	M	11,339.19		1	5	13		P
18	17	F	E	Q	11,266.03		6	5	17		Q
19	18	A	M	J	11,026.93		1	13	10		R
20	19	E	I	J	10,610.69		5	9	10		S
21	20	F	A	T	10,546.79		6	1	20		T
22	21	etc	etc	etc	10,509.38
Sheet1