6
$\begingroup$

I am looking for an effective way to generate a complete list of integer sequences

 {a_1,a_2,...,a_n} 

of the length $n$ such that $$0\le a_1\le a_2\le\dots\le a_n< m,$$

with two integer parameters $n$ and $m$.

I can imagine to perform this via

Table[Sort[IntegerDigits[x-1,m,n]],{x,m^n}] 

and then delete duplicates, but surely there should exist a much more effective way.

$\endgroup$
0
7
$\begingroup$

Since we can map such sequence

$$0\leq a_1\leq a_2\leq a_3 \leq \cdots \leq a_{n-1}\leq a_n < m $$ to $$0 < b1=a_1+1 < b2=a_2+2 < b3=a_3+3 <\cdots < b_n=a_n+n < m+n $$ and $\{b_1,b_2,\cdots b_n\}$ is the n subsets of Range[m+n-1]

And we can get $\{a_1,a_2,\cdots a_n\}$ from $\{b_1,b_2,\cdots b_n\}-\{1,2,\cdots,n\}$

m = 8;
n = 5;
list = Subsets[Range[m+n-1], {n}]
Subtract[#, Range[n]] & /@ list
$\endgroup$
3
  • 1
    $\begingroup$ nice!!!. You probably meant With[{m = 10, n = 5}, Subtract[1 + #, Range[n]] & /@ Subsets[Range[m + n - 1], {n}]]? (+1) $\endgroup$
    – kglr
    Dec 2 '20 at 12:53
  • $\begingroup$ @kglr Thanks! I make mistake. $\endgroup$
    – cvgmt
    Dec 2 '20 at 12:58
  • $\begingroup$ That's really amazing! Thanks a lot! $\endgroup$
    – drer
    Dec 2 '20 at 14:30
3
$\begingroup$

With a small trick, we can do this using the Table function. This is necessary because Table has the attribute HoldAll.

For a small example, we first set m and n:

m=4;
n=2;

We then create a list of variables and a list of iterators and join them into the body of Table:

var = Table[x[i], {i, n}];
iter = Table[{x[i], x[i - 1] + 1, m-1}, {i, n}] /. x[0] -> -1;
body = PrependTo[iter, var]

Finally we apply Table to the body and Flatten to get ride of superfluous braces:

Flatten[Table @@ body, 1]

This gives:

{{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}}
$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .