Trying to generate a population of 50 randomly permutated numbers but program doesn't stop running

I am trying to generate a population of 50 sets of 20 randomly sequenced aircraft. The only condition is that each aircraft can only shift 2 positions forward or backward from their initial positions. My code doesn't produce errors but it runs forever even when I just want to produce 1 generation with the above conditions.

%create initial population by randomizing positions of aircraft for 50
%aircraft

randcounter=1;

%let x be the number of aircraft landing in the time frame
x=20;

while randcounter<=50;

    temp= randperm(x);
    n=1; %n must start with 1 because when checking condition we must start checking from temp(1) later on
    o=0;

    %function to check if the random permutation is feasible (ie each
    %position is shifted not more than 2 places).

    %n is used to check that all 20 numbers have been checked.
    %o is used to count if all have passed. if finally after all 20 have
    %been checked and o is less than 20, means this permutation fails.
    while n<=x;

        if ((temp(n)<=(n+2))&& (temp(n)>=(n-2)))

            n=n+1;
            o=o+1;

        else

            n=n+1;

        end

    end

        if o==20; %the permutation passes
            initialpop(randcounter)=temp;
            randcounter= randcounter+1;

        else
            randcounter=randcounter;

        end

        temp=[];

end

[dpb]

I'd guess the restrictions aren't ever satisfied (and likely will take an inordinate amount of time as you've discovered to ever be so by using only rejection/regeneration).

To check that is so, monitor the value of the counter o; it never reaches 20, does it?

I suspect you'll have to think the restrictions through more carefully and do reordering within the checking process rather than simply rejecting the sample to ever get the sequence that is suitably ordered given your stated limitations of positions.

Or perhaps you should generate an initial order then resample from that some subset number to reorder within the initial sequence by the allowable [0,1,2] positions either way instead. What, specifically, would be dependent on what the process is that you're actually trying to model as to how the reordering is trying to simulate.

Answer 1

[Roger Stafford]

The method you are attempting to use would randomly select out of all possible permutations, using a rejection method, one of those that satisfy your special condition. Unfortunately, as dpb has indicated, the probability that you will succeed in a reasonable time are exceedingly small.

I would suggest a compromise that would only randomly select by rejection from a much more limited set of possible permutations.

 n = 20;
 d = 10;
 b = true;
 while b
   [~,p] = sort(d*rand(1,n)+(1:n));
   b = max(abs((1:n)-p))>2;
 end

In trials on my computer this usually took only about a second or so to find a successful solution using d equal to 10. If d is increased, it will take more time on the average but obtain a more random selection out of all possible permutations. A decrease would speed things up but have a less random selection.

[Roger Stafford]

I neglected to mention that the above assumes an initial positioning of 1:n. Subsequent solutions can be found by using the above method but then taking the "product" of such permutations, that is, p2 = p2(p1), p3 = p3(p2), p4 = p4(p3), etc. where p1, p2, p3 are initially the above solutions using 1:n.

(IGNORE THIS COMMENT. THE CORRECT WAY TO DO THE "PRODUCTS" IS GIVEN IN THE NEXT COMMENT.)

[Roger Stafford]

I got those permutation "products" backwards in that previous comment. Here is code that starts with 20 airplanes numbered from 1 to 20 but in random order. In each succeeding column of the 50, those airplanes have changed positions by no more than two places from those in the previous column.

n = 20;
m = 50;
P = zeros(n,m);
q = randperm(n)'; % Start with some random order
P(:,1)  = q;
for k = 2:m
  b = 1;
  while b
    [ig,p] = sort(10*rand(n,1)+(1:n)');
    b = max(abs((1:n)'-p))>2;
  end
  q = q(p);
  P(:,k) = q;
end

Note: I may have misunderstood you where you said "each aircraft can only shift 2 positions forward or backward from their initial positions." Perhaps you have a fixed initial ordering and each column differs from this fixed order by no more than two places. In that case, change the two lines

    q = q(p);
    P(:,k) = q;

to the single line

    P(:,k) = q(p);

which leaves q unchanging at the initial ordering.

Answer 2

[Tim]

Thanks a lot Roger. I didn't actually expect a response. I'll think about it. Thanks.