Printable View
Suppose I have an array called arMain:
Dim arMain(1000) as String
and each element contains one character:
arMain(0)="a"
arMain(1)="b"
arMain(2)="c"
arMain(3)="d"
...etc...
I want to concatenate the elements to get, firstly strings of length one, then two etc. With the above letters I would get:
a
b
c
d
aa
ab
ac
ad
ba
bb
bc
bd
ca
cb
cc
cd
da
db
dc
dd
abc
abd
acb
acd
adb
adc
...etc...
An algorithm please?
There is probably an algorithm, but you do not have the time to run the job after you program it.
You are describing the generation of all permutations of 1000 objects. The formula is 1000! / (1000 - N)! The first few values are as follows.
1000
999,000
997,002,000
994,010,994,000
9.9003495E14
9.85084775E17
9.791743E20
At a nanosecond per permutation, the last bunch of permutations would require over 31,000 years if you could generate one permutation per nanosecond. The last is permutations of 1000 objects taken 7 at a time.
I know an algorithm for generating all permuations of N objects. The above task would require an algorithm for generating combinations to each of which you would apply the permutation algorithm. Generating permutations would take most of the time.
Off hand, I do not know of any algorithm for generating combinations, but it should be easy to develop one.
Since You cannot possibly expect to cope with more than 20-30 objects, I would use strings of characters instead of arrays. The Mid Function and Mid Statement can be used to operate on strings.
The most efficient permutation algorithm uses half exchanges to change one string into another.
Hi
After rereading ur qtn and Guv's answer i see that my answer was prob not what u were after. I guess that u are asking for a way to count in base 1000 yet ur example shows counting in base 4. So i am not sure if this will help but anyhow here goes...
RegardsVB Code:
Stuart
Here is the algorithm, but as Guv said I wouldn't try and run it with a string of 1000 characters :eek:
VB Code:
Example usage, note you can pass any length string and output is to the debug window:
Code:Private Sub Command1_Click()
Call Combinations("abc")
End Sub
If you have an array of 1000 elements, this function will return any one of the 1000! / (1000 - N)! possible permutations.
Code:Function FindLetters(Letters() As String, ByVal index As Long) As String
'Letters() contains the strings you wish to work with.
'If Letters(0)="a"
' '
' '
'Letters(25)="z" then:
' this function returns the (index)th combination of letters
' ie index=1 returns "a"
' index=4 returns "d"
' index=27 returns "aa"
Dim elements As Long, tmpindex As Long, nxtlet As Long
elements = UBound(Letters()) + 1
'zero based array
tmpindex = index - 1
'build return string
'need to work backwards (add last letter first)
Do Until tmpindex < 0
nxtlet = tmpindex Mod elements
FindLetters = Letters(nxtlet) & FindLetters
tmpindex = ((tmpindex - (nxtlet)) / (elements)) - 1
Loop
End Function
Cheers guys. I'll work with these algorithms and let u kno how i get on.
As regards 1000 elements: I just said a large number to get the message across that I couldn't use inline code.
Will get back to u guys tomoz. And trust me, no arrays of 1000 chars!
/dh/
There are actually more than 1000! permutations. There would be 1000! if you were looking at all permutations of those 1000 characters. However, David asked for all permutations of 1 to 1000 characters allowing each character to be repeated...
i.e. if you have abc this is 3! for all permutations of abc = 6
abc
acb
bca
bac
cab
cba
However, David asked for many more than 3!:
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc
What is the mathematical formula for what David asked for?
sum(i = 1 to n, n^i) = n^1 + n^2 + .... + n^nQuote:
What is the mathematical formula for what David asked for?
at least, thats what you described, I didn't check if you described correctly what D. asked for. But I see no reason to doubt ;)
Banij
Ya :)Quote:
Originally posted by banij
sum(i = 1 to n, n^i) = n^1 + n^2 + .... + n^n
at least, thats what you described, I didn't check if you described correctly what D. asked for. But I see no reason to doubt ;)
Banij
To find put all the different permutations of an array of n strings into a listbox:
'strings are stored in Letters()
n=Ubound(Letters())+1
'find number of permutations
For i = 1 To n
nsum = nsum + n^i
Next
'call the FindLetters function I posted earlier
For i = 1 To nsum
perm = FindLetters(Letters(), i)
listbox.AddItem perm
Next
The original post was unclear. For groups of two, it indicated that repetitions were required, while for groups of three, it did not indicate repetitions.
The following formula posted by Banji is correct if repetitions are allowed.
Sum(N^k) for k = 1 to N, which is N + N^2 + N^3 +N^4 et cetera. for N = 1000, this is huge beyond my ability to imagine it. The first few terms are as follows.
1000
1,000,000
1,000,000,000
1,000,000,000,000
If repetitions not allowed, the formual would be the following.
Sum(1000!/1000 - k)! for k = 1 to 1000, which is much smaller, but still huge beyond my ability to imagine it. The first few terms are the following.
1000
999,000
997,002,000
994,010,994,000
9.9003495E14
9.85084775E17
9.791743E20
The formula for the number of permutations originally posted by Banij:
sum(i = 1 to n, n^i) = n^1 + n^2 + .... + n^n
is a geometric series and can be expressed as:
n * (1 - n^n)/(1 - n)
so to fill a listbox with all possible permutations of the contents of the array Letters() you can use the following code:
'strings are stored in Letters()
n=Ubound(Letters())+1
'find number of permutations
NoOfPerms = n * (1 - n^n)/(1 - n)
'call the FindLetters function I posted earlier
For i = 1 To NoOfPerms
perm = FindLetters(Letters(), i)
listbox.AddItem perm
Next
This works regardless of the number of elements in Letters(), providing you don't have so many that you cause an overflow.
One more thing,
sum(i = 1 to n, n^i) = n^1 + n^2 + .... + n^n
Works where all letters are unique. This formula does not work it some elements are repeted.
Eg. If I have aaa I do not get 39 permuatations only 1, so what is the formula if we account for some characters being repeted?
before finding all permutations, eliminate all duplilcate entries.Quote:
Works where all letters are unique. This formula does not work it some elements are repeted.
Eg. If I have aaa I do not get 39 permuatations only 1, so what is the formula if we account for some characters being repeted?
If you sort the array first then any duplications will be grouped, so finding them will be faster. If you are going to eliminate character repetition then using a collection rather than an array would make things easier.
btw here's an algoritm i wrote for that matter
http://forums.vb-world.net/showthrea...ght=duplicates
For example if I have aab, I want the formula for number of unique permutations.
In this case I have 14 permutations:
a
aa
aaa
aac
ac
aca
acc
c
ca
caa
cac
cc
cca
ccc
So what is the formula, not the algorithm, for determining number of unique permutations?
ah that kind of permutations, well it gets complicated..
å(d=0 to F)[Õ(n=0 to d)[ Z-å(k=0 to n)[Xk] C Xn]]
F is the amount of types of characters used
Z is the amount of characters used
Xa is the a'th type of character times used
If you have n different characters with d duplicates and allow permutations of upto n+d characters, then
unique permutations
= [n * (1 - n^n)/(1 - n)] +[n^(n + d) * (1 - n^(n + d))/(1-n) ]
= [n * (1 - n^n)] +[n^(n + d) * (1 - n^(n + d))]/(1 - n)
however, it's getting late and I've had a couple of beers so I would check the formula above before using it.
Also, geting back to DavidHooper's original question, I've attatched an short example of a solution.
And here is the attachment.