% riffle shuffle demonstration 
% Mark Embree
% embree@vt.edu

 N = 26;                              % deck size (N=26 makes a good demo)
 shuffles = ceil(1.5*log2(N));

 prob = zeros(N,1);
 for k=1:N 
    prob(k) = nchoosek(N,k)/(2^N);
 end
 P = cumsum(prob);

 cuts = zeros(shuffles,1);
 deck = [1:N];
 t=linspace(0,1,50);

 figure(4)
 for k=1:shuffles

% plot the deck before a shuffle

    clf, set(gcf,'doublebuffer','on')
    axis([0 N+1 -2 2]), axis off, hold on
    decktxt = [];
    for j=1:N
       decktxt(j)=text(j,0,sprintf('%d',deck(j)),'fontweight','bold');
    end
    pause(2)

% pick the place to split the deck

    cuts(k) = max(find([0;P]<rand));
    axis([0 N+1 -2 2]), axis off, hold on
    for j=1:cuts(k)
       delete(decktxt(j))
       decktxt(j)=text(j,0,sprintf('%d',deck(j)),'fontweight','bold','color','red');
    end
    for j=cuts(k)+1:N
       delete(decktxt(j))
       decktxt(j)=text(j,0,sprintf('%d',deck(j)),'fontweight','bold','color','blue');
    end
    cutline = plot(cuts(k)+.85*[1 1],.5*[-1 1], 'k-','linewidth',2);

% display size of split deck

    outtxt(1)=text(0,-1.2,sprintf('Shuffle #%d',k),'fontsize',20,'color','r');
    outtxt(2)=text(0,-1.5,sprintf('Deck cut into %d cards (left) and %d cards (right)',cuts(k),N-cuts(k)),'fontsize',20,'color','r');
    pause(2)

% animate the splitting of the deck

    left  = deck(1:cuts(k));
    right = deck(cuts(k)+1:end);
    lefttxt = decktxt(1:cuts(k));
    righttxt = decktxt(cuts(k)+1:end);
    shift = (1+(N-max(length(left), length(right))))/2;
    delete(cutline); delete(outtxt(1)); delete(outtxt(2));
    for m=1:length(t)
%       clf, axis([0 N+1 -2 2]), axis off
       for j=1:cuts(k)
          xpos = (1-t(m))*j+t(m)*(shift+j);
          ypos = (1-t(m))*0+t(m)*1;
          delete(lefttxt(j))
          lefttxt(j) = text(xpos,ypos,sprintf('%d',deck(j)),'fontweight','bold','color','red');
       end
       for j=cuts(k)+1:N
          xpos = (1-t(m))*j+t(m)*(shift+j-cuts(k));
          ypos = (1-t(m))*0+t(m)*(-1);
          delete(righttxt(j-cuts(k)))
          righttxt(j-cuts(k)) = text(xpos,ypos,sprintf('%d',deck(j)),'fontweight','bold','color','blue');
       end
       drawnow
    end
    leftpos = shift+[1:cuts(k)];
    rightpos = shift+[1:N-cuts(k)];

% simulate and animate the merging of the deck

    deck = [];
    t=linspace(0,1,25);
    for j=1:N
       d = length(left)+length(right);        % # of cards not yet merged
       if (rand*d)<length(left)
          deck(j) = left(1);
          for m=1:length(t)
              xpos = (1-t(m))*leftpos(1)+t(m)*j;
              ypos = (1-t(m))*1+t(m)*0;
              delete(lefttxt(1));
              lefttxt(1) = text(xpos,ypos,sprintf('%d',deck(j)),'fontweight','bold','color','red');
              drawnow
          end  
          decktxt(j) = lefttxt(1);
          left = left(2:end);
          leftpos = leftpos(2:end);
          lefttxt = lefttxt(2:end);
       else
          deck(j) = right(1); 
          for m=1:length(t)
              xpos = (1-t(m))*rightpos(1)+t(m)*j;
              ypos = (1-t(m))*(-1)+t(m)*0;
              delete(righttxt(1));
              righttxt(1) = text(xpos,ypos,sprintf('%d',deck(j)),'fontweight','bold','color','blue');
              drawnow
          end  
          decktxt(j) = righttxt(1);
          right = right(2:end);
          rightpos = rightpos(2:end);
          righttxt = righttxt(2:end);
       end
    end

% count rising sequences

    riseseq(k) = 1;
    [junk,deckindx] = sort(deck);
    for j=2:N
       if deckindx(j)<deckindx(j-1), riseseq(k) = riseseq(k)+1; end
    end

   pause(2)
% identify the rising sequences
   if riseseq(k)>1
      seq = []; card = 1; total = 0;
      seqcnt = 1; 
      seq = [seq;find(deck==card)];
      card = card+1; 
      while (card <= N)
          next = find(deck==card);
          if (next<seq(end))

% shift sequence up and initialize new sequecne

             for m=1:length(t)
                ypos = 1.5*t(m)*(1-(seqcnt-1)/(riseseq(k)-1));
                for j=1:length(seq)
                    delete(decktxt(seq(j)))
                    txt = text(seq(j),ypos,sprintf('%d',deck(seq(j))),'fontweight','bold','color','black');
                    decktxt(seq(j)) = txt;
                end
                drawnow
             end
             seq = [next]; 
             seqcnt = seqcnt+1;
          else 
             seq = [seq;next];
          end 
          card = card+1; 
      end

% color last rising sequence black

      for j=1:length(seq)
          delete(decktxt(seq(j)))
          txt = text(seq(j),0,sprintf('%d',deck(seq(j))),'fontweight','bold','color','black');
          decktxt(seq(j)) = txt;
      end
      drawnow
   end

% display rising sequence information

    text(5,-1.2,sprintf('After shuffle #%d',k),'fontsize',20,'color','r')
    text(5,-1.5,sprintf('%d rising sequences',riseseq(k)),'fontsize',20,'color','r')
    pause(4)
 end
