%%%%%%%
% findmin.m
% Author: Lance Harden, Davidson College
% June 2006
%
% Description: A variation of powerflipper, findmin randomly flips an
% inputted initial permutation until either (1) the stack has been
% reordered into the home permutation in less than or equal to br flips, or
% (2) all n trials are run. It accepts the same inputs as powerflipper:
% number of spatulas (1 or 2), type of permutation ('s' or 'u', for signed
% or unsigned), initial permutation, number of trials, and the number of
% random flips per trial, respectively. It stores the flip history for the
% last trial in the matrix, flips, and the number of flips it took to reach
% the home permutation for each trial in the Results matrix.
function [Results,flips] = findmin(s,t,I,n,br)
Results = [];
if (s ~= 1 & s ~= 2)
disp('How many arms do you have!')
return
end
if (t ~= 's' & t ~= 'u')
disp('Error: You must enter "s" or "u". Try again by re-running the program.')
return
end
k = length(I);
if k < 2
disp('Error: You must enter your initial permutation as a row vector with at least two entries.')
return
end
B = sort(abs(I));
if (B ~= 1:k & t == 's')
disp('Error: Your initial permutation must consist of signed consecutive integers starting at 1, e.g. [3 -2 -4 1] is OK, but [8 3 5 1] and [0 -2 1 -3] are not.')
return
end
if (B ~= 1:k & t == 'u')
disp('Error: Your initial permutation must consist of consecutive integers starting at 1, e.g. [3 1 2 4] is OK, but [2 8 0 5] is not.')
return
end
slots = k+1;
choices = nchoosek(1:slots,2);
choices(:,2) = choices(:,2) - 1;
numchoices = length(choices);
tic
if s == 1
if t == 's'
for i = 1:n
G = I;
count = 0;
flips = [];
while ( any(G ~= 1:k) || any(G ~= -k:-1) )
count = count + 1;
flips(:,count) = G';
P = G;
a = ceil(k*rand);
G = [fliplr(P(1:a)) P(a+1:k)];
for j = 1:a
G(j) = -G(j);
end
end
Results(i) = count;
flips(:,count + 1) = G';
if (count <= br)
time = toc
beep
return
end
end
else
for i = 1:n
G = I;
count = 0;
flips = [];
while any(G ~= 1:k)
count = count + 1;
flips(:,count) = G';
P = G;
a = ceil(k*rand);
G = [fliplr(P(1:a)) P(a+1:k)];
end
Results(i) = count;
flips(:,count + 1) = G';
if (count <= br)
time = toc
beep
return
end
end
end
else
if t == 's'
for i = 1:n
G = I;
count = 0;
flips = [];
while ( any(G ~= 1:k) || any(G ~= -k:-1) )
count = count + 1;
flips(:,count) = G';
P = G;
a = ceil(numchoices*rand);
G = [P(1:(choices(a,1)-1)) fliplr(P(choices(a,1):choices(a,2))) P((choices(a,2)+1):k)];
for j = choices(a,1):choices(a,2)
G(j) = -G(j);
end
end
Results(i) = count;
flips(:,count + 1) = G';
if (count <= br)
time = toc
beep
return
end
end
else
for i = 1:n
G = I;
count = 0;
flips = [];
while any(G ~= 1:k)
count = count + 1;
flips(:,count) = G';
P = G;
a = ceil(numchoices*rand);
G = [P(1:(choices(a,1)-1)) fliplr(P(choices(a,1):choices(a,2))) P((choices(a,2)+1):k)];
end
Results(i) = count;
flips(:,count + 1) = G';
if (count <= br)
time = toc
beep
return
end
end
end
end
time = toc
beep