Python: Efficient way to create equal length sublists from given list with repetition allowed and or-CodePudding

So I have a list of 151 items and need sublists of length 6 from the given list, the conditions are that repetition of items is allowed and order does not matter. Shorter example for explanation.

list_given = [1, 2]

possible_sublists = [
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2]
]

Not allowed sublists would be any permutation of the above solutions, like [1, 1, 1, 1, 1, 2] is the same as [1, 1, 1, 1, 2, 1].

I tried a recursive approach at first but the stack gets very deep very quickly.
I have implemented an iterative solution but the for loops have to complete 151^6 = 1,18,53,91,15,88,401 iterations while the required is 156 C 6(n r-1 C r) = 18,16,16,99,556 which makes 1,18,35,74,98,88,845 wasted iterations and adds more to the time complexity. How can I make it more efficient to avoid these large numbers of computations? And on top, I also have to make sure there are no repeated teams as mentioned above so O(n) time complexity adds to the current complexity where n changes as new sublists are added to the global_set.
Current Algorithm

from collections import Counter
def make_teams(poke):
    global_set = []
    for i in poke:
        for j in poke:
            for k in poke:
                for l in poke:
                    for m in poke:
                        for n in poke:
                            temp = Counter([i, j, k, l, m, n])
                            if temp not in global_set:
                                global_set.append(temp)
    return global_set

CodePudding user response：

As you've pointed out there are 18.16bio sublists (156!/6!150!)

Good luck!

N=151
global_list = []
for i in range(N):                                                                                                                                                     
    for j in range(i,N):                                                                                                                                                   
        for k in range(j,N):                                                                                                                                                   
            for l in range(k,N):                                                                                                                                                   
                for m in range(l,N):                                                                                                                                                   
                    for n in range(m,N):                                                                                                                                                   
                        global_list.append([i,j,k,l,m,n])                                                                                                                       

print(global_list)

CodePudding user response：

Use itertools.combinations_with_replacement:

list_given = [1, 2]
for combination in itertools.combinations_with_replacement(list_given, 6):
    print(combination)

->
(1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 2)
(1, 1, 1, 1, 2, 2)
(1, 1, 1, 2, 2, 2)
(1, 1, 2, 2, 2, 2)
(1, 2, 2, 2, 2, 2)
(2, 2, 2, 2, 2, 2)

But note that when list_given has 151 elements, you're going to get a lot of combinations! That's why example iterates over the combinations instead of putting them all in a list: the resulting list would be huge for 151 elements.