Math Forum / Math Software / Maple / October 2008

Enjoy!

 1, 2, 3,... 9

Do you mean that you reject a sequence when it contains any
permutation of {1,... 9} and accept it otherwise? If so, here's a
monitor that, when fed a sequence, tracks its recent history and
deduces the values prohibited in the next position:

Monitor := proc() module()
 export taboos, update;
 local history_, taboos_;
 history_,taboos_ := [],{};

 taboos := ()-> taboos_;
 update := proc(n)
   min(nops(history_) + 1, 8);
   history_ := [history_[], n][-%..-1];
   {history_[]};
   if nops(%) = 8 then  {$ 1..9} minus %;  else  {};  fi;
   taboos_ := %;
 end;
end; end:

Demo of the first taboo appearing:

m:= Monitor():
map(m:-update, [2,4,3,5,6,8]):
m:-update(9), m:-update(1);
                             {}, {7}

Set up one monitor for each selection. To generate the next symbol:
- select those monitors appropriate to the current sequence index
- join all those monitors' taboos
- randomly pick a symbol from that set's complement
- feed the symbol to the monitors and return it.
I don't know if the next symbol can ever actually fail to exist. The
code below also keeps the sequence index bounded by wrapping.

Sequence := proc(MaxStride) module()
 export emit;
 local i_, monitors_, currentStrides, pick;
 i_,monitors_ := 0, [Monitor $ MaxStride]();

 currentStrides := proc()
   select(a-> evalb(irem(i_,a) = 0), [$ 1..MaxStride]);
   if nops(%) = MaxStride then  i_ := 1;  else  i_ := i_ + 1;  fi;
   return %%;
 end;
 pick := a-> a[rand(1..nops(a))()];
 emit := proc()
   local mon, result;
   mon := [seq](monitors_[s], s=currentStrides());
   (`union`@op@map)(m-> m:-taboos(), mon);
   if nops(%) = 9 then  error "No feasible symbol";  fi;
   result := pick({$ 1..9} minus %);
   map(m-> m:-update(result), mon);
   return result;
 end;
end; end:

Now we can look at a sequence and its selections:

s:= Sequence(3):
[s:-emit $ 30]();
     [2, 6, 6, 6, 9, 9, 5, 1, 2, 4, 6, 5, 5, 3,
      7, 7, 2, 7, 1, 6, 2, 8, 8, 2, 4, 4, 9, 2, 4, 9]

seq([seq](%[1+a*i], i=0..floor((30-1)/3)), a=1..3);
     [2, 6, 6, 6, 9, 9, 5, 1, 2, 4],
     [2, 6, 9, 5, 2, 6, 5, 7, 2, 1],
     [2, 6, 5, 4, 5, 7, 1, 8, 4, 2]

The results have a fair amount of repetition by nature of the
constraint. You might try biasing the random choice away from
recently-emitted symbols to increase variation.
Let's see with a timing function if this naive method is practical
for your desired length of 9^11 elements:

Time:= proc(p)
 local t, r;
 t := time();
 r := p(args[2 .. -1]);
 t := time() - t;
 if procname :: indexed and op(procname) = 'silent'
   then  return r, t;  fi;
 print(`s elapsed` = t);
 return r;
end:

s:= Sequence(30):
Time([s:-emit $ 1000]):
                        s elapsed = 1.687

s:= Sequence(1000):
Time[silent]([s:-emit $ 100]) [-1]:
9^11/100 * %/60^2/24/365. * 'years';
                        19.30468532 years

About 19 years for 9^11 elements ;/  The culprit is the first line of
currentMonitors() in Sequence, which finds the divisors of sequence
index i_ up to MaxStride. If there is a way to do that in less than
O(MaxStride) time then you could substitute it for the first line of
currentMonitors().

Martin