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

Why not go directly for what you want? Something like:

row = ["0","0","0","0","0","0","0","0","0","01","01","01","01","01","01"]
random.shuffle(row)
print (map(int, list("".join(row)[1:])))

Answer 2

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]

Answer 3

Since the number of 1's is fixed in a row and you don't want any 1's to be adjacent, let m be the number of 1's and let k be the number of 0's of the row. Then you want to place the m 1's in (k+1) locations randomly so that there is at most one 1 in each location. This amounts to choosing a random subset of size ((k+1) choose m) from the set (1,2,...,k+1). This is easy to do. Given the random choice of subset, you can construct your random arrangement of 0's and 1's so that no two 1's are adjacent. The random choice algorithm takes O(m) time.

Answer 4

Place the 6 1's and 5 of the 0's in a list giving

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

Then insert the remaining 0's one by one at random positions in the (growing) list.

for i in range(11,19):
    row.insert(random.randint(0,i), 0)