Adding rules to a permutation generator

jazbogross

Hi everyone!

I'm an art student at the Royal College of Art in London, working with video. I'm very inexperienced when it comes to code, but the work that I'm currently doing does nevertheless involve coding. I'm getting some help from the college, but the process is slow since I can only book one hour a week with the tutor that is able to help me. Although I am trying to learn I'm also trying to finish this video project at the moment. I'm writing this post in the hope that someone in here can help me move forward a bit from where I'm stuck right now.

The work I'm doing involves video loops of very short duration: Four different loops of 3 frames, 6 frames, 12 frames and 24 frames, all playing at 24fps. What I want to do is reorganise the order of the frames of these very short loops, producing all possible non chronological iterations, playing through all the iterations before looping back to the first one and doing it all over again.

First, I found this permutation generator on the forum, provided by Chrisir:

Then, made some changes to the code to get what I have pasted at the end of this post. So far, this version "fails" all permutations that contain chronology of frame order (say, 2 followed by 3 or 5 followed by 6).

The new rule I would like to introduce - since I'm working with the video sequences as loops - is that (in the case of a 6-frame sequence) 6 should never be followed by 1, since if 6 frames were played continually in a loop, frame 1 would follow frame 6 every time the sequence started over. 6 followed by 1 therefore counts as part of the chronology of the loop, and it is this chronology that I want to eradicate. ALSO the first and the last frame of each sequence need to be checked against each other so that they do not follow each other chronologically. BUT it gets more complicated, because I don't want the code to just skip an iteration if it happens to be one that starts on 1, following an iteration ending on 6, since this iteration could still be valid if it eventually holds a different position in the string. Hopefully the meaning of this becomes more clear in my example further down.

The 3-frame one is very easy (only one possible variation): 321. So the final output is a loop that plays the frames in this order: 123321, over and over forever. But it gets too complicated with the 6-frame sequence. I will give an example, working with only 4 frames as this can actually be done manually (without too much of a headache).

EXAMPLE WITH 4 FRAMES

The code gives us 11 possible (non-chronological) iterations, but the ones marked with bold contain 4 followed by 1, so are removed:

(1234) 1324 2143 2413 2431 3142 3214 3241 4132 4213 4321

giving us:

(1234) 1324 2143 2431 3142 3214 4213 4321

Now we still have a problem, because when these iterations are put into one long string (which will be the order that the frames are played in), we get 4 followed by 1 && 2 followed by 3 && 3 followed by 4.

12341324214324313142321442134321

To avoid this, the order of the sequence needs to be reshuffled and checked again, to avoid having to just get rid of the iterations that are in the wrong place. This is my manual reordering of the iterations so they fit into one long string without breaking any of the rules I have mentioned:

The final output for a loop of 4 frames becomes a loop lasting 1,33 second when played at 24fps, which contains only the one original chronological sequence (1234) and 7 non-chronological variations of that sequence. The whole loop is absolutely non-chronological, except for the original sequence: 1234, which is the reference point.

I apologise for this very long explanation of something that could probably be said a lot simpler if I had the technical capabilities to do so, but I hope it makes some sense. It might be too big a question to be asking in this forum. I won't be disappointed if you feel like I need to do some more work on my own before I come here, but if anyone feels like helping me out with some of the coding or maybe just giving me some words of advice on this problem I would be very grateful.

(I have left out the "class PermutationGenerator {..." to make the post just a little bit shorter, but that part can be found through the link to the full code that I pasted above)

// originally by  clankill3r, MODIFIED

import java.math.BigInteger;
 int count = 0;
int[] indices;
boolean fail;
String[] elements = {
  "1", "2", "3", "4"
};
PermutationGenerator x = new PermutationGenerator (elements.length);
StringBuffer permutation;

void setup() {
  while (x.hasMore ()) {
    permutation = new StringBuffer ();
    indices = x.getNext ();
    for (int i = 0; i < indices.length; i++) {
      permutation.append (elements[indices[i]]);
    }

    fail = false; // reset the fail flag variable

    //generate each individual permutation

    for (int i = 0; i < elements.length; i++){

      if (i > 0 && i < elements.length-1)
      {
        if (indices[i+1] - indices[i] == 1 || indices[i] - indices[i-1] == 1)
        {
          fail = true;  
      }

    }

  }

    if(fail){

    }
    else
    {
    //println (indices[1]);
      println (permutation.toString ());
      count++;
    }
  }
  println ("End of setup.");
  println (count);
} //

void draw() {
  // println (permutation.toString ());
  noLoop();
}

koogs

all possible non chronological iterations,

How important is the 'all' here?

Because without that, another way of doing this would be to pick an initial frame and then chose the next frame from a list that doesn't include the next chronological frame. Ie only worrying about the single next frame.

quark

When you talked about 6 frames you said 6 should never be followed by a 1.

Then when talking about 4 frames you are leaving in permutations containing 41 e.g. 4132 but removing permutations containing 14, a non-chronological sequence.

Very confused here :)

jazbogross

@koogs. thanks for your thought. I see what you mean, its a good point, but the "all" is important to me.

@quark. Wow! how could I mess that up? I have edited my post, so hopefully my example makes more sense now.

quark

In your long reordered string you have 12342143...

You still have the chronological sequence 1234, is this right?

jazbogross

yes, that is right. The original sequence should be part of the final output as the only place in the entire string that has any chronology.

Chrisir

Is it really necessary to go from all permutations to a long String as shown in the graphic above?

you could just start from scratch with the long String and choose next number randomly, controlling if it matches the rules on the fly, no?

Screen Shot 2015-12-09 at 18.10.44

jazbogross

That would give an infinite random sequence, right? It is essential to what I'm trying to do that the final sequence (long string) is finite so that it loops back and plays again. It is also important that the same iteration doesn't appear twice in the final string, so that the final string consists only of the one original sequence (for example 1234) and all the sequences that are uniquely non-chronologic. Maybe the final step of putting it into the long string is unnecessary though. It's just the way I thought of it because I'm thinking of how it will play the frames as an uninterrupted video loop in 24 frames a second.

I'm thinking that it will still have to do it on the fly somehow though, because it would take forever to produce the 24 frame one. At the moment I'm thinking that it would do something like 1000 iterations and then play through that piece of the video sequence while figuring out the next 1000. I left this out of my original description because I figured this would be the next stage and I didn't want to make my already very long question even longer.

quark

At the moment I'm thinking that it would do something like 1000 iterations and then play through that piece of the video sequence while figuring out the next 1000

Calculating all the non-chronological permutations shouldn't be too hard but in your example you talk about 'manual reordering of the iterations' to avoid a chronological pair formed at the ends. This would seem to suggest that you calculate all the permutations first which is not compatible with your statement above.

Obviously the number of permutations depends on the number of frames, so In the final application how many frames (maximum) are we talking about?

jazbogross

The maximum will be 24 frames.

in your example you talk about 'manual reordering of the iterations' to avoid a chronological pair formed at the ends.

This reordering should be done by the code, not manually. In the example that I gave I just did it in my head because I haven't written the code yet that does it. That's what I'm trying to get some help with. Does that make sense?

koogs

there are 6.204484 * 10^23 permutations of 24 objects.

or a film 299213156700057600 days long.

jazbogross

Yes I know, it will never finish. but the shorter loops will. But then again, it will be a bit shorter than 6.204484 * 10^23 after the rules are applied, but yes, the 24 frames one still won't finish in our lifetime. This is why I figured it would have to do the calculations on the fly, because there would be too many sequences to figure out all in one go, before playing the video.

quark

With that many permutations creating random non-chronological ordered permutations at random it is virtually impossible to get a duplicate permutation especially with modern random number generators.

There are reasonably fast ways to do this but it would probably be best to use a separate thread to produce the permutations and the main thread to consume the permutations (display them).

Will think on this and see what I can come up with :)

quark

@jazbogross

I have a solution to your problem it is based on my previous statement

With that many permutations creating random non-chronological ordered permutations at random it is virtually impossible to get a duplicate permutation ...

Also there is no need for a producer thread because the time to create a single permutation is extremely small. On my computer it was about 4.5 millionths of a second to create a permutation.

Here is the output when I ran the sketch below on my computer.

BTW Although the Bag and Permutation classes are inner classes they have been written using standard Java syntax so they can be used as top-level classes at a later date and if so so desire.

First 5 permutations starting with ordered permutation
ABCDEFGHIJKLMNOPQRSTUVWX
CQFKHBOSEPRDGTAMUWJVNLIX
NIBJACSVFMURWLOXGEPTKDQH
KJISDVNMEBTOUGCWAXFLPHRQ
PKEXJNLIHRUTGWQCBAMSFVDO
------------------------------------------------------
Start of validity test
End of validity test

Start of timing test
10000000 permutations took 3990ms to calculate
Thats an average of 3.99E-4ms for each permutation
End of timing test

Sketch code

import java.util.Random;

Bag bag;
Permutation p, next;

public void settings() {
  size(400, 200);
}

public void setup() {
  bag = new Bag(24);
  p = bag.getOrdered();
  println("First 5 permutations starting with ordered permutation");
  next = p;
  for (int i = 0; i < 5; i++) {
    println(next);
    next = bag.getRandomPermutation();
  }
  println("------------------------------------------------------");
  validityTest(10000, next);
  // JVNM is warmed up ready for some timing :)
  timingTest(10000000);
}

public void timingTest(int n) {
  int time;
  println("Start of timing test");
  time = millis();
  for (int i = 0; i < n; i++) {
    next = bag.getRandomPermutation();
  }
  time = millis() - time;
  println(n + " permutations took " + time + "ms to calculate");
  float average = ((float)time) / n;
  println("Thats an average of " + average + "ms for each permutation");
  println("End of timing test\n");
}

public void validityTest(int n, Permutation prev) {
  println("Start of validity test");
  for (int i = 0; i < n; i++) {
    next = bag.getRandomPermutation();
    if (!next.isValid())
      println("Invalid permutation " + next);
    if (!next.isValidJoin(prev))
      println("Invalid Join " + prev + " >> " + next);
    prev = next;
  }
  println("End of validity test\n");
}

// Implementation of a shuffle bag to avoid chronological
// ordering of tokens.
// Tokens have values 1 to NBR_TOKENS inclusive
class Bag {
  private Random rnd = new Random();
  private int[] tokens;
  private int startTokenToAvoid = -1;
  private final int NBR_TOKENS;
  private final int LAST_IDX;
  private final int LAST_IDX_M1;
  private final int LAST_IDX_M2;

  public Bag(int nbr) {
    NBR_TOKENS = nbr;
    LAST_IDX = nbr - 1;
    LAST_IDX_M1 = LAST_IDX - 1;
    LAST_IDX_M2 = LAST_IDX - 2;
    tokens = new int[nbr];
    for (int i = 0; i < NBR_TOKENS; i++)
      tokens[i] = i + 1;
  }

  // Get a permutation with 
  public Permutation getOrdered() {
    for (int i = 0; i < NBR_TOKENS; i++)
      tokens[i] = i + 1;
    return new Permutation(tokens);
  }

  public Permutation getRandomPermutation() {
    int currentIdx, rndIdx, range;
    // Randomize the first token in the permutation making sure
    // is is not in order with the end of the previous permutation
    currentIdx = 0;
    range = NBR_TOKENS - 1;
    do {
      rndIdx = 1 + rnd.nextInt(range);
    } while (tokens[rndIdx] == startTokenToAvoid);
    swap(0, rndIdx);
    currentIdx++;
    range--;
    while (currentIdx <= LAST_IDX_M2) {
      do {
        rndIdx = currentIdx + 1 + rnd.nextInt(range);
      } while (tokens[rndIdx] == tokens[currentIdx-1] + 1);
      swap(currentIdx, rndIdx);
      currentIdx++;
      range--;
    }
    // Have to do the last 3 here to avois risk of an infinite loop
    if (tokens[LAST_IDX] == tokens[LAST_IDX_M1] + 1)
      swap(LAST_IDX, LAST_IDX_M1);
    else if (tokens[LAST_IDX_M1] == tokens[LAST_IDX_M2] + 1)
      swap(LAST_IDX_M1, LAST_IDX_M2);
    // Determine the token to avoid at the start of the next permutation
    startTokenToAvoid = (tokens[LAST_IDX] + 1);
    if (startTokenToAvoid > NBR_TOKENS)
      startTokenToAvoid = 1;
    // Create and return the permutation based on this bag
    return new Permutation(tokens);
  }

  private void swap(int idx0, int idx1) {
    int temp = tokens[idx0];
    tokens[idx0] = tokens[idx1];
    tokens[idx1] = temp;
  }
}

class Permutation {
  public final int[] frames;
  public final int length;

  public Permutation(int[] tokens) {
    length = tokens.length;
    frames = new int[length];
    System.arraycopy(tokens, 0, frames, 0, length);
  }

  // Returns true if in non-chronological order
  public boolean isValid() {
    for (int i = 1; i < length; i++) {
      if (frames[i] == frames[i-1] + 1)
        return false;
    }
    return true;
  }

  // Returns true if the last frame of the previous permutation
  // and the first frame of this one are not in order.
  public boolean isValidJoin(Permutation prev) {
    int startTokenToAvoid = prev.frames[prev.length - 1] + 1;
    if (startTokenToAvoid > prev.length)
      startTokenToAvoid = 1;
    return startTokenToAvoid != frames[0];
  }

  // Convert token values to chars 1 > A, 2 > B .... 24 > X
  // for display purposes
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < frames.length; i++)
      sb.append("" + (char)(64 + frames[i]));
    return sb.toString();
  }
}

jazbogross

@quark Thank you! At first glance this is quite different than what I had imagined, but I can't say immediately if this does in fact produce the desired result. It will take me a little time to look through it and consider the implications. I really appreciate this. I will return when I have had time to consider this properly. Thanks again!

jazbogross

Thanks a lot for your attention and support. I understand your perspective quark, but I am not really looking for the visual effect of randomness. Even if it is virtually impossible to happen on the same permutation in for example a sequence of 24 frames, it would be quite likely in sequences with less frames, say 5 or 6 frames. My interest is in creating a code that theoretically exhausts all possibilities and then starts over again, producing a unique non-chronological, non-loop-like sequence. I am still working on the code, getting closer now, and I will post it when it is finished. Thanks again for your help!