Creating combination of sequences

[Minho Chae]

Hello, python lovers!!

I'm trying to create combinations of sequences.

For example, if the sequence is 'acgt' and the length is 8,
then I would like to have 4^8 results such as
'aaaaaaaa', 'aaaaaaac', 'aaaaaaag', 'aaaaaaat', ... 'tttttttt'

Is there an easy way doing this?

Any help will be greatly appreciated.
Minho

[Mike C. Fletcher]

Minho Chae wrote:

Hello, python lovers!!

I'm trying to create combinations of sequences.

A simple recursive generator should produce what you want while being
fairly easy to read...

def permute( choices, length=8 ):

.... if length > 1:
.... for suffix in permute(choices,length-1):
.... for choice in choices:
.... yield choice + suffix
.... else:
.... for choice in choices:
.... yield choice

That's not the same ordering you wanted, but that's merely a matter of
swapping the order of choice and suffix.

HTH,
Mike

________________________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://www.vrplumber.com
http://blog.vrplumber.com

[Josiah Carlson]

"Mike C. Fletcher" <mc******@rogers.com> wrote:

Minho Chae wrote:

Hello, python lovers!!

I'm trying to create combinations of sequences.

A simple recursive generator should produce what you want while being
fairly easy to read...

>>> def permute( choices, length=8 ): ... if length > 1:
... for suffix in permute(choices,length-1):
... for choice in choices:
... yield choice + suffix
... else:
... for choice in choices:
... yield choice

That's not the same ordering you wanted, but that's merely a matter of
swapping the order of choice and suffix.

Or even the better non-recursive 'base-k' version...

Note that a permutation is just a reordering of the set of elements that
one has. There are only n! number of permutations of any arbitrary
sequence (assuming the n items are unique).

I can't remember the mathematical name of what the OP wanted (because my
brain is dumb today).
def blah(choices, length, force_string=0):
lch = len(choices)
length = long(length)
if lch <= 0:
raise ValueError, "choices must be a sequence of at least 1 item"
if length <= 0:
raise ValueError, "length must be an integer >= 1"
#use longs and a while loop because we may be dealing with sequences
#>= 2**31 in size, and we may be using Python < 2.4
cur = 0L
m = lch**length
while cur < m:
l = [choices[(cur//(lch**i))%lch] for i in xrange(length-1, -1, -1)]
if force_string:
yield ''.join(map(str, l))
else:
yield l
cur += 1

for i in blah('atcg', 2, 1): ... print i
...
aa
at
ac
ag
ta
tt
tc
tg
ca
ct
cc
cg
ga
gt
gc
gg

- Josiah

[Andrew Dalke]

Minho Chae wrote:

I'm trying to create combinations of sequences.

For example, if the sequence is 'acgt' and the length is 8,
then I would like to have 4^8 results such as
'aaaaaaaa', 'aaaaaaac', 'aaaaaaag', 'aaaaaaat', ... 'tttttttt'

Given the DNA base characters you use for your test case, do you
know about biopython.org?

Here is a solution to your problem.

def cycle(chars, length):
"""Generate 'length' copies of chars[0], then length of chars[1]
then of chars[2], etc. When chars is exhausted, start again.
"""
counter = xrange(length)
while 1:
for c in chars:
for _ in counter:
yield c

def once(chars, length):
"""Generate 'length' copies of chars[0], then of chars[1], etc.
then of chars[-1]. When chars is exhausted, stop.
"""
counter = xrange(length)
for c in chars:
for _ in counter:
yield c

def all_combinations(chars, size):
"""Generate all words combinations using items from chars as
the characters for each position. If chars is in lexiographic
order then so is the list of generated words.

for word in all_combinations("01", 3):

... print word
...
000
001
010
011
100
101
110
111
"""
if size == 0:
return

N = len(chars)
gens = [once(chars, N**(size-1))]
for i in range(size-2, -1, -1):
gens.append(cycle(chars, N**i))

def next(gen):
return gen.next()

while 1:
yield "".join(map(next, gens))

def test():
text = "acgt"
n = 8
i = -1
for i, term in enumerate(all_combinations(text, n)):
print term
print (i+1), "combinations found"
if n:
assert (i+1) == len(text) ** n, (i, text, n)
else:
assert i == -1, i

if __name__ == "__main__":
test()
Andrew
da***@dalkescientific.com

[Scott David Daniels]

Minho Chae wrote:

I'm trying to create combinations of sequences.

For example, if the sequence is 'acgt' and the length is 8,
then I would like to have 4^8 results such as
'aaaaaaaa', 'aaaaaaac', 'aaaaaaag', 'aaaaaaat', ... 'tttttttt'

Is there an easy way doing this?

You are basically counting in base 4 here.

import array

def generate(digits='acgt', length=8):
base = len(digits)
positions = range(length)
positions.reverse()
r = array.array('c', digits[0] * length)
for number in range(base**length):
for digit in positions:
number, v = divmod(number, base)
r[digit] = digits[v]
yield r.tostring()

for result in generate('ab', 2):
print result
-Scott David Daniels
Sc***********@Acm.Org

[Hung Jung Lu]

mi********@yahoo.com (Minho Chae) wrote:

I'm trying to create combinations of sequences.
For example, if the sequence is 'acgt' and the length is 8,
then I would like to have 4^8 results such as
'aaaaaaaa', 'aaaaaaac', 'aaaaaaag', 'aaaaaaat', ... 'tttttttt'

strings = lambda Xs, k: reduce(lambda r, i: [p + x for p in r for x
in Xs], range(k), [''])

print strings('acgt', 8)

This has been recently discussed. See

http://groups.google.com/groups?hl=e...ing.google.com
http://groups.google.com/groups?hl=e...it%40yahoo.com

and other previous threads and follow-ups. This question seems to pop
up more often than I thought.

Kamsahapnida,

Hung Jung