Talk:Heap's algorithm

Fix needed

This article needs to be enhanced. It looks like this algorithm is a good solution to the problem. It is quite nice that it is short and works, and in 1963 it was most important to reduce complexity and memory consumption. But if you look what it does (the picture is very helpful with that) it is quite weird and does lots of unnecessary swaps. So, the pro and contra, and other algorithms like Steinhaus–Johnson–Trotter algorithm should be mentioned. 5.146.194.61 (talk) 14:53, 8 October 2014 (UTC)[reply]

Please fix it! Feel free to add at least a "see also" section that links to the other algorithm, and if you have source that compares algorithms, be sure to cite it. QVVERTYVS (hm?) 09:34, 9 October 2014 (UTC)[reply]

An Implementation in Javascript

Array.prototype.swap = function (x, y) {
  var tmp = this[x]; this[x] = this[y]; this[y] = tmp;
  return this;
}

function perm(arr, n) {
    n = n == undefined ? arr.length : n; // n defaults to array length
    if (n == 0) {
        console.log(arr); // output in browser console (open with F12)
        return;
    }
    
    for (var i = 0; i < n; i++) {
        perm(arr, n-1);
        arr.swap(n % 2? 0 : i, n-1);
    }
}

perm([1,2,3]); // print all permutations of [1,2,3]
perm("abcd".split('')); // print all permutations of "abcd"

(I don't understand why this example - which could be very useful for other developers and saves them a lot of time - was removed. But if it bloats the article too much...maybe it could be saved at least here for others.)

JS Implementation from another user: I implemented this algorithm in Javascript based on the pseudocode from this article, as closely as possible. I had found the algorithm a little difficult to understand without a working implementation, & hope this can help others. I didn't add this link to the Article itself, to avoid violating WP:NOR. http://dsernst.com/2014/12/14/heaps-permutation-algorithm-in-javascript/ Thanks! --dsernst (talk) 09:52, 4 January 2015 (UTC)[reply]

Incorrect algorithm

The extra swaps stem from swapping in the last iteration of the for loop, are not a part of Heap's algorithm. I compared with Sedgewick (1977). I will correct the article, but this means that the nice illustration is out of date, and will be removed. sverdrup (talk) 11:48, 29 June 2015 (UTC)[reply]

The last edit to the algorithm itself (where the range of iteration has been changed from [0,n-1] to [0,n-2]) did not work, so I changed it back to [0,n-1].

I have no access to the Sedgewick 1977 paper, but according to the other 'paper'(more like presentation) the genuine range is [0,n-1]. — Preceding unsigned comment added by 5.43.65.114 (talk) 22:41, 18 August 2015 (UTC)[reply]

There have been some edits to the given algorithm, and it seems we've been through these edits before.

This edit, which deleted the second call to generate did not do enough permutations. I reverted. A similar edit was reverted previously.[1]

This edit, which added another iteration to the for loop, does too many permutations. It would do the right number of permutations if the second call to generate were removed (and produces Sedgewick's variation below). However, that brings us back to Sverdrup's comment that the algorithm performs extra swaps. (If n is even, it's a null swap, but if odd, it's a real swap.) The characteristic that Heap's paper desired was exactly one swap between successive permutations: "Methods for obtaining all possible permutations of a number of objects, in which each permutation differs from its predecessor only by the interchange of two of the objects, are discussed."

At stage n, it takes only n−1 swaps to place all n objects at the last position. The routine should only do n−1 iterations.

Sedgewick's talk (which uses 1-based arrays), article reference 3, ignores that issue, so his version is a variation of Heap's algorithm.

Glrx (talk) 17:57, 7 February 2016 (UTC)[reply]

Correct non recursive Algorithm

The non recursive implementation of Heap's algorithm proposed in the link number 3 (Sedgewick's pdf) can't work. It seems plagued by, really, a lot of errors or typos. Meanwhile, using the ideas of the link one can get a working implementation. Unfortunately the one I get is much less stylish, not even mentioning time efficiency.

// doit() is whatever shall be done with a new permutation of the N elements of table t
void exchange(int *t,int n, int i,int j){
  int b;
  b = t[i]; t[i] = t[j]; t[j] = b;
}
void permutate(int*t, int N){
  int n,i,j;
  int c[N],tt[N];
  for(i=0; i<N; i++){
    c[i] = 0; tt[i] = t[i];}
  for(j=0;j<N;j++) {exchange(t,N,j,c[j]);}
  //doit();
  for(i=1;i<N;){
    if(c[i] < i){
      c[i]++; i=1; 
      for(j=0;j<N;j++) {t[j] = tt[j];}
      for(j=0;j<N;j++) {exchange(t,N,j,c[j]);}
      //doit();
    } else {
      c[i++] = 0;
    }
  }
}

— Preceding unsigned comment added by 192.93.101.133 (talk • contribs) 11:44 6 January 2016