# 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_is 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.

edit retag close merge delete

Sort by » oldest newest most voted

I 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:

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.

more

By 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]

more