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.
Live long & prosper.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
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...
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
Last edited by chrisf; Aug 31st, 2001 at 04:09 AM.
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?
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.
The Dinosaur from prehistoric era prior to computers.
Eschew obfuscation!
If a billion people believe a foolish idea, it is still a foolish idea!
VB.net 2010 Express
64Bit & 32Bit Windows 7 & Windows XP. I run 4 operating systems on a single PC.
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.
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.
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.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Reply With Quote
