Combinations
in [Visual Basic]
|
Prev: Tom Shelton ...
Next: Instr problem in VB5
From: Shell on 2 Jun 2010 11:28 In VB6 I have an application where I have 7 characters (numbers and/or letters). I need to generate a list (probably in a database) on all possible combinations of 3, 4, 5, 6, and 7 characters. I keep getting mixed up, trying recursive functions, which I hate. Does anyone have a simpler way of doing this? Thanks -- Shell
From: dpb on 2 Jun 2010 11:52 Shell wrote: > In VB6 I have an application where I have 7 characters (numbers and/or > letters). I need to generate a list (probably in a database) on all possible > combinations of 3, 4, 5, 6, and 7 characters. > > I keep getting mixed up, trying recursive functions, which I hate. Does > anyone have a simpler way of doing this? I got the last one... ;) How about... >> nchoosek([1:7],7) ans = 1 2 3 4 5 6 7 >> nchoosek([1:7],6) ans = 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 >> nchoosek([1:7],5) ans = 1 2 3 4 5 1 2 3 4 6 1 2 3 4 7 1 2 3 5 6 1 2 3 5 7 1 2 3 6 7 1 2 4 5 6 1 2 4 5 7 1 2 4 6 7 1 2 5 6 7 1 3 4 5 6 1 3 4 5 7 1 3 4 6 7 1 3 5 6 7 1 4 5 6 7 2 3 4 5 6 2 3 4 5 7 2 3 4 6 7 2 3 5 6 7 2 4 5 6 7 3 4 5 6 7 >> nchoosek([1:7],4) ans = 1 2 3 4 1 2 3 5 1 2 3 6 1 2 3 7 1 2 4 5 1 2 4 6 1 2 4 7 1 2 5 6 1 2 5 7 1 2 6 7 1 3 4 5 1 3 4 6 1 3 4 7 1 3 5 6 1 3 5 7 1 3 6 7 1 4 5 6 1 4 5 7 1 4 6 7 1 5 6 7 2 3 4 5 2 3 4 6 2 3 4 7 2 3 5 6 2 3 5 7 2 3 6 7 2 4 5 6 2 4 5 7 2 4 6 7 2 5 6 7 3 4 5 6 3 4 5 7 3 4 6 7 3 5 6 7 4 5 6 7 >> nchoosek([1:7],3) ans = 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 3 4 1 3 5 1 3 6 1 3 7 1 4 5 1 4 6 1 4 7 1 5 6 1 5 7 1 6 7 2 3 4 2 3 5 2 3 6 2 3 7 2 4 5 2 4 6 2 4 7 2 5 6 2 5 7 2 6 7 3 4 5 3 4 6 3 4 7 3 5 6 3 5 7 3 6 7 4 5 6 4 5 7 4 6 7 5 6 7 >> Ain't Matlab useful sometimes???? :) --
From: dpb on 2 Jun 2010 13:03 dpb wrote: > Shell wrote: .... >> ...need a list of all possible combinations of 3, 4, 5, 6, and 7 >> characters from seven. >> >> I keep getting mixed up, trying recursive functions, which I hate. >> Does anyone have a simpler way of doing this? > > I got the last one... ;) > > How about... > > >> nchoosek([1:7],7) > ans = > 1 2 3 4 5 6 7 > >> nchoosek([1:7],6) > ans = > 1 2 3 4 5 6 > 1 2 3 4 5 7 .... > 3 5 6 7 > 4 5 6 7 > >> nchoosek([1:7],3) > ans = > 1 2 3 .... > 4 6 7 > 5 6 7 > >> > > Ain't Matlab useful sometimes???? :) > > -- Here's a recursive solution, in Matlab. I've added some comments to the Matlab code to aid in converting it if you wish to do the generation on the fly rather than use the results stored as lookup tables. Assuming you have a string, the above can be used iteratively as the index vectors into the string to select the various combinations as desired. function P = combs(v,m) In Matlab, the syntax for a function is that the return value is the variable following the keyword function. "Vector" is synonymous w/ 1D array and "row/column" have same orientation as does VB (column-major storage order) %COMBS All possible combinations. % COMBS(V,M) where V is a row vector of length N, % creates a matrix with N!/((N-M)! M!) rows and M columns containing % all possible combinations of N elements taken M at a time. % % This function is only practical for situations where M is less % than about 15. if nargin~=2, error('Requires 2 input arguments.'); end v = v(:).'; % Make sure v is a row vector. n = length(v); % == UBound-LBound+1 if n == m % the select 'em all case P = v; elseif m == 1 % the other extreme of only one at a time % return n rows w/ one element each % your case won't ever use this as you said m>2 P = v.'; else % all the rest... P = []; % starts w/ empty array... if m < n & m > 1 % culls out the possible erroneous input for k = 1:n-m+1 Q = combs(v(k+1:n),m-1); The [ ] enclose an array expression in Matlab. This will have to be expanded into a nested loop in VB. The semicolon concatenates the following expression as the next row in the array P. Reading the expression [v(ones(size(Q,1),1),k) Q] from inside out, size(Q,1) is the number of rows in Q this iteration (size of first dimension of Q), we'll temporarily call it nRows. Then ones(nRows,1) returns a 1D column array of ones and so v(ones(nRows,1),k) is v(1,k) for each pass thru the loop. This value is then concatenated onto the row. P = [P; [v(ones(size(Q,1),1),k) Q]]; end end end Enjoy!!! :) I've gotta' run at the moment; if have some time later on maybe I'll see about translating it (but no promises, have some other commitments)... --
From: Mike S on 3 Jun 2010 01:16 On 6/2/2010 8:28 AM, Shell wrote: > In VB6 I have an application where I have 7 characters (numbers and/or > letters). I need to generate a list (probably in a database) on all possible > combinations of 3, 4, 5, 6, and 7 characters. > > I keep getting mixed up, trying recursive functions, which I hate. Does > anyone have a simpler way of doing this? > > Thanks Avoiding recursion I think you can do it this way, to keep it simple you can use a separate sub for each different length string, how does this look? Using this approach, to make a string 4 chars long you could use a new variable n, etc. for longer strings. Is this what you were looking for? Option Explicit Private chars() As String, results() As String Private Sub btnMakeString3_Click() On Error GoTo btnMakeString3Err Dim j As Long, k As Long, m As Long, ctr As Long ctr = 1 ReDim results(1 To 7 ^ 3) Text1.Visible = False Text1.Text = "" For j = 1 To 7 For k = 1 To 7 For m = 1 To 7 results(ctr) = chars(j) & chars(k) & chars(m) Text1.Text = Text1.Text & results(ctr) & vbCrLf ctr = ctr + 1 Next Next Next Text1.Visible = True DoEvents Exit Sub ' btnMakeString3Err: MsgBox "Error " & Err.Number & " " & Err.Description End Sub Private Sub Form_Load() ReDim chars(1 To 7) chars(1) = "0" chars(2) = "1" chars(3) = "2" chars(4) = "3" chars(5) = "4" chars(6) = "5" chars(7) = "6" End Sub
From: dpb on 2 Jun 2010 19:54
dpb wrote: .... I haven't had (or more correctly, taken the time :) ) to work on an actual translation -- I'll have to think about how to even cast it as VB for a little I think, but... Look at what's left out each step and maybe that'll give you a head start in working out a procedural way... Ovbiously n-of-n has only one solution and n-1 of n is leaving out one element from 1:n so those are trivial. So, let's look at the next, n-2 out of n-- > >> nchoosek([1:7],5) > ans = % Omitted values > 1 2 3 4 5 % 6 7 > 1 2 3 4 6 % 5 7 > 1 2 3 4 7 % 5 6 > 1 2 3 5 6 % 4 7 > 1 2 3 5 7 % 4 6 > 1 2 3 6 7 % 4 5 > 1 2 4 5 6 % 3 7 > 1 2 4 5 7 % 3 6 > 1 2 4 6 7 % 3 5 > 1 2 5 6 7 % 3 4 > 1 3 4 5 6 % 2 7 > 1 3 4 5 7 % 2 6 > 1 3 4 6 7 % 2 5 > 1 3 5 6 7 % 2 4 > 1 4 5 6 7 % 2 3 > 2 3 4 5 6 % 1 7 > 2 3 4 5 7 % 1 6 > 2 3 4 6 7 % 1 5 > 2 3 5 6 7 % 1 4 > 2 4 5 6 7 % 1 3 > 3 4 5 6 7 % 1 2 > >> nchoosek([1:7],4) > ans = > 1 2 3 4 % 5 6 7 > 1 2 3 5 % 4 6 7 > 1 2 3 6 % 4 5 7 > 1 2 3 7 % 4 5 6 > 1 2 4 5 % 3 6 7 > 1 2 4 6 % 3 5 7 > 1 2 4 7 % 3 5 6 > 1 2 5 6 % 3 4 7 > 1 2 5 7 % 3 4 6 > 1 2 6 7 % 3 4 5 .... Begin to see the pattern emerging? BTW, the number for each is, as the code comments say, N!/[(N-K)! K!] which for an example if you don't recall factorials C(7,3) = 7!/[(7-3)! 3!] = 7!/[4! 3!] = [7x6x5x4!]/[4! 3!] = 7x6x5/3! = (7x6x5)/(3x2x1) = 7x5 = 35 A VB routine to calculate the number based on the Pascal's triangle method is Function BinomCoef(n As Long, k As Long) As Long ' Binomial coefficient. ' BINOMCOEF(N,K) where N and K are non-negative integers returns ' N!/K!(N-K)!. ' This is the number of combinations of N things taken K at a time. Dim c As Double Dim i As Long, j As Long If k > n / 2 Then k = n - k End If If k <= 1 Then BinomCoef = n ^ k Return End If c = 1# j = 1 For i = n - k + 1 To n c = c * i / j j = j + 1 Next i BinomCoef = c End Function That'll at least tell you if you got 'em all... :) -- |