%%%%%%% 
% powerflipperplus.m
% Author: Lance Harden, Davidson College
% June 2006
% 
% Description: A more efficient, more practical version of powerflipper,
% powerflipperplus differs in that it only saves the flip histories of
% trials that reached the home permutation in br flips or less. Unlike
% powerflipper, powerflipperplus ends a trial if it reaches the home
% permutation.

function [orderedflips,bigbox] = powerflipperplus(s,t,I,n,br)
orderedflips = cell(1,1);
bigbox = [];
norder = 0;

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 = [];
            isorder = 0;
            
            for u = 1:br
                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
                
                if ( all(G == 1:k) || all(G == -k:-1) )
                    bigbox(i,u) = 1;
                    isorder = 1;
                else
                    bigbox(i,u) = 0;
                end
            end
            
            flips(:,count + 1) = G';
            if isorder == 1
                norder = norder + 1;
                orderedflips{norder,1} = flips;
            end
        end
    else
        for i = 1:n
            G = I;
            count = 0;
            flips = [];
            isorder = 0;
            
            for u = 1:br
                count = count + 1;
                flips(:,count) = G';
                P = G;
                a = ceil(k*rand);
                G = [fliplr(P(1:a)) P(a+1:k)];
                
                if all(G == 1:k)
                    bigbox(i,u) = 1;
                    isorder = 1;
                else
                    bigbox(i,u) = 0;
                end                
            end
            
            flips(:,count + 1) = G';
            if isorder == 1
                norder = norder + 1;
                orderedflips{norder,1} = flips;
            end         
        end
    end
else
    if t == 's'
        for i = 1:n
            G = I;
            count = 0;
            flips = [];
            isorder = 0;
            
            for u = 1:br
                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
                
                if ( all(G == 1:k) || all(G == -k:-1) )
                    bigbox(i,u) = 1;
                    isorder = 1;
                else
                    bigbox(i,u) = 0;
                end                
            end
            
            flips(:,count + 1) = G';
            if isorder == 1
                norder = norder + 1;
                orderedflips{norder,1} = flips;
            end          
        end
    else
        for i = 1:n
            G = I;
            count = 0;
            flips = [];
            isorder = 0;
            
            for u = 1:br
                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)];
                
                if all(G == 1:k)
                    bigbox(i,u) = 1;
                    isorder = 1;
                else
                    bigbox(i,u) = 0;
                end
            end

            flips(:,count + 1) = G';
            if isorder == 1
                norder = norder + 1;
                orderedflips{norder,1} = flips;
            end          
        end
    end
end

time = toc
beep