First time here? Check out the FAQ!

Ask Your Question
1

Can I create these sequences with Sage?

asked 13 years ago

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

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
3

answered 13 years ago

benjaminfjones gravatar image

updated 13 years ago

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

Preview: (hide)
link

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 ( 13 years ago )

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

benjaminfjones gravatar imagebenjaminfjones ( 13 years ago )

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

Grigori gravatar imageGrigori ( 13 years ago )
2

answered 13 years ago

updated 13 years ago

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], ...
Preview: (hide)
link

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: 13 years ago

Seen: 1,445 times

Last updated: Sep 19 '11