set partitioning

Discussion in 'Python' started by hymort@hotmail.com, May 1, 2006.

  1. Guest

    Can someone tell me of a good algorithm to partition a set of n
    elements into m non-empty, disjoint subsets, where each subset has size
    k?
    , May 1, 2006
    #1
    1. Advertising

  2. Guest

    Also, if I do not care about the number of subsets, what is a good
    algorithm to partition a set of n elements into non-empty, disjoint
    subsets of size k?
    , May 1, 2006
    #2
    1. Advertising

  3. Guest

    Something like this, or am I missing something?

    def partition(List, n, m, k):
    if n!=m*k:
    raise "sorry, too many or too few elts"
    D = {}
    for x in List:
    D[x] = 1
    if len(D)!=n:
    raise "sorry (2) you lied about the number"
    List2 = D.keys()
    result = []
    for i in range(m):
    result.append( List2[i*k: i*k+k] )
    return result
    ?

    If this was a take home exam problem,
    you should be ashamed of yourself!
    -- Aaron Watters

    ===

    It's easy. All you have to do is hit
    the right keys at the right time and
    the organ plays itself. -- J.S. Bach
    , May 1, 2006
    #3
  4. Guest

    Hello,

    Not quite what I'm looking for. I would like a list of all partitions
    with each partition having k or less elements, not just one instance.



    wrote:
    > Something like this, or am I missing something?
    >
    > def partition(List, n, m, k):
    > if n!=m*k:
    > raise "sorry, too many or too few elts"
    > D = {}
    > for x in List:
    > D[x] = 1
    > if len(D)!=n:
    > raise "sorry (2) you lied about the number"
    > List2 = D.keys()
    > result = []
    > for i in range(m):
    > result.append( List2[i*k: i*k+k] )
    > return result
    > ?
    >
    > If this was a take home exam problem,
    > you should be ashamed of yourself!
    > -- Aaron Watters
    >
    > ===
    >
    > It's easy. All you have to do is hit
    > the right keys at the right time and
    > the organ plays itself. -- J.S. Bach
    , May 1, 2006
    #4
  5. On Mon, May 01, 2006 at 03:42:53PM -0700, wrote:
    > Not quite what I'm looking for. I would like a list of all partitions
    > with each partition having k or less elements, not just one instance.


    def partition(S, k):
    parts = []
    ct = 0
    cp = []
    for elem in S:
    if ct > k:
    parts.append(cp)
    cp = []
    ct = 0
    cp.append(elem)
    ct += 1
    parts.append(cp)
    return parts

    > > If this was a take home exam problem,
    > > you should be ashamed of yourself!
    > > -- Aaron Watters


    - Michael

    --
    mouse, n: a device for pointing at the xterm in which you want to type.
    -- Fortune
    Visit me on the Web: http://www.elehack.net
    Michael Ekstrand, May 2, 2006
    #5
  6. Guest

    For the list [1,2,3,4], I'm looking for the following for k = 2:

    [[1,2], [3,4]]
    [[1,3], [2,4]]
    [[1,4], [2,3]]

    for k = 3:

    [[1,2,3], [4]]
    [[1,2,4], [3]]
    [[1,3,4], [2]]
    [[2,3,4], [1]]
    , May 2, 2006
    #6
  7. James Waldby Guest

    "" wrote:
    > Can someone tell me of a good algorithm to partition a set of n
    > elements into m non-empty, disjoint subsets, where each subset has
    > size k?


    and later wrote in a separate post
    > Also, if I do not care about the number of subsets, what is a good
    > algorithm to partition a set of n elements into non-empty, disjoint
    > subsets of size k?


    and then execrably wrote [ie, top-posted]:
    > Not quite what I'm looking for. I would like a list of all partitions
    > with each partition having k or less elements, not just one instance.


    when Aaron Watters wrote:
    > Something like this, or am I missing something?
    >
    > def partition(List, n, m, k):

    [snip Watters' program to partition set of n elements
    into m non-empty disjoint subsets, each of size k]

    So if n=3 and k=2 and set S={a,b,c}, you would want a list
    like the following?
    1. {a},{b},{c}
    2. {a,b},{c}
    3. {a,c},{b}
    4. {b,c},{a}

    So it appears you need to do 2 things -

    (1) Produce a list of additive partitions of n with numbers
    not exceeding k. In the S={a,b,c} example, the list contains
    (1,1,1) and (2,1). I think you can make the list with work
    O(T(n,k)). For values of T(n,k) (ie, "number of partitions of
    n in which the greatest part is k, 1<=k<=n") see
    http://www.research.att.com/~njas/sequences/A008284 .

    (2) For each list from (1), fill in elements from S into each
    of the subsets, in canonical order. (Eg, after filling in (1,1,1)
    to make {a},{b},{c}, don't produce {a},{c},{b} etc.) See a
    combinatorial algorithms book, eg Reingold, for this part.
    http://www.amazon.com/gp/product/013152447X/104-5966364-8396722?n=283155

    -jiw
    James Waldby, May 2, 2006
    #7
  8. wrote:

    > For the list [1,2,3,4], I'm looking for the following for k = 2:
    >
    > [[1,2], [3,4]]
    > [[1,3], [2,4]]
    > [[1,4], [2,3]]


    That's not what you asked for the first time. You said you wanted "m
    non-empty, disjoint subsets", but the subsets above are clearly not all
    disjoint; only those on the same line are. It sounds like what you really
    want is the "powerset of non-empty, disjoint partitions of size k".
    Edward Elliott, May 2, 2006
    #8
  9. Boris Borcic Guest

    wrote:
    > For the list [1,2,3,4], I'm looking for the following for k = 2:
    >
    > [[1,2], [3,4]]
    > [[1,3], [2,4]]
    > [[1,4], [2,3]]
    >
    > for k = 3:
    >
    > [[1,2,3], [4]]
    > [[1,2,4], [3]]
    > [[1,3,4], [2]]
    > [[2,3,4], [1]]
    >


    def pickk(k,N,m=0) :
    if k==1 :
    return ((n,) for n in range(m,N))
    else :
    return ((n,)+more for more in pickk(k-1,N,m+1)
    for n in range(m,more[0]))

    def partitionN(k,N) :
    subsets = [frozenset(S) for S in pickk(k,N)]
    def exhaust(rest,bound=0) :
    if len(rest) < k :
    if rest :
    yield [sorted(rest)]
    else :
    yield []
    for newbound in range(bound,len(subsets)) :
    S = subsets[newbound]
    if rest >= S :
    sS = [sorted(S)]
    for restpart in exhaust(rest-S,newbound+1) :
    yield sS+restpart
    return exhaust(set(range(N)))

    partition = lambda k,S : [[[S[j] for j in S0] for S0 in P0]
    for P0 in partitionN(k,len(S))]

    >>> partition(2,[1,2,3,4])

    [[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[2, 3], [1, 4]]]
    >>> partition(3,[1,2,3,4])

    [[[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 3, 4], [2]], [[2, 3, 4], [1]]]


    CAVEAT : insufficiently tested, not proved correct, uncommented, provided as is
    Boris Borcic, May 2, 2006
    #9
  10. Boris Borcic Guest

    I wrote:
    >
    > def pickk(k,N,m=0) :
    > if k==1 :
    > return ((n,) for n in range(m,N))
    > else :
    > return ((n,)+more for more in pickk(k-1,N,m+1)
    > for n in range(m,more[0]))
    >
    > def partitionN(k,N) :
    > subsets = [frozenset(S) for S in pickk(k,N)]


    while it doesn't otherwise change results, changing this line to

    subsets = [frozenset(S) for S in sorted(pickk(k,N))]

    provides everything nicely ordered (e.g. lexicographically)

    > def exhaust(rest,bound=0) :
    > if len(rest) < k :
    > if rest :
    > yield [sorted(rest)]
    > else :
    > yield []
    > for newbound in range(bound,len(subsets)) :
    > S = subsets[newbound]
    > if rest >= S :
    > sS = [sorted(S)]
    > for restpart in exhaust(rest-S,newbound+1) :
    > yield sS+restpart
    > return exhaust(set(range(N)))
    >
    > partition = lambda k,S : [[[S[j] for j in S0] for S0 in P0]
    > for P0 in partitionN(k,len(S))]
    >
    > >>> partition(2,[1,2,3,4])

    > [[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[2, 3], [1, 4]]]
    > >>> partition(3,[1,2,3,4])

    > [[[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 3, 4], [2]], [[2, 3, 4], [1]]]
    >
    >
    > CAVEAT : insufficiently tested, not proved correct, uncommented,
    > provided as is
    Boris Borcic, May 2, 2006
    #10
    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. BobRoyAce

    Application "partitioning"

    BobRoyAce, Jan 24, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    337
    Suhaib Khan
    Jan 24, 2005
  2. Darrel

    Folder 'partitioning'

    Darrel, Apr 13, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    357
    Lau Lei Cheong
    Apr 13, 2006
  3. GianGuz
    Replies:
    4
    Views:
    368
    Jonathan Mcdougall
    Dec 20, 2004
  4. Max Muermann

    [GOLF]: partitioning an array

    Max Muermann, Dec 7, 2006, in forum: Ruby
    Replies:
    6
    Views:
    98
    Trans
    Dec 7, 2006
  5. Peter Szinek

    Partitioning with Set.divide

    Peter Szinek, Apr 29, 2007, in forum: Ruby
    Replies:
    6
    Views:
    114
    Robert Klemme
    Apr 30, 2007
Loading...

Share This Page