Is there an elegant way to generate the permutations of all the members of a set?

Processing Coding Questions
9

Can this be bettered?
Start by editing this line (39) so the list is the elements you want to perm, IntList base = new IntList(1, 2, 3, 4, 5, 6);

// @potter3366
// @hsolatges


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, 2, 3, 4, 5, 6);
  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;
}
2 Likes