Get all combinations of items in a list while prohibiting certain items from being together

Question

Say I have a list as follows:

spam = ['A1', 'A2', 'B1', 'B2', 'C1', 'C2']

I want to get all possible combinations of items in this list (of lengths from 1 to len(spam)) while not letting A1 in a combination together with A2, as well as B1 with B2 and C1 with C2.

Expected output:

Combinations of length 1:

[('A1'),
 ('A2'),
 ('B1'),
 ('B2'),
 ('C1'),
 ('C2')]

Combinations of length 2:

[('A1', 'B1'),
 ('A1', 'B2'),
 ('A1', 'C1'),
 ('A1', 'C2'),
 ('A2', 'B1'),
 ('A2', 'B2'),
 ('A2', 'C1'),
 ('A2', 'C2'),
 ('B1', 'C1'),
 ('B1', 'C2'),
 ('B2', 'C1'),
 ('B2', 'C2')]

Combinations of length 3:

[('A1', 'B1', 'C1'),
 ('A1', 'B1', 'C2'),
 ('A1', 'B2', 'C1'),
 ('A1', 'B2', 'C2'),
 ('A2', 'B1', 'C1'),
 ('A2', 'B1', 'C2'),
 ('A2', 'B2', 'C1'),
 ('A2', 'B2', 'C2')]

Combinations of length 4 and higher should return an empty list since no combinations of length 4 and higher can possibly avoid inclusion of prohibited combinations.

Then simply gather combinations of different lengths in one list.

While this seems like a simple task, I don't have much ideas on how to implement this, apart from getting all combinations without restrictions first (via itertools.combinations) and then setting up a complicated rule to filter out all undesired combinations, which seems tedious. Is there an easier way to do this?

Answer 1

you can make use of filter: EDIT:

Your question wast clear at first. This is what you are looking for:

import itertools, re

filter_fun = lambda x: re.search("(.)\\d.*\\1","".join(x)) is None
def get_combs(lst,here = None):
    if here is None: here = {}
    comb = len(here)+1
    a = [i for i in itertools.combinations(lst,comb) if filter_fun(i)]
    if a==[]: return here
    here.update({comb:a})
    return get_combs(lst,here)

get_combs(spam)
{1: [('A1',), ('A2',), ('B1',), ('B2',), ('C1',), ('C2',)],
 2: [('A1', 'B1'),
  ('A1', 'B2'),
  ('A1', 'C1'),
  ('A1', 'C2'),
  ('A2', 'B1'),
  ('A2', 'B2'),
  ('A2', 'C1'),
  ('A2', 'C2'),
  ('B1', 'C1'),
  ('B1', 'C2'),
  ('B2', 'C1'),
  ('B2', 'C2')],
 3: [('A1', 'B1', 'C1'),
  ('A1', 'B1', 'C2'),
  ('A1', 'B2', 'C1'),
  ('A1', 'B2', 'C2'),
  ('A2', 'B1', 'C1'),
  ('A2', 'B1', 'C2'),
  ('A2', 'B2', 'C1'),
  ('A2', 'B2', 'C2')]}