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

[Chrisir]

@paulstgeorge

members

I don’t know

should be universal

[raron]

@paulstgeorge

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

You could use BigInteger to go beyond 12 characters?

It means it will treat equal characters (in this case, or equal elements) the same as if they were different. For example the string “AAAB” gets 24 permutations (4 factorial), but it will only have 4 unique permutations (AAAB, AABA, ABAA, BAAA). Or 4!/3! But this algorithm does not take that into account.

A 32-bit signed integer maximum value is 2^(32-1)-1 = 2,147,483,647
12 factorial = 479,001,600
13 factorial = 6,227,020,800 (too large for 32-bit signed integer)

You could definately use bigIntegers for a huge increase in elements (and computing time… )

[jeremydouglass]

@paulstgeorge

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

I made Recursor just for that purpose! It allows you to customize the order of generating and drawing from a recursive stack, creating different animation behaviors

Update screen during draw() without thread?

If you want to be able to render progressively from an unbounded recursive process in a single thread – and don’t want to use thread() – then there are ways. I mentioned a linked data structure that acts as a recursion queue. I actually have a draft library I wrote that does that – “Recursor”. Supposing you start out with a basic recursive function that cannot be animated. It looks like this: void tree(float[] seg) { line(seg[0], seg[1], seg[0]+seg[2], seg[1]+seg[3]); PVector s = new PV…

[paulstgeorge]

I am almost speechless! Recursor is so good. I installed it by downloading the *.jar and dragging it into the sketch window. Is that right? The mode I prefer is Mode.LAST;

[paulstgeorge]

@raron

It means it will treat equal characters (in this case, or equal elements) the same as if they were different. For example the string “AAAB” gets 24 permutations (4 factorial), but it will only have 4 unique permutations (AAAB, AABA, ABAA, BAAA). Or 4!/3! But this algorithm does not take that into account.

Ah ha… thanks. Now I understand.

[jeremydouglass]

@paulstgeorge

I installed it by downloading the *.jar and dragging it into the sketch window. Is that right?

Glad you like it! Yes, you can drag the jar in for a single sketch.

Or, if you just want to install in Processing so that any sketch can use it, unzip and drag the recursor folder into your Processing /libraries folder, alongside peasycam / minim / whatever. Then restart Processing and it will be installed on your path. You can open any of the examples and run them directly.

The behavior of the FIRST / LAST modes can correspond (somewhat) to breadth-first vs depth-first searching. First is “draw each branch out to the last leaf before moving on to the next” and last is “draw all branches, then all twigs, then all leaves.”

[grege2]

Hi folks, here are a couple of JavaScript algorithms I got from searching around a couple of years ago. I’ve used them in p5.js. I haven’t got the link for the first one. They work fine for me. I’ve only permuted small sets, eg. 3 or 6 numbers. You can translate them to Java of course. Hope that helps someone, ciao.

// Here's a simple but maybe inefficient permute function.
// Try "permute1([1,2,3])" 


const permute1 = (inputArr) => {
   let result = [];

   const permute = (arr, m = []) => {
      if (arr.length === 0) {
         result.push(m);
      } else {
         for (let i = 0; i < arr.length; i++) {
            let curr = arr.slice();
            let next = curr.splice(i, 1);
            permute(curr.slice(), m.concat(next));
         }
      }
   };

   permute(inputArr);

   return result;
};


// Here's another one, allegedly more efficient for large N.
// https://stackoverflow.com/questions/9960908/permutations-in-javascript.
// Try it with permute2([4,5,6,7]);

function permute2(permutation) {
   let length = permutation.length,
       result = [permutation.slice()],
       c = new Array(length).fill(0);
   let i = 1, k, p;

   while (i < length) {
      if (c[i] < i) {
         k = i % 2 && c[i];
         p = permutation[i];
         permutation[i] = permutation[k];
         permutation[k] = p;
         ++c[i];
         i = 1;
         result.push(permutation.slice());
      } else {
         c[i] = 0;
         ++i;
      }
   }
   return result;
}