Geek Answers Handbook

Set restricted section in Python

It was difficult for me to deal with the problem of the group partition. Someone shed some light for me, please?

Let me simplify my question. I want to divide ten numbers (i.e. 0, 1, ..., 9 ) into three groups, with ( 4, 3, 3 ) the number of each group. Conditions:

  • The intra-group sequence does not matter. For example, [( 0, 1, 2, 3 ), ( 4, 5, 6 ), ( 7, 8, 9 )] will be considered the same as [( 3, 0, 1, 2 ), ( 5, 6, 4 ), ( 7, 8, 9 )].

  • I want to keep ( 1, 2, 3 ) always in the same group, as well as for ( 7, 8 ).

How can I list all possible grouping scenarios that meet the above criteria? Many thanks!

I am using Python 2.7.

+5
source share
3 answers

So, you want to split 3 blocks of size 4.3.3, with (1,2,3) in one block and (7,8) in one block.

This means that 1,2,3 and 7,8 cannot be in one block.

Let me first forget the keyboard and analyze the problem

IMHO, you have to separate 3 cases:

  • 1,2,3 are in a block of size 4 (case 1)
  • 7.8 are in a block of size 4 (case 2)
  • neither 1,2,3, nor 7,8, nor in a block of size 4 (case 3)

Case 1

  • one element of (0,4,5,6,9) goes into a block containing (1, 2, 3)
  • one element of (0,4,5,6,9) goes to the block containing (7,8)

total: 5 * 4 = 20 different sections

Case 2

  • two elements from (0,4,5,6,9) go to the block containing (7,8)

total: 5 * 4/2 = 10 different sections (/ 2, because you want combinations, not permutations)

Case 3

  • one element from (0,4,5,6,9) goes to the block containing (7,8)

total: 5 different sections

So, you know that you should have 35 different sections

Python Code:

 def gen(): B1 = [1,2,3] B2 = [7,8] C = [x for x in range(10) if x not in B1 + B2 ] def gen1(): for x in C: c = C[:] b1 = B1[:] b1.append(x) c.remove(x) for y in c: c1 = c[:] b2 = B2[:] b2.append(y) c1.remove(y) yield(b1, b2, c1) def gen2(): for i in range(len(C)-1): for j in range(i+1, len(C)): b2 = B2 + [C[i], C[j]] c = [C[k] for k in range(len(C)) if k not in (i,j)] yield (B1, b2, c) def gen3(): for x in C: b2 = B2[:] c = C[:] c.remove(x) b2.append(x) yield(B1, b2, c) for g in (gen1, gen2, gen3): for t in g(): yield t

And you get it right:

 >>> list(gen()) [([1, 2, 3, 0], [7, 8, 4], [5, 6, 9]), ([1, 2, 3, 0], [7, 8, 5], [4, 6, 9]), ([1, 2, 3, 0], [7, 8, 6], [4, 5, 9]), ([1, 2, 3, 0], [7, 8, 9], [4, 5, 6]), ([1, 2, 3, 4], [7, 8, 0], [5, 6, 9]), ([1, 2, 3, 4], [7, 8, 5], [0, 6, 9]), ([1, 2, 3, 4], [7, 8, 6], [0, 5, 9]), ([1, 2, 3, 4], [7, 8, 9], [0, 5, 6]), ([1, 2, 3, 5], [7, 8, 0], [4, 6, 9]), ([1, 2, 3, 5], [7, 8, 4], [0, 6, 9]), ([1, 2, 3, 5], [7, 8, 6], [0, 4, 9]), ([1, 2, 3, 5], [7, 8, 9], [0, 4, 6]), ([1, 2, 3, 6], [7, 8, 0], [4, 5, 9]), ([1, 2, 3, 6], [7, 8, 4], [0, 5, 9]), ([1, 2, 3, 6], [7, 8, 5], [0, 4, 9]), ([1, 2, 3, 6], [7, 8, 9], [0, 4, 5]), ([1, 2, 3, 9], [7, 8, 0], [4, 5, 6]), ([1, 2, 3, 9], [7, 8, 4], [0, 5, 6]), ([1, 2, 3, 9], [7, 8, 5], [0, 4, 6]), ([1, 2, 3, 9], [7, 8, 6], [0, 4, 5]), ([1, 2, 3], [7, 8, 0, 4], [5, 6, 9]), ([1, 2, 3], [7, 8, 0, 5], [4, 6, 9]), ([1, 2, 3], [7, 8, 0, 6], [4, 5, 9]), ([1, 2, 3], [7, 8, 0, 9], [4, 5, 6]), ([1, 2, 3], [7, 8, 4, 5], [0, 6, 9]), ([1, 2, 3], [7, 8, 4, 6], [0, 5, 9]), ([1, 2, 3], [7, 8, 4, 9], [0, 5, 6]), ([1, 2, 3], [7, 8, 5, 6], [0, 4, 9]), ([1, 2, 3], [7, 8, 5, 9], [0, 4, 6]), ([1, 2, 3], [7, 8, 6, 9], [0, 4, 5]), ([1, 2, 3], [7, 8, 0], [4, 5, 6, 9]), ([1, 2, 3], [7, 8, 4], [0, 5, 6, 9]), ([1, 2, 3], [7, 8, 5], [0, 4, 6, 9]), ([1, 2, 3], [7, 8, 6], [0, 4, 5, 9]), ([1, 2, 3], [7, 8, 9], [0, 4, 5, 6])]

(manual formatting for easier reading ...)

+3
source 
 For comb in combination k=3 in (0,4,5,6,9), remaining a, b: (g1+a, g2+b, comb) (g1+b, g2+a, comb) (g2+a+b, g3, g1) For comb in combination k=4 in (0,4,5,6,9), remaining a: (comb, g1, g2+a) 
 from itertools import combinations, permutations def partition_generator(): wildcards = (0,4,5,6,9) g1, g2 = (1,2,3), (7,8) for comb in combinations(wildcards, 3): unused = remaining(wildcards, comb) for r in permutations(unused): yield part(g1, g2, comb, r) yield part(g2, g1, comb, unused) for comb in combinations(wildcards, 4): yield part(comb, g1, g2, remaining(wildcards, comb)) def remaining(a, b): return [ x for x in a if x not in b ] def part(x,y,z,remaining): q = list(remaining) while len(x) < 4: x = x + (q.pop(0),) if len(y) < 3: y = y + (q.pop(0),) if len(z) < 3: z = z + (q.pop(0),) return (x,y,z) 

 >>> for partition in partition_generator(): ... print(partition) ... ((1, 2, 3, 6), (7, 8, 9), (0, 4, 5)) ((1, 2, 3, 9), (7, 8, 6), (0, 4, 5)) ((7, 8, 6, 9), (1, 2, 3), (0, 4, 5)) ((1, 2, 3, 5), (7, 8, 9), (0, 4, 6)) ((1, 2, 3, 9), (7, 8, 5), (0, 4, 6)) ((7, 8, 5, 9), (1, 2, 3), (0, 4, 6)) ((1, 2, 3, 5), (7, 8, 6), (0, 4, 9)) ((1, 2, 3, 6), (7, 8, 5), (0, 4, 9)) ((7, 8, 5, 6), (1, 2, 3), (0, 4, 9)) ((1, 2, 3, 4), (7, 8, 9), (0, 5, 6)) ((1, 2, 3, 9), (7, 8, 4), (0, 5, 6)) ((7, 8, 4, 9), (1, 2, 3), (0, 5, 6)) ((1, 2, 3, 4), (7, 8, 6), (0, 5, 9)) ((1, 2, 3, 6), (7, 8, 4), (0, 5, 9)) ((7, 8, 4, 6), (1, 2, 3), (0, 5, 9)) ((1, 2, 3, 4), (7, 8, 5), (0, 6, 9)) ((1, 2, 3, 5), (7, 8, 4), (0, 6, 9)) ((7, 8, 4, 5), (1, 2, 3), (0, 6, 9)) ((1, 2, 3, 0), (7, 8, 9), (4, 5, 6)) ((1, 2, 3, 9), (7, 8, 0), (4, 5, 6)) ((7, 8, 0, 9), (1, 2, 3), (4, 5, 6)) ((1, 2, 3, 0), (7, 8, 6), (4, 5, 9)) ((1, 2, 3, 6), (7, 8, 0), (4, 5, 9)) ((7, 8, 0, 6), (1, 2, 3), (4, 5, 9)) ((1, 2, 3, 0), (7, 8, 5), (4, 6, 9)) ((1, 2, 3, 5), (7, 8, 0), (4, 6, 9)) ((7, 8, 0, 5), (1, 2, 3), (4, 6, 9)) ((1, 2, 3, 0), (7, 8, 4), (5, 6, 9)) ((1, 2, 3, 4), (7, 8, 0), (5, 6, 9)) ((7, 8, 0, 4), (1, 2, 3), (5, 6, 9)) ((0, 4, 5, 6), (1, 2, 3), (7, 8, 9)) ((0, 4, 5, 9), (1, 2, 3), (7, 8, 6)) ((0, 4, 6, 9), (1, 2, 3), (7, 8, 5)) ((0, 5, 6, 9), (1, 2, 3), (7, 8, 4)) ((4, 5, 6, 9), (1, 2, 3), (7, 8, 0))
+2
source

If I understand your problem correctly, this should do what you asked for:

 from copy import deepcopy # slice into appropriate chunks def slice_lst(size_tup, lst): for index, length in enumerate(size_tup): running_total = sum(size_tup[:index]) yield lst[running_total:running_total+length] # perform integer partition def integer_partition(num): return {(x,) + y for x in range(1, num) for y in integer_partition(num-x)} | {(num,)} # create all partitions given the starting list def subsets(lst): for partition in integer_partition(len(lst)): yield list(slice_lst(partition, deepcopy(lst))) # check that 1,2 and 3 are always contained within the same subset def triplet_case(lst): bool_arr = [1 in lst, 2 in lst, 3 in lst] return all(bool_arr) or not any (bool_arr) # check that 7 and 8 are always contained within the same subset def duplet_case(lst): bool_arr = [7 in lst, 8 in lst] return all(bool_arr) or not any(bool_arr) for subset in subsets([1,2,3,4,5,6,7,8,9]): if all([triplet_case(s) for s in subset]) and all([duplet_case(s) for s in subset]): print subset

Feel free to ask additional questions if you have any!

0
source

More articles:


All Articles