# Can I create these sequences with Sage?

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

Sort by » oldest newest most voted

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

more

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)

( 2011-09-18 19:57:45 +0200 )edit

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

( 2011-09-18 23:53:45 +0200 )edit

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

( 2011-09-19 01:15:08 +0200 )edit

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], ...

more