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?
elements into m non-empty, disjoint subsets, where each subset has size
k?
-
-
Re: set partitioning
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?
-
Re: set partitioning
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
Comment
-
Re: set partitioning
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.
aaronwmail-use...@yahoo.co m wrote:[color=blue]
> 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[/color]
Comment
-
Re: set partitioning
On Mon, May 01, 2006 at 03:42:53PM -0700, hymort@hotmail. com wrote:[color=blue]
> 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.[/color]
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
[color=blue][color=green]
> > If this was a take home exam problem,
> > you should be ashamed of yourself!
> > -- Aaron Watters[/color][/color]
- 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
Comment
-
Re: set partitioning
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]]
Comment
-
Re: set partitioning
"hymort@hotmail .com" wrote:[color=blue]
> 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?[/color]
and later wrote in a separate post[color=blue]
> 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?[/color]
and then execrably wrote [ie, top-posted]:[color=blue]
> 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.[/color]
when Aaron Watters wrote:[color=blue]
> Something like this, or am I missing something?
>
> def partition(List, n, m, k):[/color]
[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/013...96722?n=283155
-jiw
Comment
-
Re: set partitioning
hymort@hotmail. com wrote:
[color=blue]
> 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]][/color]
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".
Comment
-
Re: set partitioning
hymort@hotmail. com wrote:[color=blue]
> 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]]
>[/color]
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,bo und=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(ran ge(N)))
partition = lambda k,S : [[[S[j] for j in S0] for S0 in P0]
for P0 in partitionN(k,le n(S))]
[color=blue][color=green][color=darkred]
>>> partition(2,[1,2,3,4])[/color][/color][/color]
[[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[2, 3], [1, 4]]][color=blue][color=green][color=darkred]
>>> partition(3,[1,2,3,4])[/color][/color][/color]
[[[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
Comment
-
Re: set partitioning
I wrote:[color=blue]
>
> 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)][/color]
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. lexicographical ly)
[color=blue]
> def exhaust(rest,bo und=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(ran ge(N)))
>
> partition = lambda k,S : [[[S[j] for j in S0] for S0 in P0]
> for P0 in partitionN(k,le n(S))]
>[color=green][color=darkred]
> >>> partition(2,[1,2,3,4])[/color][/color]
> [[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[2, 3], [1, 4]]][color=green][color=darkred]
> >>> partition(3,[1,2,3,4])[/color][/color]
> [[[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[/color]
Comment
Comment