4
$\begingroup$

I am looking for an effective way of generating all sequences of length $m$ of integer numbers $\{n_1,n_2\dots n_m\}$ such that

1) $0\le n_i\le N$;

2) $n_{i+1}\ge n_i$ for odd $i$; $n_{i+1}\le n_i$ for even $i$.

Any hint is appreciated.

$\endgroup$

4 Answers 4

7
$\begingroup$

In this answer I will give a method for computing how many such (odd-length) sequences there are. Let $N=10$ and consider the matrix:

$$ M = \left( \begin{array}{ccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 1 & 2 & 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 1 & 2 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 1 & 2 & 3 & 4 & 5 & 6 & 6 & 6 & 6 & 6 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 7 & 7 & 7 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 8 & 8 & 8 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 9 & 9 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 10 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \end{array} \right) $$

Then, the number of sequences of length $2n+1$ is given by:

$$ \sum_{i, j}^{N+1} (M^n)_{i, j} $$

Let's check this against the other answers:

mat = Table[Min[i, j], {i, 11}, {j, 11}];
mat //MatrixForm //TeXForm

$$\left( \begin{array}{ccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 1 & 2 & 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 1 & 2 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 1 & 2 & 3 & 4 & 5 & 6 & 6 & 6 & 6 & 6 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 7 & 7 & 7 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 8 & 8 & 8 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 9 & 9 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 10 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \end{array} \right) $$

Number of sequences:

Total[MatrixPower[mat, 3], 2]

1437799

Comparing with @Coolwaters' solution:

bigN=10;
m=7;

res = With[{tup=Tuples[Range[0,bigN],m]},
    Pick[
        tup,
        Total[UnitStep[Differences[Transpose[tup]] PadRight[{1,-1},m-1,"Periodic"]]],
        m-1
    ]
];
res //Length

1437799

The above approach could also be used to determine how many sequences start with 0, 1, etc. by only performing a partial sum. For example:

MatrixPower[mat, 3] . ConstantArray[1, 11]
Table[
    Count[res, {i, __}],
    {i, Range[10, 0, -1]}
]

{26818, 53130, 78441, 102277, 124194, 143786, 160692, 174602, 185262, 192478, 196119}

{26818, 53130, 78441, 102277, 124194, 143786, 160692, 174602, 185262, 192478, 196119}

$\endgroup$
1
  • $\begingroup$ Can you add a few words explaining why this works? $\endgroup$ Jan 10, 2018 at 17:53
6
$\begingroup$

By brute force:

bigN = 4;
m = 3;

With[{tup = Tuples[Range[0, bigN], m]},
  Pick[tup, Total[UnitStep[Differences[Transpose[tup]]
     PadRight[{1, -1}, m - 1, "Periodic"]]], m - 1]]
{{0,0,0},{0,1,0},{0,1,1},{0,2,0},{0,2,1},{0,2,2},{0,3,0},{0,3,1},{0,3,2},{0,3,3},{0,4,0},{0,4,1},{0,4,2},{0,4,3},{0,4,4},{1,1,0},{1,1,1},{1,2,0},{1,2,1},{1,2,2},{1,3,0},{1,3,1},{1,3,2},{1,3,3},{1,4,0},{1,4,1},{1,4,2},{1,4,3},{1,4,4},{2,2,0},{2,2,1},{2,2,2},{2,3,0},{2,3,1},{2,3,2},{2,3,3},{2,4,0},{2,4,1},{2,4,2},{2,4,3},{2,4,4},{3,3,0},{3,3,1},{3,3,2},{3,3,3},{3,4,0},{3,4,1},{3,4,2},{3,4,3},{3,4,4},{4,4,0},{4,4,1},{4,4,2},{4,4,3},{4,4,4}}
$\endgroup$
5
$\begingroup$

It is not easy to make fast as this involves a lot of copying anyways. Still, the following can be a bit faster than Coolwater's proposal:

bigN = 10;

cf = With[{nn = bigN},
   Compile[{{a, _Integer, 1}},
    Block[{k = Length[a]},
     If[OddQ[k],
      Table[Join[a, {i}], {i, Compile`GetElement[a, k], nn}],
      Table[Join[a, {i}], {i, 0, Compile`GetElement[a, k]}]
      ]
     ],
    CompilationTarget -> "C",
    RuntimeAttributes -> {Listable},
    Parallelization -> True,
    RuntimeOptions -> "Speed"
    ]
   ];
f[data_] := Flatten[cf[data], 1];

Some test timings from my quad core machine:

m = 7;
bla = Nest[f, Transpose[{Range[0, bigN]}], m - 1]; // RepeatedTiming // First
blubb = With[{tup = Tuples[Range[0, bigN], m]}, 
    Pick[tup, 
     Total[UnitStep[
       Differences[Transpose[tup]] PadRight[{1, -1}, m - 1, 
         "Periodic"]]], m - 1]]; // RepeatedTiming // First
Max[Abs[blubb - bla]]

0.69

3.608

0

Note that for m < 5, Coolwater's solution is quicker (at least for bigN = 10).

$\endgroup$
2
$\begingroup$

Actually it is not an answer to the original question but rather an extended comment on the answer of Carl Woll. As it appears to be too lengthy I hope nobody will mind its publishing. It extends the previous answer onto the case of even sequence lengths and besides allows simple counting of the total number of sequences with given first and last elements.

As the indexing of the states plays no role with regard to counting it is advantageous to let the smallest number in the sequences of the original question be 1 instead of 0 (correspondingly the largest number $n$ is $N+1$ of the original question).

Further, it is convenient to introduce the $n\times n$ "all-ones" upper anti-triangular matrix $\Lambda_n$ and anti-diagonal matrix $\Gamma_n$, given below for $n=5$ as example:

$$\Lambda_5 = \left( \begin{array}{ccccccccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ \end{array} \right),\quad \Gamma_5 = \left( \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ \end{array} \right).$$

Note that $\Lambda$ is anti-diagonal symmetric to square root of the matrix $M$ introduced by Carl Woll.

Then, the elements $\Omega^{(n,k)}_{ij}$ of the matrix: $$\Omega^{(n,k)}=\Lambda^{k-1}_n\Gamma^{k-1}_n$$ give the total number of sequences of length $k$ starting with $i$ and ending with $j$. Note that $\Gamma^{k-1}$ is either $\Gamma$ for even $k$ or the identity matrix $I$ for odd $k$. Note also that $\Gamma$ matrix only permutes the elements of $\Lambda^{k-1}$ placing them into the "correct" positions.

The sum of all elements of the matrix (or equivalently the product $u.\Omega.u\equiv u.\Lambda^{k-1}.u$, with $u=\{1,1,\dots,1\}$ being $n$-dimensional "all-ones" vector) gives the total number of sequences of length $k$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.