CODEWITHSUNDEEP
pythonpython-3.xalgorithmdata-structures
Dawn17
Dawn17

Reputation: 8297

How can I generate a list of lists of permutations

Let's say I have a list of pattern [2, 1] and given a length = 5.

The pattern means that there are sets of 2 and 1 'ones' in the list in that order in a list of length = 5.

Also the space or 0 between successive groups has to be at least one.

What I've tried is:

for curr_col in pattern_list:

    curr_pattern = curr_col

    example_combo = [0] * dim0
    idx, group_strt_idxs = 0, []
    for num in curr_pattern :
        group_strt_idxs.append(idx)
        for i in range(num ):
            example_combo[idx] = 1
            idx += 1
        if idx < dim0 and dim0 > 1:
            example_combo[idx] = 0
            idx += 1
    print('ex', example_combo)

Please help!

Upvotes: 1

Views: 70

Answers (2)

Ajax1234
Ajax1234

Reputation: 71471

Since the length of the groups of 1's are already given, the recursion can determine the placing for each:

def generate_groups(d, fill=1):
  return [[fill]*i for i in d]

def all_groups(_d, _len):
  def groupings(d, current = []):
    if sum(not i for i in current) == d and sum(i == '*' for i in current) == len(_d):
      yield current
    else:
      if sum(not i for i in current) < d:
         yield from groupings(d, current+[0])
      if not current or not current[-1]:
         yield from groupings(d, current+['*'])
  return [(lambda x, y:[c for h in y for c in ([h] if not h else next(x))])(iter(generate_groups(_d)), i) 
    for i in groupings(_len-sum(_d))]

print(all_groups([2, 1], 5))
print(all_groups([2, 3, 2], 11))

Output:

[[0, 1, 1, 0, 1], [1, 1, 0, 0, 1], [1, 1, 0, 1, 0]]
[[0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1], [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1], [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1], [0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0], [1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0], [1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0]]

Upvotes: 0

Thierry Lathuille
Thierry Lathuille

Reputation: 24289

The problem is to put the zeros into len(constraints_list) + 1 buckets. The first and last one can contain 0 or more zeros, the intermediate ones must contain at least one.

We generate the possible repartitions in the repartitions function. It is then easy to build the corresponding list:

from itertools import zip_longest 


def repartitions(number, buckets, start=None):
    if start is None:
        start = []
        mini = 0 # first sequence of zeros can be empty
    else:
        mini = 1 # others contain at least one zero

    if buckets == 1:
        # last bucket, we put all remaining zeros here
        start = start + [number]
        yield start
    else:
        for i in range(mini, number-buckets+3):
            # we have to keep at least 1 zero for each other bucket
            # except the last one.
            current = start + [i]
            yield from repartitions(number-i, buckets-1, current)


def permutations_with_constraints(constraints_list, length):
    number_of_zeros = length - sum(constraints_list)
    buckets = len(constraints_list) + 1
    for rep in repartitions(number_of_zeros, buckets):
        out = sum(([0]*zeros + [1]*ones 
                   for zeros, ones in zip_longest(rep, constraints_list, fillvalue=0)), [])
        yield out

Some examples:

print(list(permutations_with_constraints([1, 2], 5)))
# [[1, 0, 1, 1, 0], [1, 0, 0, 1, 1], [0, 1, 0, 1, 1]]

print(list(permutations_with_constraints([2, 3, 2], 11)))
# [[1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0], 
# [1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0],
# [1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1],
# [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0],
# [1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1],
# [1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1],
# [0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0],
# [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1],
# [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1],
# [0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1]]

Some explanations about the sum, as you asked in comments:

We have a rep list, and a one item shorter constraints list. We zip them with zip_longest and a fillvalue=0, which gives us [(rep[0], constraints[0]), (rep[1], constraints[1]), ... (rep[-1], 0)]. (It's really a generator, not a list, but this doesn't change anything to the explanation). The last 0 fills the missing value in constraints.

We then build a list from each tuple. For example, (2, 3) will give us [0, 0, 1, 1, 1]. sum then adds these lists, using [] as a start value.

Upvotes: 1

Related Questions