permute tuple combinations among nested list

Question

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')),...)

This will be very helpful in solving your problem. https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python — Beginner, Nov 07 '18 at 04:39

Ajax1234 · Accepted Answer · 2018-11-07T04:17:56.913

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'))
...

If I have a list of 5 sublists, is it possible to permute from 2 to 5? like `[((),()),...,((),(),()),...,((),(),(),()),...,((),(),(),(),()),...]` — Anita, Nov 07 '18 at 03:30
@Abbey I just saw your most recent edit. Adding a solution that meets the criteria... — Ajax1234, Nov 07 '18 at 03:35
Sorry for the confusion. I didn't ask my questions explicitly in the beginning. The current edit is the final touch. Let me try and understand your self-define function. — Anita, Nov 07 '18 at 03:41
@Abbey No problem. Please see my recent edit. I think the solution covers all the proper criteria. — Ajax1234, Nov 07 '18 at 03:51
@ Ajax1234 Hi could you please explain these two lines of code? Much appreciated! `if len(_c) == 1 and not any(all(t in h for t in _c+[c]) for h in d)` and `yield from combinations(d[1:], _c = [] if len(_c) > 0 else _c+[c])` — Anita, Nov 08 '18 at 22:31
@Abbey That particular line is used to find all the combinations of two different elements from the input. The conditional checks that there is one element in the list storing the current permutation, and if the latter is true, `any(all(t in h for t in _c+[c]) for h in d)` is evaluated to ensure that the elements in `_c+[c]` do not occur in the same list in the initial input. Lastly, if the entire condition is true, `yield from combinations(d[1:], _c = [] if len(_c) > 0 else _c+[c])` will call the function again, passing a sliced input and reassigning the default parameter of the function. — Ajax1234, Nov 08 '18 at 22:51

permute tuple combinations among nested list

1 Answers1