Heap's algorithm

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.

Your Swap function doesn’t actually do anything. :slight_smile:

Also, you can do this:

Public Function Even(N as Integer) as Boolean
  return ( N mod 2 ) = 0
End Function
Public Sub Swap(byref firstElement as String, byref secondElement as String)
  dim tempElement as String
  
  tempElement = firstElement
  firstElement = secondElement
  secondElement = tempElement
  
  
End Sub

Your Swap method doesn’t work the way you think. In order to return the swapped parameters to the caller you need to declare them as byref. However, you can’t pass array elements as byref parameters.

Change your Swap routine like this:

Public Sub Swap (myArray() as String, firstIndex as Integer, secondIndex as Integer)

dim temp as String

temp = myArray(firstIndex) // ignoring bounds checking here...
myArray(firstIndex) = myArray(secondIndex) // ditto
myArray(secondIndex) = temp

End Sub

And call it like this:

Swap(A, 0, i)

ah… didn’t notice he passed array values… I just took the routine “as-is” :slight_smile:

Ah! I wrote the swap function without giving it much thought. Couldn’t be that hard… :slight_smile: I will try again. Many thanks you all.

Ps the Even function was written by Norman.