# Storing all index permutations with Heap's algorithm

**URL:** https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326
**Category:** Coding Questions
**Created:** [July 2, 2020, 4:02pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326 "2020-07-02T16:02:50Z")
**Posts on this page:** 7
**Page:** 1

<div class="post-metadata">

### Author: ![hsolatges](https://avatars.discourse-cdn.com/v4/letter/h/6bbea6/32.png) [@hsolatges](https://discourse.processing.org/u/hsolatges)
#### Post date: [July 2, 2020, 4:02pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/1 "2020-07-02T16:02:51Z")

</div>

Hi, I am new on _Processing_ and I am struggling with Java.  
I am trying to use [Heap’s algorithm](https://en.wikipedia.org/wiki/Heap%27s_algorithm#Details_of_the_algorithm) to get the list of all the permutations of numbers.  
I want to store that list so I wan use it as a matrix for animation.

I have tried many different ways and types but I can’t fill it correctly.  
As I am stuck, I would appreciate some help.

Here what I have:

```auto
// https://en.wikipedia.org/wiki/Heap%27s_algorithm#Details_of_the_algorithm
void heapPermutations(int k, IntList l, ArrayList<IntList> a) { 
  if (k == 1) {
    a.add(l); // Side effect : current permutation storage
    printArray(l); // For testing purposes
    println("--");
  } else {
    heapPermutations(k-1, l, a);
    
    for (int i=0; i<k-1; i++) {
      if (k % 2 == 0) {
        swapInt(i, k-1, l);
      } else {
        swapInt(0, k-1, l);
      }
      heapPermutations(k-1, l, a);
    }
  }
};

```

To store the stuff, I wrote that :

```auto
  IntList base = new IntList(0, 1, 2);
  ArrayList<IntList> permutations = new ArrayList<IntList>(factorial(base.size()));
  heapPermutations(base.size(), base, permutations);
  for(IntList perm : permutations) {
    printArray (perm);
  }

```

**Current output:**

```auto
IntList size=3 [0, 1, 2]
--
IntList size=3 [1, 0, 2]
--
IntList size=3 [2, 0, 1]
--
IntList size=3 [0, 2, 1]
--
IntList size=3 [1, 2, 0]
--
IntList size=3 [2, 1, 0]
--
IntList size=3 [2, 1, 0]
IntList size=3 [2, 1, 0]
IntList size=3 [2, 1, 0]
IntList size=3 [2, 1, 0]
IntList size=3 [2, 1, 0]
IntList size=3 [2, 1, 0]

```

**Desired output:**

```auto
IntList size=3 [0, 1, 2]
--
IntList size=3 [1, 0, 2]
--
IntList size=3 [2, 0, 1]
--
IntList size=3 [0, 2, 1]
--
IntList size=3 [1, 2, 0]
--
IntList size=3 [2, 1, 0]
--
IntList size=3 [0, 1, 2]
IntList size=3 [1, 0, 2]
IntList size=3 [2, 0, 1]
IntList size=3 [0, 2, 1]
IntList size=3 [1, 2, 0]
IntList size=3 [2, 1, 0]

```

NB. `factorial` is obviously the factorial function for an integer.

---

<div class="post-metadata">

### Author: ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)
#### Post date: [July 2, 2020, 9:36pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/2 "2020-07-02T21:36:30Z")

</div>

Hi @hsolatges,

It’s hard to tell since you did not provide an [MCVE](https://stackoverflow.com/help/minimal-reproducible-example) and we can’t test it but I think the reason you get that is because of the way you add your permutations to your list.

When you do `a.add(l);`, I think you simply point to the list itself but your are not creating any copy of it. So if later on you modify your 4th element for example then they will all be modified because they point to the same object.

And I guess also that the reason why you have the first elements working is because of the way the recusrion is working. The simplest way to check it is to try listing all your permutation after and see if you get the same result or if they are all identical this time.

Instead, try creating a new IntList every time you want to add a permutation to your ArrayList.

---

<div class="post-metadata">

### Author: ![hsolatges](https://avatars.discourse-cdn.com/v4/letter/h/6bbea6/32.png) [@hsolatges](https://discourse.processing.org/u/hsolatges)
#### Post date: [July 4, 2020, 6:35pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/3 "2020-07-04T18:35:28Z")

</div>

Here a MCVE as requested:

```auto
int factorial(int n) {
  int product = 1;
  while(n > 1) {
    product *= n;
    n--;
  }
  return product;
}

void swapInt(int i , int j, IntList l) {
  int temp = l.get(i);
  l.set(i, l.get(j));
  l.set(j, temp);
}

// https://en.wikipedia.org/wiki/Heap%27s_algorithm#Details_of_the_algorithm
void heapPermutations(int k, IntList l, ArrayList<IntList> a) { 
  if (k == 1) {
    a.add(l);
    printArray(l);
    println("--");
  } else {
    heapPermutations(k-1, l, a);
    
    for (int i=0; i<k-1; i++) {
      if (k % 2 == 0) {
        swapInt(i, k-1, l);
      } else {
        swapInt(0, k-1, l);
      }
      heapPermutations(k-1, l, a);
    }
  }
};

void setup(){
  surface.setVisible(false);
  IntList base = new IntList(0, 1, 2);
  ArrayList<IntList> permutations = new ArrayList<IntList>(factorial(base.size()));
  heapPermutations(base.size(), base, permutations);
  for(IntList perm : permutations) {
    printArray (perm);
  };
}

```

---

<div class="post-metadata">

### Author: ![hsolatges](https://avatars.discourse-cdn.com/v4/letter/h/6bbea6/32.png) [@hsolatges](https://discourse.processing.org/u/hsolatges)
#### Post date: [July 4, 2020, 6:43pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/4 "2020-07-04T18:43:18Z")

</div>

Hi @jb4x,  
Thanks for your reply.  
First, I just provided a MCVE. I didn’t realise it was such a trouble, sorry.  
Second, THANK YOU so much! I fall into the pointer trap! You were exactly right: by just adding a `.copy()` of the current state of the `IntList l` I managed to get it right.

I had an hard time with this; but it is a good lesson learnt\*!

Cheers mate!

\* Until next time…

So now, there it is:

```auto
// https://en.wikipedia.org/wiki/Heap%27s_algorithm#Details_of_the_algorithm
void heapPermutations(int k, IntList l, ArrayList<IntList> a) { 
  if (k == 1) {
    a.add(l.copy());
  } else {
    heapPermutations(k-1, l, a);
    
    for (int i=0; i<k-1; i++) {
      if (k % 2 == 0) {
        swapInt(i, k-1, l);
      } else {
        swapInt(0, k-1, l);
      }
      heapPermutations(k-1, l, a);
    }
  }
};

```

---

<div class="post-metadata">

### Author: ![potter3366](https://avatars.discourse-cdn.com/v4/letter/p/bb73d2/32.png) [@potter3366](https://discourse.processing.org/u/potter3366)
#### Post date: [March 31, 2021, 8:13pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/5 "2021-03-31T20:13:51Z")

</div>

How to remove repetitive permutations in ArrayList permutations?

```auto

```

---

<div class="post-metadata">

### Author: ![potter3366](https://avatars.discourse-cdn.com/v4/letter/p/bb73d2/32.png) [@potter3366](https://discourse.processing.org/u/potter3366)
#### Post date: [March 31, 2021, 10:40pm UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/6 "2021-03-31T22:40:18Z")

</div>

I found a solution:

```auto
int factorial(int n) {
  int product = 1;
  while (n > 1) {
    product *= n;
    n--;
  }
  return product;
}

void swapInt(int i, int j, IntList l) {
  int temp = l.get(i);
  l.set(i, l.get(j));
  l.set(j, temp);
}

void heapPermutations(int k, IntList l, ArrayList<IntList> a) { 
  if (k == 1) {
    a.add(l.copy());
  } else {
    heapPermutations(k-1, l, a);

    for (int i=0; i<k-1; i++) {
      if (k % 2 == 0) {
        swapInt(i, k-1, l);
      } else {
        swapInt(0, k-1, l);
      }
      heapPermutations(k-1, l, a);
    }
  }
};

void setup() {
  IntList base = new IntList(1, 1, 2, 2, 2, 2);
  ArrayList<IntList> permutations = new ArrayList<IntList>(factorial(base.size()));
  ArrayList<IntList> temp = new ArrayList<IntList>(factorial(base.size()));
  temp = permutations;
  heapPermutations(base.size(), base, permutations);

  for (IntList perm : permutations) {
    printArray (perm);
  };

  for (int i = temp.size()-1; i >= 1; i--) {
    IntList temp1 = temp.get(i);
    for (int k = i-1; k >= 0; k--) {
      IntList temp2 = temp.get(k);
      if (compare(temp1, temp2)) {
        // Items can be deleted with remove()
        permutations.remove(i);
        break;
      }
    }
  }

  println("-------------------------------------------");
  println(permutations.size());
  println("-------------------------------------------");

  for (IntList perm : permutations) {
    printArray (perm);
  };
}

boolean compare(IntList a, IntList b) {
  int size=a.size();
  if (size!=b.size()) return false;
  for (int i1=0; i1<size; i1++) {
    if (a.get(i1)!=b.get(i1)) return false;
  }
  return true;
}

```

---

<div class="post-metadata">

### Author: ![raron](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/raron/32/13651_2.png) [@raron](https://discourse.processing.org/u/raron)
#### Post date: [April 3, 2021, 4:08am UTC](https://discourse.processing.org/t/storing-all-index-permutations-with-heaps-algorithm/22326/7 "2021-04-03T04:08:51Z")

</div>

Btw, this might be of interest?

> **[Parallel all permutations - non-recursive - GPU optimal](https://voxels.blogspot.com/2013/05/all-permutations-non-recursive-gpu.html)**
>
> This post is a general one - not voxel related. Some time ago I developed a a s imple, fast and yet non-recursive method to directly compu...

That way you don’t need to store them, but can calculate any specific permutation on the fly. Permutations can grow huge fast (n! - nth factorial).