On a problem posed by M.R.Khalil (for the record)

On a problem posed by M.R. Khalil (For the record)

For some positive integers $N$ and $L$ ,if is asked to generate -print- in lexical order the integer sequences $f\left( {i : 0 \leq i < N}\right)$ satisfying

$\left( 0\right) \;\left( {A,i : 0 \leq i < N : 0 \leq {P}_{i} < L}\right)$ (1) $f$ is ascending,i.e. $\left( {\underline{A}i,j : 0 \leq i < j < N}\right) .\;f\left( i\right) \leq f\left( j\right)$

An f-sequence containing n different values (1nL) can be represented by two sequences of length n , v (of values) and fr (of frequencies) satisfying

$\left( 2\right) \;\left( {A,i : 1 \leq i \leq n : 0 \leq v,i < k}\right)$ (3) $v$ is ascending $\left( 4\right) \;\left( {A,i : 1 \leq i \leq n : 1 \leq {p}{r.i}}\right)$ $\left( 5\right) \;\left( {5,i : 1 \leq i \leq n : {f}{n.i}}\right) = N$

and coupled to $f$ by

(6) $\left( {\underline{A}i : 1 \leq i \leq n : \left( {{E}{j}\because \left( {A}{k} : j \leq k < j + {F}{r,i} : {F}{k} = v,i}\right) }\right) }\right)$

Since $n \leq \min \left( {N,L}\right)$ , $n$ is at most $N$ and may be much smaller. From given $v$ - and fr- sequences, the corresponding $p$ - sequence is generated by the following (trivial) block

"print $f$ ：[var i:int; i:=0

$$ \begin{array}{l} j \underline {{\underline {{d o}}}} i \neq n \rightarrow 1 [ \underline {{v a r}} j: i n t; j := 0; i := i + 1 \ ; \underline {{d o}} j \neq f r. i \rightarrow p r i n t (v. i); j := j + 1 \quad o d ] ] \ \prod_ {i} ^ {o d} \ \end{array} $$

The program is 11 var n: int; var v, fr: array of int i n:=1 ; v.1:=0 ; fr.1:=N ; do n≠0→ 11 var tv, tfr: int ; "print p" ; if v.n < L-1 → tfr:= 1 [ ] v.n = L-1 → tfr:= fr.n + 1 ; n:=n-1 f { n>0 ⇒ v.n < L-1 ; (S i : 1 ≤ i ≤ n : fr.i) + tfr = N+1} ; if n=0 → skip { successor construction aborted} [ ] n>0 → tv:= v.n + 1 {t.v < L} ; if fr.n > 1 → fr.n:= fr.n-1 ; n:=n+1 [ ] fr.n = 1 → skip f; v.n := tv ; fr.n := tfr fi

The point of the $(v, p_r)$ -representation is that the lexical successor can be constructed without repetition. The point of the above program is the separate successive determinations of the "top frequency" and the "top value".

Nuenen, 15 August 1985

prof. dr. Edsger W. Dgiksha Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 United States of America