ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 13 Jun 2013 05:58:28 -0500Generating permutations of coefficientshttp://ask.sagemath.org/question/10229/generating-permutations-of-coefficients/I have created the following function to return all pairs `(n, k)` such that a slightly altered binomial coefficient is less than or equal to a certain `N`:
bin = lambda n, k : binomial(n + k - 1, k)
def nkfilter(N):
pairs = []
for n in range(2, N+1):
for k in range(1, n):
if bin(n, k) <= N:
pairs.append([n, k])
print '\n (n, k)\n'
return pairs
This prints out the following:
example = nkfilter(8); print example
(n, k)
[[2, 1], [3, 1], [3, 2], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1]]
I now would like to take this `n` and generate a tuple of length `n`: `(a_1,..., a_n)`, for which all the `a_i`s are less than or equal to `k`. I have been considering `permutations` to accomplish this, but I believe I need to first generate `list_of_numbers_less_than_k` and then take `permutations(n, list_of_numbers)`.
However I am not sure which data types to use, and how to generate these `n`-length tuples. Thu, 13 Jun 2013 04:57:57 -0500http://ask.sagemath.org/question/10229/generating-permutations-of-coefficients/Answer by tmonteil for <p>I have created the following function to return all pairs <code>(n, k)</code> such that a slightly altered binomial coefficient is less than or equal to a certain <code>N</code>:</p>
<pre><code>bin = lambda n, k : binomial(n + k - 1, k)
def nkfilter(N):
pairs = []
for n in range(2, N+1):
for k in range(1, n):
if bin(n, k) <= N:
pairs.append([n, k])
print '\n (n, k)\n'
return pairs
</code></pre>
<p>This prints out the following:</p>
<pre><code>example = nkfilter(8); print example
(n, k)
[[2, 1], [3, 1], [3, 2], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1]]
</code></pre>
<p>I now would like to take this <code>n</code> and generate a tuple of length <code>n</code>: <code>(a_1,..., a_n)</code>, for which all the <code>a_i</code>s are less than or equal to <code>k</code>. I have been considering <code>permutations</code> to accomplish this, but I believe I need to first generate <code>list_of_numbers_less_than_k</code> and then take <code>permutations(n, list_of_numbers)</code>. </p>
<p>However I am not sure which data types to use, and how to generate these <code>n</code>-length tuples. </p>
http://ask.sagemath.org/question/10229/generating-permutations-of-coefficients/?answer=15075#post-id-15075By the way, you can shorten the definition of your function nkfilter by doing:
sage: nkfilter = lambda N : [[n, k] for n in range(2, N+1) for k in range(1, n) if bin(n, k) <= N]
Thu, 13 Jun 2013 05:58:28 -0500http://ask.sagemath.org/question/10229/generating-permutations-of-coefficients/?answer=15075#post-id-15075Answer by tmonteil for <p>I have created the following function to return all pairs <code>(n, k)</code> such that a slightly altered binomial coefficient is less than or equal to a certain <code>N</code>:</p>
<pre><code>bin = lambda n, k : binomial(n + k - 1, k)
def nkfilter(N):
pairs = []
for n in range(2, N+1):
for k in range(1, n):
if bin(n, k) <= N:
pairs.append([n, k])
print '\n (n, k)\n'
return pairs
</code></pre>
<p>This prints out the following:</p>
<pre><code>example = nkfilter(8); print example
(n, k)
[[2, 1], [3, 1], [3, 2], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1]]
</code></pre>
<p>I now would like to take this <code>n</code> and generate a tuple of length <code>n</code>: <code>(a_1,..., a_n)</code>, for which all the <code>a_i</code>s are less than or equal to <code>k</code>. I have been considering <code>permutations</code> to accomplish this, but I believe I need to first generate <code>list_of_numbers_less_than_k</code> and then take <code>permutations(n, list_of_numbers)</code>. </p>
<p>However I am not sure which data types to use, and how to generate these <code>n</code>-length tuples. </p>
http://ask.sagemath.org/question/10229/generating-permutations-of-coefficients/?answer=15074#post-id-15074I am not sure i understand your question. If you want, for a given `(n,k)`, get all the possible tuples `(a_1, ..., a_n)` where `1 <= a_i <= k` for all i you can use [multidimensional enumeration](http://www.sagemath.org/doc/reference/misc/sage/misc/mrange.html):
sage: car = lambda n,k : cartesian_product_iterator([xrange(1,k+1) for i in range(n)])
sage: list(car(4,2))
[(1, 1, 1, 1),
(1, 1, 1, 2),
(1, 1, 2, 1),
(1, 1, 2, 2),
(1, 2, 1, 1),
(1, 2, 1, 2),
(1, 2, 2, 1),
(1, 2, 2, 2),
(2, 1, 1, 1),
(2, 1, 1, 2),
(2, 1, 2, 1),
(2, 1, 2, 2),
(2, 2, 1, 1),
(2, 2, 1, 2),
(2, 2, 2, 1),
(2, 2, 2, 2)]
Note that i am creating an iterator and not a list, so that, if i do something like
sage: for i in car(1000,1000):
....: blabla(i)
the tuples are created on the fly and my memory won't get stuck.
Thu, 13 Jun 2013 05:52:44 -0500http://ask.sagemath.org/question/10229/generating-permutations-of-coefficients/?answer=15074#post-id-15074