Ask Your Question
0

dividing range by combinations

asked 2020-04-02 19:32:00 -0600

parkjr gravatar image

The following is an example:

temp = range(5)
L = [2,1,2]

Then we know that

$_5\rm C_2 \times _3\rm C_1 \times _2\rm C_2 = 30$

We can get every combinations as following:

result = []
for A in Combinations(temp, L[0]):
    temp = list(set(temp) - set(A))
    for B in Combinations(temp, L[1]):
        temp = list(set(temp) - set(B))
        result += [[A,B, temp]]
        temp = list(set(range(5))- set(A))
    temp = range(5)

Then result is

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

The problem is that 'How can I get the general case?'

temp = range(k)

L = [$e_1$, $e_2$, $\cdots$, $e_n$ ], where $\sum_{i=1} ^n e_i = k$

I don't know the size of list L.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2020-04-13 16:38:39 -0600

dan_fulea gravatar image

Here is a possible recursive (rather lazy) implementation without using specialized iter tools.

def mySplitIntoPieces(S, L):
    """S is a list of "elements", 
    L is a list of positive integers with sum(L) = len(S),
    we want to return the list of all tuples
    [ S0, S1, S2, ... ]
    where S0, S1, S2, ... are a partition of S and 
    len(S0) = L[0],
    len(S1) = L[1],
    len(S2) = L[2],
    and so on.
    """

    if len(S) != sum(L):
        return

    if len(L) == 0:
        return [ S ]    # the partition of S in one piece

    return [ [ S0, ] + furtherPieces
             for S0 in Combinations( S, L[0] )
             for furtherPieces in mySplitIntoPieces( list(set(S).difference(S0)), L[1:] ) ]

Let us test the functionality:

sage: for pieces in mySplitIntoPieces( [0..4], [2,1,2] ): 
....:     print(pieces)                                                                                                                                                                               
[[0, 1], [2], [3, 4]]
[[0, 1], [3], [2, 4]]
[[0, 1], [4], [2, 3]]
[[0, 2], [1], [3, 4]]
[[0, 2], [3], [1, 4]]
[[0, 2], [4], [1, 3]]
[[0, 3], [1], [2, 4]]
[[0, 3], [2], [1, 4]]
[[0, 3], [4], [1, 2]]
[[0, 4], [1], [2, 3]]
[[0, 4], [2], [1, 3]]
[[0, 4], [3], [1, 2]]
[[1, 2], [0], [3, 4]]
[[1, 2], [3], [0, 4]]
[[1, 2], [4], [0, 3]]
[[1, 3], [0], [2, 4]]
[[1, 3], [2], [0, 4]]
[[1, 3], [4], [0, 2]]
[[1, 4], [0], [2, 3]]
[[1, 4], [2], [0, 3]]
[[1, 4], [3], [0, 2]]
[[2, 3], [0], [1, 4]]
[[2, 3], [1], [0, 4]]
[[2, 3], [4], [0, 1]]
[[2, 4], [0], [1, 3]]
[[2, 4], [1], [0, 3]]
[[2, 4], [3], [0, 1]]
[[3, 4], [0], [1, 2]]
[[3, 4], [1], [0, 2]]
[[3, 4], [2], [0, 1]]
sage:
edit flag offensive delete link more

Comments

You showed me the perfect answer!!! Thanks:)

parkjr gravatar imageparkjr ( 2020-04-22 01:05:03 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-04-02 19:32:00 -0600

Seen: 20 times

Last updated: Apr 13