Ask Your Question
1

Can I create these sequences with Sage?

asked 2011-09-18 17:53:09 +0100

Grigori gravatar image

Let me start by confessing that I know next to nothing about math and really don't know exactly how to describe what I'm trying here; I hope the below description is adequate.

I am attempting to create a list of all possible 7-digit sequences of the numbers 1, 2, and 3 that add up to 12 (e.g., 1-2-2-3-1-1-2, 2-1-2-3-1-1-2, 2-1-2-3-1-2-1, etc.). I'm not looking merely for the number of sequences, but the actual sequences themselves. Is this something that Sage is capable of and, if so, how would I go about accomplishing this? If not… any suggestions?

Thank you in advance.

Greg

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
3

answered 2011-09-18 18:08:42 +0100

benjaminfjones gravatar image

updated 2011-09-18 23:52:44 +0100

There is a marvelous combinatorial class called IntegerListsLex that returns an iterator (a type of python object that you can iterate over) for lists of integers subject to certain constraints. Try entering IntegerListsLex? at the Sage command line to see the documentation.

Below is an iterator that does the job. The length parameter limits to sequences of length 7, the floor parameter limits the integers to be larger or equal to 1, the ceiling parameter limits the integers to be less or equal to 3.

sage: L = IntegerListsLex(12, length=7, floor=[1]*7, ceiling=[3]*7)
sage: for l in L:
....:     print l
....:     
[3, 3, 2, 1, 1, 1, 1]
[3, 3, 1, 2, 1, 1, 1]
[3, 3, 1, 1, 2, 1, 1]
[3, 3, 1, 1, 1, 2, 1]

etc...

The Lex part of the name indicates that the lists are returned in lexicographic order.

Note that if you sort the sequences, convert to tuples (so that they are hashable), and then uniquify them you get the 3 basic sequences that generate the whole collection by reordering:

sage: L = IntegerListsLex(12, length=7, floor=[1]*7, ceiling=[3]*7)
sage: LS = [ tuple(sorted(i)) for i in L ]
sage: uniq(LS)
[(1, 1, 1, 1, 2, 3, 3), (1, 1, 1, 2, 2, 2, 3), (1, 1, 2, 2, 2, 2, 2)]

Update changed ceiling option to limit the sequence to 1's, 2's, and 3's

edit flag offensive delete link more

Comments

Thanks so much for the info, Benjamin. I have Sage installed and was able to generate the lists. Looking at the result, starting with [6, 1, 1, 1, 1, 1, 1], I think I should have been clearer in my description. I want to limit the numbers used to 1, 2, and 3 (i.e., no 4, 5, 6, etc.), THEN create all possible orderings of those numbers. The results I generated include 4, 5, and 6, and are not limited to 1, 2, and 3. I did a little background work on this, and it looks as though there are basically three series that will fulfill my criteria: [1+1+1+1+2+3+3], [1+1+1+2+2+2+3], and [1+1+2+2+2+2+2] (there could be another I've missed, perhaps?). Having those basic series (I apologize if my terminology is confusing ...(more)

Grigori gravatar imageGrigori ( 2011-09-18 19:57:45 +0100 )edit

Sure, it's an easy change. I somehow missed that part of your question. I've updated the answer now.

benjaminfjones gravatar imagebenjaminfjones ( 2011-09-18 23:53:45 +0100 )edit

That seems to have done the trick; thanks so much, Benjamin!

Grigori gravatar imageGrigori ( 2011-09-19 01:15:08 +0100 )edit
2

answered 2011-09-19 11:55:05 +0100

updated 2011-09-19 12:15:46 +0100

A composition of a nonnegative integer n is an ordered list of positive integers with total sum n, so you can call Compositions, specifying the maximum term:

sage: P = Compositions(4, max_part=2)
sage: P.list()
[[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
sage: list(P)
[[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

sage: list(Compositions(12, length=7, max_part=3))
[[3, 3, 2, 1, 1, 1, 1], [3, 3, 1, 2, 1, 1, 1], [3, 3, 1, 1, 2, 1, 1], ...
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: 2011-09-18 17:53:09 +0100

Seen: 1,414 times

Last updated: Sep 19 '11