# Heap's algorithm

**URL:** <https://forum.xojo.com/t/heaps-algorithm/37912>\
**Category:** General\
**Created:** [May 30, 2017, 1:46pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912 "2017-05-30T13:46:45Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Alexander\_van\_der\_Linden](https://forum.xojo.com/user_avatar/forum.xojo.com/alexander_van_der_linden/32/323_2.png) [@Alexander\_van\_der\_Linden](https://forum.xojo.com/u/Alexander_van_der_Linden)\
**Post date:** [May 30, 2017, 1:46pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/1 "2017-05-30T13:46:45Z")

</div>

Heap’s [algorithm](https://en.wikipedia.org/wiki/Heap%27s_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.

---

<div class="post-metadata">

**Author:** ![Kem\_Tekinay](https://forum.xojo.com/user_avatar/forum.xojo.com/kem_tekinay/32/154_2.png) [@Kem\_Tekinay](https://forum.xojo.com/u/Kem_Tekinay)\
**Post date:** [May 30, 2017, 4:15pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/2 "2017-05-30T16:15:36Z")

</div>

Your Swap function doesn’t actually do anything. 🙂

Also, you can do this:

```auto
Public Function Even(N as Integer) as Boolean
  return ( N mod 2 ) = 0
End Function
```

---

<div class="post-metadata">

**Author:** ![DaveS](https://forum.xojo.com/letter_avatar_proxy/v4/letter/d/848f3c/32.png) [@DaveS](https://forum.xojo.com/u/DaveS)\
**Post date:** [May 30, 2017, 4:17pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/3 "2017-05-30T16:17:46Z")

</div>

```auto
Public Sub Swap(byref firstElement as String, byref secondElement as String)
  dim tempElement as String
  
  tempElement = firstElement
  firstElement = secondElement
  secondElement = tempElement
  
  
End Sub
```

---

<div class="post-metadata">

**Author:** ![Urs\_Geiser](https://forum.xojo.com/user_avatar/forum.xojo.com/urs_geiser/32/2152_2.png) [@Urs\_Geiser](https://forum.xojo.com/u/Urs_Geiser)\
**Post date:** [May 30, 2017, 4:19pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/4 "2017-05-30T16:19:09Z")

</div>

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:

```auto
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:

```auto
Swap(A, 0, i)
```

---

<div class="post-metadata">

**Author:** ![DaveS](https://forum.xojo.com/letter_avatar_proxy/v4/letter/d/848f3c/32.png) [@DaveS](https://forum.xojo.com/u/DaveS)\
**Post date:** [May 30, 2017, 4:23pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/5 "2017-05-30T16:23:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Alexander\_van\_der\_Linden](https://forum.xojo.com/user_avatar/forum.xojo.com/alexander_van_der_linden/32/323_2.png) [@Alexander\_van\_der\_Linden](https://forum.xojo.com/u/Alexander_van_der_Linden)\
**Post date:** [May 30, 2017, 7:43pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/6 "2017-05-30T19:43:20Z")

</div>

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

Ps the Even function was written by Norman.

---

<div class="post-metadata">

**Author:** ![system](https://forum.xojo.com/uploads/default/original/1X/455b4dcc0e61630e9f81940004ddffa49c432a46.png) [@system](https://forum.xojo.com/u/system)\
**Post date:** [October 29, 2020, 6:47pm UTC](https://forum.xojo.com/t/heaps-algorithm/37912/7 "2020-10-29T18:47:29Z")

</div>


