Valid arrangement of non duplicate 1:1 pairs in a row

[tschatz]

Hello,

given the following data pairs:

A-B
A-C
A-D
A-E
A-F
B-C
B-D
B-E
B-F
C-D
C-E
C-F
D-E
D-F
E-F

with n = 6 being the number of unique single entities. I want to calculate one possible solution for the highest possible parallelisation.

Assuming each element can only exist once at a certain time, I can determine the maximum number of parallel slots as

=ROUNDDOWN(n/2,0)

.
I would like to find a possible valid arrangement of the data pairs.

One possible valid (every element is only allowed once per row) solution might look like this:

B - C	D - F	A - E
C - E	A - D	B - F
A - B	D - E	C - F
A - C	B - D	E - F
A - F	B - E	C - D

I thought about randomly filling each row with the "left over" data-pairs starting with row 1 and checking their validity, however starting with row 3 you quickly run into solutions where not all columns can be filled out e.g.

B - C	D - F	A - E
C - E	A - D	B - F
A - B	C - D	E - F
A - C	B - D
A - F	D - E
B - E	C - F

Can anyone give me a hint of how to best approach this topic?

Thanks a lot!

 

[BSALV]

Map1.xlsm
	A	B	C	D	E
1	A-B		0,848138	0,908966	0,530637
2	A-C		0,458089	0,998203	0,085773
3	A-D		0,122752	0,989669	0,491893
4	A-E		0,20507	0,788026	0,605936
5	A-F		0,943109	0,645382	0,849694
6	B-C
7	B-D		B-C	A-E	C-D
8	B-E		C-F	A-B	E-F
9	B-F		D-F	A-C	C-E
10	C-D		D-E	B-D	B-F
11	C-E		A-D	B-E	A-F
12	C-F
13	D-E
14	D-F
15	E-F
Blad2

Cell Formulas
Range	Formula
C1:E5	C1	=RANDARRAY(5,3)
C7:E11	C7	=INDEX($A$1:$A$15,RANK(C1,$C$1:$E$5))
Dynamic array formulas.

 

[tschatz]

Map1.xlsm
	A	B	C	D	E
1	A-B		0,848138	0,908966	0,530637
2	A-C		0,458089	0,998203	0,085773
3	A-D		0,122752	0,989669	0,491893
4	A-E		0,20507	0,788026	0,605936
5	A-F		0,943109	0,645382	0,849694
6	B-C
7	B-D		B-C	A-E	C-D
8	B-E		C-F	A-B	E-F
9	B-F		D-F	A-C	C-E
10	C-D		D-E	B-D	B-F
11	C-E		A-D	B-E	A-F
12	C-F
13	D-E
14	D-F
15	E-F
Blad2

Cell Formulas
Range	Formula
C1:E5	C1	=RANDARRAY(5,3)
C7:E11	C7	=INDEX($A$1:$A$15,RANK(C1,$C$1:$E$5))
Dynamic array formulas.

Hi BSALV,

thanks for your reply, however your proposal does not offer a valid solution.

For example the this row:

the letter "C" is not unique.

 

[BSALV]

a little bit more complicated, in average, 4 trials for 1 good parallelisation.

Sub rand()
     Dim rand2(), result()
     a = ActiveSheet.Range("A1").CurrentRegion.Columns(1)
     Application.ScreenUpdating = False
     Do
          DoEvents
          ptr = ptr + 1
          ReDim result(1 To 5)
          rand1 = WorksheetFunction.RandArray(UBound(a))

          ReDim rand2(1 To UBound(rand1), 1 To 2)
          For i = 1 To UBound(rand2)
               rand2(i, 1) = rand1(i, 1): rand2(i, 2) = a(i, 1)
          Next

          r = 1
          b = True
          Do
               rand3 = Application.Sort(rand2, 1)
               rand2 = rand3
               For i = 1 To UBound(rand2)
                    b = (rand2(i, 1) < 1)
                    If Not b Then Exit For
                    sp = Split(rand2(i, 2), "-")
                    If InStr(result(r), sp(0)) + InStr(result(r), sp(1)) = 0 Then
                         result(r) = result(r) & "," & rand2(i, 2)
                         rand2(i, 1) = 1000000000#
                         If Len(result(r)) > 10 Then
                              result(r) = Mid(result(r), 2): r = r + 1:
                              Exit For
                         End If
                    End If
               Next
          Loop While b
          
          With Range("D1").Resize(UBound(result))
               .Value = Application.Transpose(result)
               Application.DisplayAlerts = False
               .TextToColumns .Range("A1"), xlDelimited, , , , , 1
               Application.DisplayAlerts = True
          End With
     
     Loop While Range("D5") = "" And ptr < 100
     
     Range("F6").Value = ptr & " trials"
     Range("H" & Rows.Count).End(xlUp).Offset(1) = ptr
End Sub

Map1.xlsm
	A	B	C	D	E	F
1	A-B	1		B-E	C-D	A-F
2	A-C	1		B-F	A-D	C-E
3	A-D	1		C-F	A-B	D-E
4	A-E	1		A-C	B-D	E-F
5	A-F	1		B-C	D-F	A-E
6	B-C	1				5 trials
7	B-D	1
8	B-E	1
9	B-F	1
10	C-D	1
11	C-E	1
12	C-F	1
13	D-E	1
14	D-F	1
15	E-F	1
Blad2

Cell Formulas
Range	Formula
B1:B15	B1	=COUNTIF($D$1:$F$5,A1)

 

[tschatz]

Hi BSALV,

that gave me a very good starting point! Thanks a lot for your help!

BR
Tillmann