Skip to content
Advertisement

Find all 3^4 permutation using lists

Let’s say I have 4 distinguishable balls, and I want to distribute them into 3 cells (that’s 3^4 different ways of doing that) – how would you suggest me to demonstrate all those 81 different distributions using Python?

I want my program to return a list that contains 81 lists, each contain 3 lists representing the 3 cells, where in each sub-list there are numbers 1-4.

hope you understood what i meant.. it’s a bit complicated interpretation.

I’ll try to give an example of how my list should look like:

[
  [ [1,2] , [3,4] , []  ]  # cell #1 contains the balls 1,2 and cell #2 contains the balls 3,4 and cell #3 is empty
  [ [1,2] , [3] , [4]  ]  # cell #1 contains the balls 1,2 and cell #2 contains ball 3 and cell #3 contains ball 4
  [ [1,2] , [] , [3,4]  ]  # cell #1 contains the balls 1,2, cell #2 is empty and cell #3 contains the balls 3,4
...
]

Advertisement

Answer

There is simple and bruteforce, but working, example:

import itertools
import pprint

balls = set('1234')
splits = []
for i in range(0,len(balls)+1): # python ranges are upper-bound exclusive
    bucket_1_possibilities = (set(x) for x in itertools.combinations(balls,i))
    for bucket1 in bucket_1_possibilities:
        for j in range(0,len(balls)-i+1): # in the second cell there may be up to len(balls)-i balls 
            bucket_2_possibilities = list(set(x) for x in itertools.combinations(balls-bucket1,j))
            for bucket_2 in bucket_2_possibilities:
                splits.append([list(bucket1), list(bucket_2),list(balls-bucket1-bucket_2)])
pprint.pprint(splits)
print(len(splits))

Itertools.combinations (https://docs.python.org/3/library/itertools.html#itertools.combinations) allow you to get possible contents of first cell. From remaining balls you get possible contents of second cells, and so on.

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement