Home > Software engineering >  Generate Permutations using Heap's Algorithm
Generate Permutations using Heap's Algorithm

Time:01-02

I am trying to generate all permutations for an array using the Heap's algorithm that I found in wikipedia.

This is what I tried so far:

n <- 3
array <- c(1, 2, 3)
perm <- function(n, array) {
  if (n == 1)
    print(perm)
  for (i in length(array))
    perm(n, array - 1) 
  if (array %% 2 == 1) {
    swap(array[i], array[n - 1])
  } else {
    swap(array[0], array[n - 1])
  } 
}
perm(3, array)

The output is not showing, and it would be great to receive some help.

CodePudding user response:

To implement Heap's algorithm in R, this should work:

h <- function(s, n) {
  ## processes Heap's algorithm
  if (n == 1L) {
    print(s)
  } else {
    h(s, n - 1L)
    for (i in 1:(n - 1L)) {
      if (n %% 2L == 0L) {
        j <- 1L
      } else {
        j <- i
      }
      tmp <- s[n]
      s[n] <- s[j]
      s[j] <- tmp
      h(s, n - 1L)
    } 
  }
}

hperm <- function(A) {
  ## wrapper
  h(A, length(A))
}

A <- 0:2
hperm(A)
# [1] 0 1 2
# [1] 1 0 2
# [1] 2 1 0
# [1] 1 2 0
# [1] 2 0 1
# [1] 0 2 1

Mainly, you mixed up array and n in the conditions (and swap() doesn't exist in basic R installation).

See also: This Python code of Heap's algorithm on Stack Overflow.

  • Related