#Stuff done on Apr. 15, 2010
#(also PRg finished after class)

Help:=proc(): print(`Orbit1(G,i), IsCyclic(G)`):
print(`Losers(G), PRg(n,k) `):
end:


Orbit1:=proc(G,i) local F1,F2,T,f1,f2:
F1:=G[i]:
F2:= F1 union {seq(op(G[f1]),f1 in F1)}:

while F1<>F2 do
F1:=F2:
F2:= F2 union {seq(op(G[f2]),f2 in F2)}:
od:

F1:

end:






#IsCyclic(G): inputs a directed graph in the
#above format and decides whether there exist cycles
IsCyclic:=proc(G) local i:

for i from 1 to nops(G) do

if member(i,Orbit1(G,i)) then
  RETURN(true):
fi:
od:

false:
end:


Losers:=proc(G) local L,W,A,n,Ac,v1,V,i:

if IsCyclic(G) then
  RETURN(FAIL):
fi:

n:=nops(G):
V:={seq(i,i=1..n)}:
L:={}:
W:={}:

for i from 1 to n do
 if G[i]={} then
     L:=L union {i}:
 fi:
od:

A:=L union W:

while A<>V do
Ac:=V minus A:

 for v1 in Ac do
   if G[v1] intersect L<>{} then
       W:=W union {v1}:
   fi:
od:

A:=A union W:
Ac:=V minus A:

 for v1 in Ac do
   if G[v1] minus W={} then
     L:=L union {v1}:  
   fi:
od:
A:=A union L:


od:

L:

end:




#PRg(n,k): the game of removing up to k pennies
#from a pile of n pennies. The output is the directed graph
#in our data-structure for directed graphs G,
#where G is a list of subsets of {1, ..., n} (where n=nops(G))
#evertices are assumed to have names 1 through  n
#and G[i] is the set of vertices reachable from vertex i in one move
#followed by the "key" the list of vertices in their "natural" names.
PRg:=proc(n,k) local V,v,i,T,V1,V2,tv1:
V:=[seq(i,i=0..n)]:

for i from 1 to nops(V) do
  V1[i]:=V[i]:
  V2[V[i]]:=i:
od:


for v in V do
T[v]:={seq(v-i,i=1..min(k,v))}:
T[v]:={seq(V2[tv1],tv1 in T[v])}:
od:


[seq(T[V1[i]],i=1..nops(V))],V:

end: