How do I get all possible orderings of 9 zeros and 9 ones using Python?

Question

I want to end up with a list with 48 620 nested lists, containing 9 zeros and 9 ones in different orders.

from itertools import permutations

print(list(permutations('000000000111111111', r=18)))

I assume the code above works, but every 0 and 1 is treated like an individual symbol, so for every ordering I get tons of repeats:

('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
...

So, basically, how do I shuffle a list in every possible way, excluding repeats?

I tried to use every method from itertools, but I didn't find one that specifically does what i need.

Answer 1

Where 18 is the length of the list you want to generate and 9 is how many of them should be 0:

for x in itertools.combinations(range(18),9):
    print(tuple(('0' if i in x else '1' for i in range(18))))

The idea here is to use combinations to choose the set of locations that will be 0 for each of (in your example's case) 48620 lists.

Answer 2

Your question is slightly ambiguous. Do you want the output list to have strings 9 characters long or 18? I'm assuming 18, because you said "containing 9 zeros and 9 ones"

The following code works, but I must warn you, it's terribly slow. You might want to consider just storing the output in a text file or something so you don't have to compute it every time.

import itertools

def merge_tuples(items: list[tuple]) -> list[str]:
    new_items = set()
    for tup in items:
        new_items.add("".join(tup))
    return list(new_items)

inp_string = ('0'*9) + ('1'*9)
output = merge_tuples(list(itertools.combinations(inp_string, 18)))

Answer 3

A simple one, and faster than the accepted solution (~100 ms vs ~170 ms):

from itertools import product

for x in product('01', repeat=18):
    if x.count('0') == 9:
        print(x)

Attempt This Online!

Answer 4

More solutions (Kelly2 and Kelly3) and a benchmark:

  8.7 ± 0.1 ms  Kelly2
  9.1 ± 0.1 ms  Kelly3
 44.1 ± 0.4 ms  CtrlZ
101.4 ± 1.2 ms  Kelly
179.5 ± 0.7 ms  Scott_Hunter

Python: 3.11.4 (main, Sep  9 2023, 15:09:21) [GCC 13.2.1 20230801]

The new solutions prepare tuples of length 9 and then just combine them appropriately, which is relatively fast. (No generation+outfiltering of invalid ones like Kelly and CtrlZ, and no costly creation of each tuple like Scott_Hunter).

Code:

from itertools import product, combinations
from timeit import timeit
from statistics import mean, stdev
import sys

def Kelly():
    return [
        x
        for x in product('01', repeat=18)
        if x.count('0') == 9
    ]

def Kelly2():
    xss = [[] for _ in range(10)]
    for x in product('01', repeat=9):
        xss[x.count('1')].append(x)
    return [
        x + y
        for xs, ys in zip(xss, xss[::-1])
        for x in xs
        for y in ys
    ]

def Kelly3():
    xs = [*product('01', repeat=9)]
    xss = [[] for _ in range(10)]
    for x in xs:
        xss[x.count('0')].append(x)
    return [
        x + y
        for x in xs
        for y in xss[x.count('1')]
    ]

def Scott_Hunter():
    return [
        tuple(('0' if i in x else '1' for i in range(18)))
        for x in combinations(range(18),9)
    ]

def CtrlZ():
    hi = int("111111111000000000", 2)
    lo = int("111111111", 2)
    return [
        tuple(f"{x:018b}")
        for x in range(lo, hi + 1)
        if x.bit_count() == 9
    ]

funcs = Kelly, Kelly2, Kelly3, Scott_Hunter, CtrlZ

print(Kelly() == sorted(Kelly2()) == Kelly3() == Scott_Hunter() == CtrlZ())

times = {f: [] for f in funcs}
def stats(f):
    ts = [t * 1e3 for t in sorted(times[f])[:5]]
    return f'{mean(ts):5.1f} ± {stdev(ts):3.1f} ms '
for _ in range(25):
    for f in funcs:
        t = timeit(f, number=1)
        times[f].append(t)
for f in sorted(funcs, key=stats):
    print(stats(f), f.__name__)

print('\nPython:', sys.version)

Attempt This Online!