CODEWITHSUNDEEP
pythonlisttuples
Anita
Anita

Reputation: 285

permute tuple combinations among nested list

I have a nested list and would like to permute the combinations among the list.

test = [[('a',)],
        [('b', 'c'), ('d', 'e')],
        [('f', 'g'), ('h', 'i'), ('j', 'k')],
        [('l', 'm'), ('n', 'o'), ('p', 'q')]]

My expected output is like this:

[(('a',), ('b', 'c')),
 (('a',), ('d', 'e')),
 (('a',), ('f', 'g')),
 (('a',), ('h', 'i')),
 (('a',), ('j', 'k')),
 (('b', 'c'), ('f', 'g')),
 (('b', 'c'), ('h', 'i')),
 (('b', 'c'), ('j', 'k')),
 (('d', 'e'), ('f', 'g')),
 (('d', 'e'), ('h', 'i')),
 (('d', 'e'), ('j', 'k')),
 (('a',), ('b', 'c'), ('f', 'g')),
 (('a',), ('b', 'c'), ('h', 'i')),
 (('a',), ('b', 'c'), ('j', 'k')),
 (('a',), ('d', 'e'), ('f', 'g')),...,
 (('a',), ('b', 'c'), ('f', 'g'), ('l', 'm')), ...]

To further elaborate, my ultimate goal is to permute among tuple lists from the permutation of 2 till the product permutation with the same logic that there is no self permutation. i.e. If there are 5 sublists in a nested list, I will permute from the combination of 2 to 5. Something like this [((),()),...,((),(),()),...,((),(),(),()),...,((),(),(),(),()),...]

I've tried list(itertools.combinations(itertools.chain(*test),2)) but I do not want the permutation among the sublists. For example, I want to exclude

((('b', 'c'), ('d', 'e')),
 (('f', 'g'), ('h', 'i')),
 (('f', 'g'), ('j', 'k')),
 (('h', 'i'), ('j', 'k')),
 (('f', 'g'), ('h', 'i'), ('j', 'k')),...)

Upvotes: 1

Views: 207

Answers (1)

Ajax1234
Ajax1234

Reputation: 71471

You can use recursion:

test = [[('a',)],
    [('b', 'c'), ('d', 'e')],
    [('f', 'g'), ('h', 'i'), ('j', 'k')]] 

def _product(d):
   def combinations(d, _c = []):
      for i, a in enumerate(d):
        for c in a:
          if len(_c) == 1 and not any(all(t in h for t in _c+[c]) for h in d):
            yield tuple(sorted(_c+[c]))
          yield from combinations(d[1:], _c = [] if len(_c) > 0 else _c+[c])
   r = list(combinations(d))
   return [a for i, a in enumerate(r) if a not in r[:i]]

print(_product(test))

Output:

[(('a',), ('b', 'c')), 
 (('a',), ('d', 'e')), 
 (('a',), ('f', 'g')), 
 (('a',), ('h', 'i')), 
 (('a',), ('j', 'k')), 
 (('b', 'c'), ('f', 'g')), 
 (('b', 'c'), ('h', 'i')), 
 (('b', 'c'), ('j', 'k')), 
 (('d', 'e'), ('f', 'g')), 
 (('d', 'e'), ('h', 'i')), 
 (('d', 'e'), ('j', 'k'))]

Edit:

To find all permutations, create a method to find the permutations to a certain length, then iterate over the range of the enter input and use a list comprehension for the full result:

def product(d, _len):
  def combinations(d, _d, current):
    if len(current) == _d:
      yield tuple(sorted(current))
    else:
      if d:
        for i in d:
          for c in i:
            _c = current+[c]
            if not current or (not any(all(t in h for t in _c) for h in d) and len(set(_c))) == len(_c):
              yield from combinations(d, _d, _c)
  r = list(combinations(d, _len, []))
  return [a for i, a in enumerate(r) if a not in r[:i]]

def full_product(test):
  return [i for b in range(2, len(test)+1) for i in product(test, b)]

for i in full_product(test):
  print(i)

Output:

(('a',), ('b', 'c'))
(('a',), ('d', 'e'))
(('a',), ('f', 'g'))
(('a',), ('h', 'i'))
(('a',), ('j', 'k'))
(('b', 'c'), ('f', 'g'))
(('b', 'c'), ('h', 'i'))
(('b', 'c'), ('j', 'k'))
(('d', 'e'), ('f', 'g'))
(('d', 'e'), ('h', 'i'))
(('d', 'e'), ('j', 'k'))
(('a',), ('b', 'c'), ('d', 'e'))
(('a',), ('b', 'c'), ('f', 'g'))
(('a',), ('b', 'c'), ('h', 'i'))
(('a',), ('b', 'c'), ('j', 'k'))
(('a',), ('d', 'e'), ('f', 'g'))
(('a',), ('d', 'e'), ('h', 'i'))
(('a',), ('d', 'e'), ('j', 'k'))
(('a',), ('f', 'g'), ('h', 'i'))
(('a',), ('f', 'g'), ('j', 'k'))
(('a',), ('h', 'i'), ('j', 'k'))
(('b', 'c'), ('d', 'e'), ('f', 'g'))
(('b', 'c'), ('f', 'g'), ('h', 'i'))
(('b', 'c'), ('f', 'g'), ('j', 'k'))
(('b', 'c'), ('d', 'e'), ('h', 'i'))
(('b', 'c'), ('h', 'i'), ('j', 'k'))
(('b', 'c'), ('d', 'e'), ('j', 'k'))
(('d', 'e'), ('f', 'g'), ('h', 'i'))
(('d', 'e'), ('f', 'g'), ('j', 'k'))
(('d', 'e'), ('h', 'i'), ('j', 'k'))

Edit 2: when running full_product on the updated test variable, part of the output when length is four is:

...
(('a',), ('b', 'c'), ('d', 'e'), ('f', 'g'))
(('a',), ('b', 'c'), ('d', 'e'), ('h', 'i'))
(('a',), ('b', 'c'), ('d', 'e'), ('j', 'k'))
(('a',), ('b', 'c'), ('d', 'e'), ('l', 'm'))
(('a',), ('b', 'c'), ('d', 'e'), ('n', 'o'))
(('a',), ('b', 'c'), ('d', 'e'), ('p', 'q'))
...

Upvotes: 1

Related Questions