Sorting a string array containing combinations

[noname]

Hi,

i have a string array which 16 variables viz.,
Array2Compare()=(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16)

there is another array Array2Sort()which already contains 2^16 =65535 combinations for the above 16, viz.,

Array2Sort()
============
Array2Sort(0)=x1
Array2Sort(1)=x2
Array2Sort(2)=x14
Array2Sort(3)=x1 x14
Array2Sort(4)=x1 x10
Array2Sort(5)=x6 x8 x16
Array2Sort(6)=x13 x14 x16
Array2Sort(7)=x2 x5 x14 x16
Array2Sort(8)=x5 x9 x14 x16
Array2Sort(8)=x4 x10 x12 x13
....
....

what i want to do is take each element e.g x1, of the Array2Compare(), search it in Array2Sort(), group all x1 occurrences together in a sorted manner back to Array2Sort().
Also, simultaneously create another array which does not contain occurrences of x1 in it. see below e.g:

I want to have both the arrays grouped and sorted like this in Ascending order.

with x1 without x1
--------------------------
x1 -
x1 x2 x2
x1 x3 x3
x1 x4 x4
x1 x2 x3 x2 x3
x1 x2 x4 x2 x4
x1 x3 x4 x3 x4
x1 x2 x3 x4 x2 x3 x4

x2 -
x1 x2 x1
x2 x3 x3
x2 x4 x4
x1 x2 x3 x1 x3
x1 x2 x4 x1 x4
x2 x3 x4 x3 x4
x1 x2 x3 x4 x1 x3 x4
.....
.....
so there would be 2 sorted arrays
withX() & withoutX()


my question is:
Can the Array Array2Sort() be grouped & sorted in place without using any loops?
Has someone attempted something like this and which is very fast?

i think this is very challenging though stumped right now!

 

[GS]

The simplest (and fastest) way I've found to sort arrays is to 'dump'
them into a temp worksheets and use Excel's Sort.

Also, the only way to check each element in an array is to iterate
(loop) the outer array against the inner array.

Example: <aircode>
For i = LBound(vOuter) To UBound(vOuter)
For n = LBound(vInner) To UBound(vInner)
If vInner(n) = vOuter(i) Then '//do stuff
Next 'n
Next 'i

 

[noname]

hi Garry,

i think i was not clear in explaining my issue.

i have one array of 16 variables x1 to x16.
i have another array which has combinations of those 16 variables. i.e. 65536
my problem is that this Combination array is not sorted. i like to have it in two different arrays sorted as shown below.

with x1 without x1
--------------------------
x1 -
x1 x2 x2
x1 x3 x3
x1 x4 x4
x1 x2 x3 x2 x3
x1 x2 x4 x2 x4
x1 x3 x4 x3 x4
x1 x2 x3 x4 x2 x3 x4

x2 -
x1 x2 x1
x2 x3 x3
x2 x4 x4
x1 x2 x3 x1 x3
x1 x2 x4 x1 x4
x2 x3 x4 x3 x4
x1 x2 x3 x4 x1 x3 x4

 

[GS]

noname explained on 10/27/2011 :

hi Garry,

i think i was not clear in explaining my issue.

i have one array of 16 variables x1 to x16.
i have another array which has combinations of those 16 variables. i.e. 65536
my problem is that this Combination array is not sorted. i like to have it in
two different arrays sorted as shown below.

And so you would need to modify my loop example to determine the
'withs' and the 'withouts'. This is where the "'//do stuff" comes in:
you put the values in separate arrays and 'dump' them onto a temp
worksheet to sort them. Once sorted, you can 'dump' them back into
separate arrays to work with if need be. Any value moved from one array
to another should be set to an empty string in the array it was moved
from, so the empty elements get ignored in the sort. So...

Array(16) gets compared to Array(65536).
Found elements get left in.
Not found elements get put in a temp array, and the checked array gets
those elements replaced with "".

Now you have 3 arrays:

Array(16)
Array(65536) with 'not founds' removed
Array(Temp) with not founds

with x1 without x1
--------------------------
x1 -
x1 x2 x2
x1 x3 x3
x1 x4 x4
x1 x2 x3 x2 x3
x1 x2 x4 x2 x4
x1 x3 x4 x3 x4
x1 x2 x3 x4 x2 x3 x4

x2 -
x1 x2 x1
x2 x3 x3
x2 x4 x4
x1 x2 x3 x1 x3
x1 x2 x4 x1 x4
x2 x3 x4 x3 x4
x1 x2 x3 x4 x1 x3 x4

This doesn't display as sorted in my reader. Perhaps you mean...

Block1
x1 -
x1,x2 x2
x1,x3 x3
x1,x4 x4
x1,x2,x3 x2,x3
x1,x2,x4 x2,x4
x1,x3,x4 x3,x4
x1,x2,x3,x4 x2,x3,x4

Block2
x2 -
x1,x2,x1
x2,x3,x3
x2,x4,x4
x1,x2,x3,x1,x3
x1,x2,x4,x1,x4
x2,x3,x4,x3,x4
x1,x2,x3,x4,x1,x3,x4
-OR-
x2 -
x1,x2 x1
x2,x3 x3
x2,x4 x4
x1,x2,x3 x1,x3
x1,x2,x4 x1,x4
x2,x3,x4 x3,x4
x1,x2,x3,x4 x1,x3,x4

...where each array is separated by " ".

Looks like lottery wheeling to me!<g>

 

[Scott]

Hi,

i have a string array which 16 variables viz.,
Array2Compare()=(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16)

there is another array Array2Sort()which already contains 2^16 =65535 combinations for the above 16, viz.,

Array2Sort()
============
Array2Sort(0)=x1
Array2Sort(1)=x2
Array2Sort(2)=x14
Array2Sort(3)=x1 x14
Array2Sort(4)=x1 x10
Array2Sort(5)=x6 x8 x16
Array2Sort(6)=x13 x14 x16
Array2Sort(7)=x2 x5 x14 x16
Array2Sort(8)=x5 x9 x14 x16
Array2Sort(8)=x4 x10 x12 x13
...
...

what i want to do is take each element e.g x1, of the Array2Compare(), search it in Array2Sort(), group all x1 occurrences together in a sorted manner back to Array2Sort().
Also, simultaneously create another array which does not contain occurrences of x1 in it. see below e.g:

I want to have both the arrays grouped and sorted like this in Ascending order.

with x1         without x1
--------------------------
x1              -
x1 x2           x2
x1 x3           x3
x1 x4           x4
x1 x2 x3        x2 x3
x1 x2 x4        x2 x4
x1 x3 x4        x3 x4
x1 x2 x3 x4     x2 x3 x4

x2      -
x1 x2   x1
x2 x3   x3
x2 x4   x4
x1 x2 x3        x1 x3
x1 x2 x4        x1 x4
x2 x3 x4        x3 x4
x1 x2 x3 x4     x1 x3 x4
....
....
so there would be 2 sorted arrays
withX() & withoutX()

my question is:
Can the Array Array2Sort() be grouped & sorted in place without using anyloops?
Has someone attempted something like this and which is very fast?

i think this is very challenging though stumped right now!

This uses loops. However, it may not be in the way you were
thinking. Based on how you have described things you can just
generate a list -- you don't need to filter and sort. If your values
are other than numbers, you can have a separate array of size 16 with
the 16 values sorted and use the following as an index into that
array.

Assumption: Your sample data looks to be sorted (1) by number of
values, then (2) by the values themselves. This functions
recursively.

It's fairly fast if you ignore the test print section.

S

Code:

Option Explicit

Const ArraySize As Long = 4 'Change ArraySize to 16; it's set to 4 for
testing
Const Rows As Long = 2 ^ (ArraySize - 1)

Dim TempArray(1 To ArraySize) As Long
Dim ExcludedValue As Long

'Note that the first value in each row is the number of elements in
that row
Dim WithX(1 To Rows, ArraySize) As Long
Dim WithoutX(1 To Rows, ArraySize) As Long
Dim RowCount As Long

Private Sub GenerateAllCombinations()
Dim i As Long, j As Long

RowCount = 0

'The value you want the split into WithX and WithoutX to be based on
ExcludedValue = 1

For i = 0 To ArraySize - 1
Call GenerateArray(0, 1, i)
Next i

'Test print of WithX ==> Test printing is the slow part
For i = 1 To RowCount
For j = 1 To WithX(i, 0)
Sheet1.Cells(i, j) = WithX(i, j)
Next j
Next i
End Sub

Private Sub GenerateArray(LastPosition As Long, aCurrent As Long,
aMaximum As Long)
'This is the recursive portion.
'
'LastPosition = Last position in the temporary array that got a
value.
'aCurrent = Current number of values in the temporary array.
'aMaximum = Maximum number of values in the temporary array.
Dim i As Long

'Ending condition: Placed the appropriate # of values in the
temporary array, so append it
If aCurrent > aMaximum Then
Call AppendArray
Exit Sub
End If

'Ending condition: Haven't placed all the values, but have reached
the end of the array.
If LastPosition = ArraySize Then Exit Sub

'Loop through the possible locations for the next value
For i = LastPosition + 1 To ArraySize
If i <> ExcludedValue Then
TempArray(i) = 1
Call GenerateArray(i, aCurrent + 1, aMaximum)
TempArray(i) = 0
End If
Next i
End Sub

Private Sub AppendArray()
Dim i As Long
Dim CountWith As Long, CountWithout As Long

CountWith = 0
CountWithout = 0
RowCount = RowCount + 1

For i = 1 To ArraySize
If i = ExcludedValue Then
CountWith = CountWith + 1
WithX(RowCount, CountWith) = i

ElseIf TempArray(i) = 1 Then
CountWith = CountWith + 1
WithX(RowCount, CountWith) = i
CountWithout = CountWithout + 1
WithoutX(RowCount, CountWithout) = i
End If
Next i

WithX(RowCount, 0) = CountWith
WithoutX(RowCount, 0) = CountWithout
End Sub