Hi. Here's another way. Note that in your example, we assume the size of
the subset from the given array of values. (we don't supply the '6).
We do have to give the size of the set though.
Sub TestYourData()
'//Easy Test (1)
Debug.Print RankKSubset(9, 1, 2, 3, 4, 5, 6)
'// Other easy test...
Debug.Print RankKSubset(9, 4, 5, 6, 7, 8, 9)
Debug.Print [Combin(9,6)]
Debug.Print RankKSubset(50, 1, 7, 23, 35, 47, 49)
Debug.Print RankKSubset(20, 1, 2, 3, 4, 5, 19)
Debug.Print RankKSubset(20, 1, 2, 3, 4, 5, 14)
End Sub
Function RankKSubset(Size, ParamArray v())
'//= = = = = = = = = = = = = = = = = =
'// By: Dana DeLouis
'//= = = = = = = = = = = = = = = = = =
Dim j As Long
Dim d As Double
Dim n As Double
Dim m As Double
Dim T As Double
With WorksheetFunction
m = Size
n = UBound(v) + 1
d = v(0)
T = T + .Combin(m, n) - .Combin(m - d + 1, n)
For j = 1 To UBound(v) - 1
m = m - d
n = n - 1
d = v(j) - v(j - 1)
T = T + .Combin(m, n) - .Combin(m - d + 1, n)
Next j
T = T + v(j) - v(j - 1)
End With
RankKSubset = T
End Function
To convert a number to a subset, we need to supply both the size of the set,
and the size of the subset.
So, in our example of 50 & 6, we note that if our number falls within
=COMBIN(49,5) = 1906884
then our first digit is 1.
If n is greater than this, then we add =COMBIN(48,5) = 1712304
If n falls within this new number, then the first number is 2...etc
We have to do these short loops because there is no analytical way to
directly solve the binomial sum (afaik)
As a side note, when your size gets too large, it can sometimes be more
efficient to call a NextPermutation routine
I've done this before, but I can't find it at the moment.
The reason for this is that if you had a size 1000, and a subset size of 14,
then this exceeds Excel's extended capabilities.
For example, if you had this size 14 subset out of 1,000:
{2, 39, 140, 230, 262, 341, 443, 558, 612, 661, 674, 705, 804, 839}
then it would be the
202,646,961,038,399,155,876,623,226,251
'th item in the list.
This slightly exceeds Excel's extended capabilities.
Hence, it is usually faster to work with the smaller array.
--
Dana DeLouis
thank you for your reply
I think that you are right
"I believe the Op is asking for the "Rank"
I will want the way simplest to have the Rank
ex: combin(20,6)
(1,2,3,4,5,19) rank is 14
(1,2,3 4,5,14) rank is 9
how to have it and use the functions RankKSubset UnrankKSubs
and they are not in Excel
I believe the Op is asking for the "Rank"
n = RankKSubset[{1, 7, 23, 35, 47, 49}, s] + 1
926,277
(ie it's the 926,277 item in the list)
and then wanting to "UnRank" it.
UnrankKSubset[n, 6, s]
{1, 7, 23, 35, 47, 50}
Again, I may be wrong.
--
Dana DeLouis
<snip>Joel a écrit :
Ther was no error in my code. I wasn't sure if the PST wanted 2 to the N
combinitions or PST was looking for N! (factorial) permutations. Sinced
you asked for permutations here is the modified code. It looks very
similar except I do a check to make sure the number isn't used more than
once.
P.S. I was expecting somebody to respond with the question why were the
numbers appearing twice. A couple of weeks ago somebody posted a
requested for permutations, so I knew exactly how to make the changes
before the question was asked.
Const Forward As Integer = 0
Const Reverse As Integer = 1
Public MyNumbers() As Variant
Public SearchArray() As Variant
Public combinationArray() As Variant
Public ArraySize As Integer
Public LowerLimit As Double
Public UpperLimit As Double
Sub test()
Dim index As Long
Dim ComboNo As Double
MyNumbers = Array(1, 6, 7, 23, 35, 47, 49, 50)
SearchArray = Array(50, 6, 1, 7, 23, 35, 47, 49)
ArraySize = UBound(MyNumbers)
ReDim combinationArray(ArraySize)
index = 0
level = 0
StartIndex = CombinationToIndex(Forward, level, index)
LowerLimit = StartIndex
UpperLimit = StartIndex + 99#
index = 0
level = 0
StartIndex = CombinationToIndex(Reverse, level, index)
End Sub
Function CombinationToIndex(Mode, level, ByRef index As Long)
For i = 0 To ArraySize
found = False
For n = 0 To (level - 1)
If combinationArray(n) = i Then
found = True
Exit For
End If
Next n
If found = False Then
combinationArray(level) = i
If level = ArraySize Then
If Mode = Forward Then
'check if search value was found
found = True
For j = 0 To ArraySize
If SearchArray(j) <> _
MyNumbers(combinationArray(j)) Then
found = False
Exit For
End If
Next j
If found = True Then
CombinationToIndex = index
Exit For
Else
CombinationToIndex = -1
End If
Else
If index >= LowerLimit Then
For k = 0 To ArraySize
If k = 0 Then
PrintString = _
CStr(MyNumbers(combinationArray(k)))
Else
PrintString = PrintString & "," & _
CStr(MyNumbers(combinationArray(k)))
End If
Next k
MsgBox (PrintString)
If index = UpperLimit Then
CombinationToIndex = 0
Exit For
Else
CombinationToIndex = -1
End If
Else
CombinationToIndex = -1
End If
End If
index = index + 1
Else
CombinationToIndex = _
CombinationToIndex(Mode, level + 1, index)
End If
If CombinationToIndex <> -1 Then
Exit For
End If
End If
Next i
End Function
Dana DeLouis said:
Hi. Here are your first 6 outputs:
50,6,1,7,23,35,47,49
50,6,1,7,23,35,47,50
50,6,1,7,23,35,49,1
50,6,1,7,23,35,49,6
50,6,1,7,23,35,49,7
50,6,1,7,23,35,49,23
I may be wrong, but I think there is a logic error in the code.
I read the op's question as being that from a set of s=50, and Subsets of
size 6,
find the next Subset in Lexicographical order.
(Using another program, the next Subset appears correct:
NextKSubset[s, {1, 7, 23, 35, 47, 49}]
{1, 7, 23, 35, 47, 50}
But your third one is a little off.
NextKSubset[s, %]
{1, 7, 23, 35, 48, 49}
Also note that your 6th output has two "23's", which can not be part of a
Subset in this context.
I believe the Op is asking for the "Rank"
n = RankKSubset[{1, 7, 23, 35, 47, 49}, s] + 1
926,277
(ie it's the 926,277 item in the list)
and then wanting to "UnRank" it.
UnrankKSubset[n, 6, s]
{1, 7, 23, 35, 47, 50}
Again, I may be wrong.
