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.