How to check for adjacency in list, then fix adjacency in python

Question

I have this list:

row = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

I need to then shuffle or randomize the list:

shuffle(row)

And then I need to go through and find any adjacent 1's and move them so that they are separated by at least one 0. For example I need the result to look like this:

row = [0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0]

I am not sure of what the most efficient way to go about searching for adjacent 1's and then moving them so that they aren't adjacent is... I will also being doing this repeatedly to come up with multiple combinations of this row.

Originally when the list was shorter I did it this way:

row = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
rowlist = set(list(permutations(row)))
rowschemes = [(0, 0) + x for x in rowlist if '1, 1' not in str(x)]

But now that my row is 20 elements long this takes forever to come up with all the possible permutations.

Is there an efficient way to go about this?

Answer 1

I had a moderately clever partition-based approach in mind, but since you said there are always 20 numbers and 6 1s, and 6 is a pretty small number, you can construct all the possible locations (38760) and toss the ones which are invalid. Then you can uniformly draw from those, and build the resulting row:

import random
from itertools import combinations

def is_valid(locs):
    return all(y-x >= 2 for x,y in zip(locs, locs[1:]))

def fill_from(size, locs):
    locs = set(locs)
    return [int(i in locs) for i in range(size)]

and then

>>> size = 20
>>> num_on = 6
>>> on_locs = list(filter(is_valid, combinations(range(size), num_on)))
>>> len(on_locs)
5005
>>> fill_from(size, random.choice(on_locs))
[0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1]
>>> fill_from(size, random.choice(on_locs))
[0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
>>> fill_from(size, random.choice(on_locs))
[1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]