Storing all index permutations with Heap's algorithm

Processing Coding Questions
1

Hi, I am new on Processing and I am struggling with Java.
I am trying to use Heap’s 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:

// 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 :

  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:

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:

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.

1 Like
2

Hi @hsolatges,

It’s hard to tell since you did not provide an MCVE 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.

1 Like
3

Here a MCVE as requested:

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);
  };
}
4

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:

// 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);
    }
  }
};
2 Likes
5

How to remove repetitive permutations in ArrayList permutations?

6

I found a solution:

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;
}
1 Like
7

Btw, this might be of interest?

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).

1 Like