Python and Combinatorics

Discussion in 'Python' started by Nic, May 16, 2006.

  1. Nic

    Nic Guest

    Hello,
    I've a problem in defining a good Python code useful to articulate the
    following algorithm.
    Can you help me please?
    Thanks a bunch,
    Nic

    1. Insert a number "n".
    Example: 3

    2. List all the numbers < or = to n.
    Example: 1,2,3.

    3. Combine the listed numbers each other.
    Example:
    12
    13
    23

    4. For each combination associate two letters a and b.
    Example:
    12a
    12b
    13a
    13b
    23a
    23b

    5. Combine the new combinations each other, provided that combinations
    including the same couple of numbers (e.g. 12a and 12b) cannot be combined.
    Example:
    12a 13a 23a
    12a 13b 23a
    12a 13b 23b
    12b 13a 23a
    12b 13b 23a
    12b 13b 23b

    PS
    12a 13a 23a and13a 23a 12a are the same thing.
    Nic, May 16, 2006
    #1
    1. Advertising

  2. Nic

    Peter Otten Guest

    Nic wrote:

    [Algorithm that I may have misunderstood]

    > 12a 13a 23a
    > 12a 13b 23a
    > 12a 13b 23b
    > 12b 13a 23a
    > 12b 13b 23a
    > 12b 13b 23b


    What about 12a 13a 23b and 12b 13a 23b?

    Peter

    PS: Please don't top-post.
    Peter Otten, May 16, 2006
    #2
    1. Advertising

  3. Nic

    Nic Guest

    I forgot them. Sorry.
    They should be included.
    Nic

    "Peter Otten" <> ha scritto nel messaggio
    news:e4c0dh$197$03$-online.com...
    > Nic wrote:
    >
    > [Algorithm that I may have misunderstood]
    >
    >> 12a 13a 23a
    >> 12a 13b 23a
    >> 12a 13b 23b
    >> 12b 13a 23a
    >> 12b 13b 23a
    >> 12b 13b 23b

    >
    > What about 12a 13a 23b and 12b 13a 23b?
    >
    > Peter
    >
    > PS: Please don't top-post.
    Nic, May 16, 2006
    #3
  4. Nic

    Peter Otten Guest

    Nic wrote:

    >> PS: Please don't top-post.


    You probably overlooked that :)

    Here's a naive implementation:

    from itertools import izip

    def unique(items, N):
    assert N > 0
    if N == 1:
    for item in items:
    yield item,
    else:
    for index, item in enumerate(items):
    for rest in unique(items[index+1:], N-1):
    yield (item,) + rest

    def repeat(*items):
    assert len(items)
    if len(items) == 1:
    for item in items[0]:
    yield item,
    else:
    for item in items[0]:
    for rest in repeat(*items[1:]):
    yield (item,) + rest

    def render():
    pairs = list(unique(range(1, 4), 2))
    for item in unique(pairs, 3):
    for suffix in repeat(*["ab"]*3):
    yield tuple((a, b, s) for (a, b), s in izip(item, suffix))

    if __name__ == "__main__":
    for item in render():
    print " ".join("%s%s%s" % t for t in item)

    Peter
    Peter Otten, May 16, 2006
    #4
  5. Nic wrote:
    > Hello,
    > I've a problem in defining a good Python code useful to articulate the
    > following algorithm.
    > Can you help me please?
    > Thanks a bunch,
    > Nic
    >
    > 1. Insert a number "n".
    > Example: 3
    >
    > 2. List all the numbers < or = to n.
    > Example: 1,2,3.
    >
    > 3. Combine the listed numbers each other.
    > Example:
    > 12
    > 13
    > 23
    >
    > 4. For each combination associate two letters a and b.
    > Example:
    > 12a
    > 12b
    > 13a
    > 13b
    > 23a
    > 23b
    >
    > 5. Combine the new combinations each other, provided that combinations
    > including the same couple of numbers (e.g. 12a and 12b) cannot be combined.
    > Example:
    > 12a 13a 23a
    > 12a 13b 23a
    > 12a 13b 23b
    > 12b 13a 23a
    > 12b 13b 23a
    > 12b 13b 23b
    >
    > PS
    > 12a 13a 23a and13a 23a 12a are the same thing.


    This might get you some of the way:

    def nkRange(n,k):
    m = n - k + 1
    indexer = range(0, k)
    vector = range(1, k+1)
    last = range(m, n+1)
    yield vector
    while vector != last:
    high_value = -1
    high_index = -1
    for i in indexer:
    val = vector
    if val > high_value and val < m + i:
    high_value = val
    high_index = i
    for j in range(k - high_index):
    vector[j+high_index] = high_value + j + 1
    yield vector


    X = [ ''.join(map(str,x)) + y for x in nkRange(3,2) for y in ['a','b']
    ]
    print X

    def kSubsets( alist, k ):
    n = len(alist)
    for vector in nkRange(n, k):
    ret = []
    for i in vector:
    ret.append( alist[i-1] )
    yield ret

    Y = [ ''.join(x) + y for x in kSubsets( '123', 2 ) for y in ['a','b']]
    print Y

    ['12a', '12b', '13a', '13b', '23a', '23b']

    (a 'cross product' function may also help you - search this Group)

    Gerard
    Gerard Flanagan, May 16, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Carnosaur

    combinatorics question

    Carnosaur, Oct 28, 2003, in forum: C Programming
    Replies:
    17
    Views:
    542
    Carnosaur
    Oct 31, 2003
  2. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    382
    bruno modulix
    Feb 11, 2005
  3. none

    Python and Combinatorics

    none, Oct 24, 2007, in forum: Python
    Replies:
    4
    Views:
    476
    Gerard Flanagan
    Oct 26, 2007
  4. David Palm
    Replies:
    7
    Views:
    107
    Sergio Bayona
    Feb 18, 2010
  5. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Perl Misc
    Replies:
    5
    Views:
    129
    bruno modulix
    Feb 11, 2005
Loading...

Share This Page