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? 9 2633
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?
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
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.com 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
On Mon, May 01, 2006 at 03:42:53PM -0700, hy****@hotmail.com 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
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]]
"hy****@hotmail.com" 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/013...96722?n=283155
-jiw hy****@hotmail.com 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". hy****@hotmail.com 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
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Jeff Boes |
last post by:
I'm sure this is a concept that's been explored here. I have a table
(fairly simple, just two columns, one of which is a 32-digit checksum)
with several million rows (currently, about 7 million)....
|
by: Jane |
last post by:
In Oracle we can partition a table as follows. What is the equivalent in DB2?
CREATE TABLE sales_list
(salesman_id NUMBER(5),
salesman_name VARCHAR2(30),
sales_state VARCHAR2(20),...
|
by: shsandeep |
last post by:
DB2 V8.2 (not Viper yet and no range partitioning!!)
I have created a table T1 (col1, col2) with col1 as the primary key.
When I try to create a partitioning key on col2, it gives me error that it...
|
by: mitek |
last post by:
Hi, All
I have strange situation with table design for DB2 9.1 on Windows
I have 3 tables with same structure :
1 table - is MDC
2 table - is partitioned MDC table
3 table - is compressed...
|
by: harrylarenson |
last post by:
Hi, Happy New Year.
I am trying to insert a query to a partitioned view but the error is :
Server: Msg 4436, Level 16, State 12, Line 1
UNION ALL view 'T' is not updatable because a...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |