Ask Your Question
0

Generating permutations of coefficients

asked 2013-06-13 04:57:57 -0500

JoshIzzard gravatar image

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 flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2013-06-13 05:52:44 -0500

tmonteil gravatar image

updated 2013-06-13 05:56:36 -0500

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.

edit flag offensive delete link more
0

answered 2013-06-13 05:58:28 -0500

tmonteil gravatar image

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]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-06-13 04:57:57 -0500

Seen: 109 times

Last updated: Jun 13 '13