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

Processing Coding Questions
1

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

I have done it in a long winded, clumsy, inelegant way for six elements by having an array of all 720 permutation of six numbers, then having a look-up table. So, each number (1, 2, … 6) can represent a colour, a string, anything.

But there must be a better way!

elementArray[1] = 123456;
  elementArray[2] = 123465;
  elementArray[3] = 123546;
  elementArray[4] = 123564;
  elementArray[5] = 123645;
  elementArray[6] = 123654;
  elementArray[7] = 124356;
  elementArray[8] = 124365;
  elementArray[9] = 124536;
  elementArray[10] = 124563;
  elementArray[11] = 124635;
  elementArray[12] = 124653;
  elementArray[13] = 125346;
2

There is a better way.

2 Likes
3

It is possible. But I have a few questions. What do you want to achieve in the end? 123456 as number may not be convenient as a lookup table. You may want to store it as an array or string "123456". How are you referencing it to map to color?

I checked the referenced topic and it seems @jeremydouglass already gave an answer in a Python script. It would be so much nicer if you’d have explicitly linked it in the first place :slight_smile: and I guess, it’s a matter of porting it to Java.

2 Likes
4

A new topic for sure… looking forward to this.

:)

5

I’m happy to move these to a new thread / topic – @paulstgeorge, go ahead and create one.

One example I like is the Python documentation of itertools.permutations.

It is very idiomatically Python – the use of a separate index lookup, of slicing, and of reversed() – so it doesn’t translate well to Java, but it is pretty interesting as an approach.

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return
2 Likes
7

I haven’t looked into it or tried it, but I think there is a Java implementation here:

…and several people mention Guava’s permutations and orderedPermutations – those are probably going to be verbose, but it might be interesting to look at the code.

https://guava.dev/releases/19.0/api/docs/com/google/common/collect/Collections2.html

1 Like
8

I was trying to work out the algorithm used in the Python approach mentioned by @jeremydouglass

I think it is Heap’s algorithm so then I looked up Heap’s algorithm in Processing and found this: Storing all index permutations with Heap's algorithm

More follows.
And here is the Steinhaus–Johnson–Trotter algorithm in JS https://codepen.io/jbranchaud/pen/gbRGBp
and in ALGOL 60 !!! https://dl.acm.org/doi/10.1145/368637.368660

2 Likes
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
10

Another interesting reference is the Rosetta Code page on “Permutations”:

https://rosettacode.org/wiki/Permutations

I notice that there is a Java permutations entry, but there aren’t entries (yet) for Processing / p5.js / Python mode, et cetera… :wink:

2 Likes
11

Yes, very interesting. I am tempted to add the Heap solution as a Processing entry but relunctant to do so with someone else’s code. I think it is very good but they might not. Is there a protocol?

Also, the quest for elegance in code continues. I had thought permutations might yield it but the subject defies brevity.

@hsolatges
@potter3366

12

Well, elegance is in the eye of the beholder… but if you are looking for something that combines brevity and function, maybe something recursive? Eg fractal tree or dragon curve?

https://rosettacode.org/wiki/Fractal_tree#Processing

https://rosettacode.org/wiki/Dragon_curve#Processing

2 Likes
13

Well, there are a few obvious brute force solutions. The most obvious be run through all 1000000 combinations and find ones containing #s 1-6 w/ no repeats. Of course…not elegant at all, but let’s keep going.

Next solution is iterative. This time we have to represent our permutations as arrays of integers. We’re gonna traverse all possibilities for each index, but any time we have duplicate indices, we skip. So all permutations starting with 1,1 are immediately ignored. Observe:

for(int a=1;a<=6;a++) {
  for(int b=1;b<=6;b++) {
    if(b==a) { continue; }
    for(int c=1;c<=6;c++) {
      if(c==a || c==b) { continue; }
      for(int d=1;d<=6;d++) {
        if(d==a || d==b || d==c) { continue; }
        for(int e=1;e<=6;e++) {
          if(e==a || e==b || e==c || e==d) { continue; }
          int f=(1+2+3+4+5+6) - (a+b+c+d+e);
          //add permutation a,b,c,d,e,f to your list
          //I'm being ambiguous here because there are many ways to store your list
        }
      }
    }
  }
}

You might also notice that we didn’t even have to use loops for the 6th index because we instead just found whichever one hadn’t been used yet. The whole adding and subtracting method was the first thing that came to mind, but there’s probably another better way of doing that. I think this involves 2586 iterations, which is good, but might not be the best.

The other method I came up with, and arguably a more elegant method, involves recursion.

Ultimately, if you want all permutations of numbers 1-6, that’s the same as concatenating the following 6 sets together:

Take all permutations of 1,2,3,4,5. Then put a 6 at the end of each permutation.
Take all permutations of 1,2,3,4,6. The put a 5 at the end of each permutation.
Take all permutations of 1,2,3,5,6. Then put a 4 at the end of each permutation.
…
Take all permutations of 2,3,4,5,6. Then put a 1 at the end of each permutation.

This ultimately involves taking all permutations of 5 different numbers, and repeating that 6 times, just with different sets. Taking all permutations of 5 different numbers can be broken down further, into 5 sets, each containing permutations of 4 numbers with another number slapped on at the end. And so on until you reach the trivial combinations of 2 numbers. This is probably more efficient than the iterative method. Or at least, if not more efficient, it’s at least reusable.

That said, if you really want, I might be able to write code for this recursive method. I started doing it, then realized it involves a bunch of tedious array functions and realized the first thing I gave you should work just fine.

Also, I realized that there’s a possible speedup to the recursive method. It’d probably cut the work load down by a lot. Instead of creating 6 unique sets of permutations of 5 numbers, we could just generate one set, then swap the number at the end with one other number. This could cut the work load down a lot, or could make things slower because of how much sequential searching it involves.

Honestly, if you apply that one speedup, you really eliminate all the trial and error and only ever have to work with combinations guaranteed to work. And, as a bonus, if you decide to slap the number before the permutation instead of after, your permutations come in the exact same order they did in the iterative method. Honestly, the only downside is all the array accesses, which could make or break the overall efficiency.

There are probably many different ways I didn’t even think of to approach this. At heart, this problem feels like a classical conundrum with multiple different solutions, like sorting algorithms. Which is why I’m surprised I never ran into this problem until now.

Anyway, feel free to use the code I supplied. Have a good one!

1 Like
14

That’s great, thank you. I like the iterative solution because it has a concrete poetry feel and a repeating pattern with variations. I added println(a, b, c, d, e, f); after line 10 to see the results.

I think your recursive method will be very very interesting (if you can be persuaded to write the code). You mention concatenating the 6 sets. Your speeded-up method of breaking down to 5 different numbers, then four, and so on sounds like a method I might use on paper. I will share it in case it suggests something effective, beautiful, or even both.

For permutations of three numbers (as an example).

Put 1 into position 1. Place the permutations of 2 and 3 after it.
1,2, 3 and 1, 3, 2

Put 1 into position 2. Place the permutations of 2 and 3 around it.
2, 1, 3 and 3, 1, 2

Put 1 into position 3. Place the permutations of 2 and 3 after it.
2, 3, 1 and 3, 2, 1

So, swapping numbers or swapping positions??

1 Like
15

I like the Fractal tree very much. I would like it even more if I could watch the tree grow (be drawn). Am working on it!

16 


// by  clankill3r

import java.math.BigInteger;

int[] elements = {
  0, 1, 2, 3, 4, 5
};
IntList[] permutation;

void setup() {
  size(1220, 900);
  funcForPermutation();
  fill(0); 
  println ("End of setup.");
} //

void draw() {
  // println (permutation.toString ());
  text("Permutation\nat pos 0 "
    +permutation[0]
    +"\nat pos 120 "
    +permutation[120]
    +"\n\n"
    , 20, 30);// +permutation.size() 
  println (permutation[0]);
  println (permutation[120]);

  int line=0; 
  for (IntList i1 : permutation) {
    String result=""; 
    for (int i2 : i1) 
      result+=str(i2); 
    text(result, 
      width -230, line*20+33);
    line++;
  }

  // End here 
  noLoop();
}

// ------------------------------------------------------------------

void funcForPermutation() {
  PermutationGenerator x = new PermutationGenerator (elements.length);

  int[] indices;

  int i2 = 0; 

  permutation=  new IntList [ 720 ]; //  PermutationGenerator.getTotal ()  ];
  while (x.hasMore ()) {
    permutation[i2] = new IntList ();
    indices = x.getNext ();
    for (int i = 0; i < indices.length; i++) {
      permutation[ i2 ].append (elements[indices[i]]);
    }
    // println (permutation[i2].toString ());
    i2++;
  }
  println(i2);
}

// ==========================================================================

class PermutationGenerator {

  int[] a;
  BigInteger numLeft;
  BigInteger total;

  //-----------------------------------------------------------
  // Constructor. WARNING: Don't make n too large.
  // Recall that the number of permutations is n!
  // which can be very large, even when n is as small as 20 --
  // 20! = 2,432,902,008,176,640,000 and
  // 21! is too big to fit into a Java long, which is
  // why we use BigInteger instead.
  //----------------------------------------------------------

  PermutationGenerator (int n) {
    if (n < 1) {
      throw new IllegalArgumentException ("Min 1");
    }
    a = new int[n];
    total = getFactorial (n);
    reset ();
  }

  //------
  // Reset
  //------

  void reset () {
    for (int i = 0; i < a.length; i++) {
      a[i] = i;
    }
    numLeft = new BigInteger (total.toString ());
  }

  //------------------------------------------------
  // Return number of permutations not yet generated
  //------------------------------------------------

  BigInteger getNumLeft () {
    return numLeft;
  }

  //------------------------------------
  // Return total number of permutations
  //------------------------------------

  BigInteger getTotal () {
    return total;
  }

  //-----------------------------
  // Are there more permutations?
  //-----------------------------

  boolean hasMore () {
    return numLeft.compareTo (BigInteger.ZERO) == 1;
  }

  //------------------
  // Compute factorial
  //------------------

  BigInteger getFactorial (int n) {
    BigInteger fact = BigInteger.ONE;
    for (int i = n; i > 1; i--) {
      fact = fact.multiply (new BigInteger (Integer.toString (i)));
    }
    return fact;
  }

  //--------------------------------------------------------
  // Generate next permutation (algorithm from Rosen p. 284)
  //--------------------------------------------------------

  int[] getNext () {

    if (numLeft.equals (total)) {
      numLeft = numLeft.subtract (BigInteger.ONE);
      return a;
    }

    int temp;

    // Find largest index j with a[j] < a[j+1]

    int j = a.length - 2;
    while (a[j] > a[j+1]) {
      j--;
    }

    // Find index k such that a[k] is smallest integer
    // greater than a[j] to the right of a[j]

    int k = a.length - 1;
    while (a[j] > a[k]) {
      k--;
    }

    // Interchange a[j] and a[k]

    temp = a[k];
    a[k] = a[j];
    a[j] = temp;

    // Put tail end of permutation after jth position in increasing order

    int r = a.length - 1;
    int s = j + 1;

    while (r > s) {
      temp = a[s];
      a[s] = a[r];
      a[r] = temp;
      r--;
      s++;
    }

    numLeft = numLeft.subtract (BigInteger.ONE);
    return a;
  }
} //class
//
2 Likes
17

What about a domino tile approach?

You have 6 spaces.
And 6 matrices.
Mat[0]=123456=> choose item N[0) and create matrix 2
Mat[1]=23456 => (matrix 0 without element N[0]). Choose N[1] and create Mat[2] with remaining elements.

After creating Mat[5], output result and change N[5].
After N[5] reaches 6-5 (=1), change N[5] and M[5]
And so on.

I think i have a Processing code with permutations somewhere. I have to look up on my phone backups, since i did it on APDE (Android Processing).

2 Likes
18

There is a brilliant permutation algorithm posted in this (linked) blog. The guy has a great explanation of his method too.

I’ve used his method a few years ago, and did a bit of (attempted) clean up of a couple of demos (Might not be the most elegant coding):

Simple demo 
/* Permutations test for Processing

Based on Sven Forstmann's brilliant algorithm:
https://voxels.blogspot.com/2013/05/all-permutations-non-recursive-gpu.html

Max 12 character length, 32-bit signed integers can't hold values above 12!
(12 factorial)

Does not account for repeated characters

2021.07.17 raron - rewritten for Processing (again)
*/

String test = "123";

int perm=1, digits=test.length();
for (int i=1; i<=digits; perm*=i++); // factorial

println("Lenght: " + digits + ", Permutations: " + perm);

for (int a=0; a<perm; a++)
{
   char avail[] = test.toCharArray();
   print(a + ": ");
   for (int b=digits,div=perm; b>0; b--)
   {
      div/=b;
      int index = (a/div)%b;
      print(avail[index]);
      //avail[index] = avail[b-1]; // non-lexigraphic but fast
      for (int e=index; e<digits-1; e++) avail[e] = avail[e+1]; // lexigraphically correct
   }
   println();
}
println("permutations: " + perm);
exit();
Demo 2, as a function 
/* Permutation funtion test for Processing

Based on Sven Forstmann's brilliant algorithm:
https://voxels.blogspot.com/2013/05/all-permutations-non-recursive-gpu.html

Max 20 character length, 64-bit signed integers can't hold values above 20!
(20 factorial)

Does not account for repeated characters

2021.08.25 Demoing a function returning specific permutations
2015.01.02 Fixed for long ints (64-bit - 20 elements/characters only)
2014.12.28 raron - rewritten for Processing
*/

//String test = "123456789ABCDEFGHIJK"; // 20 character max for long ints
String test = "123";

char chPermuteThis[] = test.toCharArray();
int digits           = test.length();
int[]  remapper      = new int[digits];
char[] chRemapped    = new char[digits];  // Holds result of permutation

long permutations  = 1;

void setup()
{
  for (long i=1; i<=digits; permutations*=i++); // factorial

  println("Lenght: " + digits + ", Permutations: " + permutations);

  // Go through all permutations from first (original) to last (original backwards)
  for (long nr=0; nr<permutations; nr++)
  {
    permute(permutations, nr, digits, remapper);
    for (int r=0; r<digits; r++) chRemapped[r] = chPermuteThis[remapper[r]];
    print(nr + ": ");
    for (int r=0; r<digits; r++) print(chRemapped[r]);  // Result of permutation
    println();
  }
  println("Done. Permutations: " + permutations);
  exit();
}


// Get specific permutation nr. (as a remapping array from original)
void permute(long permutations, long pnr, int nrofdigits, int[] remap)
{
  // temp remapping array
  int[] temp = new int[nrofdigits];
  for (int dpos=0; dpos<nrofdigits; dpos++) temp[dpos]=dpos;

  // Get permutation remapping
  long div = permutations;
  for (int dpos=nrofdigits; dpos>0; dpos--)
  {
      div /= dpos;
      long longindex = (pnr/div)%dpos;
      int index = (int)longindex;
      //remap[dpos-1] = temp[index];         // Alternate backwards first
      remap[nrofdigits-dpos] = temp[index];  // backwards last
      // Pseudo truncate array
      for (int pos=index; pos<nrofdigits-1; pos++) temp[pos] = temp[pos+1];
  }
}

EDIT: Misspelled Sven’s last name (corrected)

2 Likes
19

Would love to see the code! Is a matrix an array?

20

The simple demo is very good indeed!

There is a comment: :“Does not account for repeated characters”. What does that mean?

You could use BigInteger to go beyond 12 characters?

21

Wow!
Is this code specifically for six members? The arrays have 120, 720, etc.