Heap’s algorithm is used to show all permutations of a given string.
The recursive version (in Python(?)) is:
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n - 1; i += 1 do
generate(n - 1, A)
if n is even then
swap(A(i), A(n-1))
else
swap(A(0), A(n-1))
end if
end for
generate(n - 1, A)
end if
I coded this in Xojo as:
[code]Public Sub Generate(N as Integer, A() as String)
if N = 1 then
exit
else
for I as Integer = 0 to N - 1
Generate(N - 1, A)
if Even(N) then
Swap(A(i), A(N-1))
else
Swap(A(0), A(N-1))
end if
next
Generate(N - 1, A)
end if
End Sub
[/code]
N = length of the array
A = array holding string (every element is a character)
[code]Public Sub Swap(firstElement as String, secondElement as String)
dim tempElement as String
tempElement = firstElement
firstElement = secondElement
secondElement = tempElement
End Sub
[/code]
Public Function Even(N as Integer) as Boolean
if ( N Mod 2 ) = 1 then
return false
else
return true
end if
End Function
If I run the code with ‘abcd’ I get:
‘abcd’
‘abcd’
‘bcd’
‘cd’
‘d’
it should give
‘abcd’
‘abdc’
‘acbd’
‘acdb’
‘bacd’
etc… every possible permutation. So somewhere the array gets truncated… but I can’t figure out where. Anybody?
There’s also a non-recursive version:
[code]Public Sub Generate1(N as Integer, A() as String)
dim C(-1) As Integer
for i as Integer = 0 to N
c.Append(i)
next
dim i as Integer = 0
while i < N
if c(i) < i then
if even(i) then
Swap(A(0), A(i))
else
Swap(A(c(i)), A(i))
end if
c(i) = c(i+1)
i = 0
else
c(i) = 0
i = i+1
end if
wend
End Sub
[/code]
This gives me the same results. I can post the project if you want.