2

How can I iterate over all disjoints pairs of pairs from range(n)?

For example, set n = 4. Then you would iterate over should be

[((0,1),(2,3)),((0,2),(1,3)), ((0,3),(1,2))]

If n=5 then you would iterate over

[((0,1),(2,3)), ((0,1),(2,4)), ((0,1),(3,4)), ((0,2),(1,3)),((0,2),(1,4)), ((0,3),(1,2)),  ((0,3),(1,4)), ((0,4),(1,2)), ((0,4), (1,3)), ((0,4),(2,3)) ...
marshall
  • 2,443
  • 7
  • 25
  • 45
  • Will `n` always be even? – Kevin Jan 15 '14 at 14:46
  • 1
    What is the expected output for n=5? – Kevin Jan 15 '14 at 14:47
  • possible duplicate of [how to split a list into pairs in all possible ways](http://stackoverflow.com/questions/5360220/how-to-split-a-list-into-pairs-in-all-possible-ways) – roippi Jan 15 '14 at 14:50
  • @roippi It is similar. The only difference is that I only want pairs of pairs where in that answer they split the whole list into pairs. – marshall Jan 15 '14 at 14:51

2 Answers2

1

You can do:

import itertools

n = 4
data = range(n)
for item1 in itertools.combinations(data, 2):
    for item2 in itertools.combinations(data, 2):
        if item1 < item2 and not set(item1) & set(item2):
            print item1, item2

This gives:

(0, 1) (2, 3)
(0, 2) (1, 3)
(0, 3) (1, 2)
Simeon Visser
  • 118,920
  • 18
  • 185
  • 180
  • I would do `if not set(item1) & set(item2)` to avoid creating an additional `set`. – Joel Cornett Jan 15 '14 at 14:52
  • Thank you but this method quite inefficient isn't it? I mean it creates a lot of pairs it doesn't use. – marshall Jan 15 '14 at 15:00
  • @marshall: how big can `n` become? – Simeon Visser Jan 15 '14 at 15:02
  • Well, for `n = 1000` there are about 249 billion pairs of pairs that one can possibly construct from the input. However, for any given pair most other pairs are valid combinations. For example, for `(0, 1)` only the pairs that contain `0` and `1` are invalid, all others can be combined with `(0, 1)` to give a valid pair of pairs. So although the algorithm skips those invalid pairs, most pairs that are compared will be valid. Note that the `item1 < item2` also eliminates many pairs that have already been looked at earlier. – Simeon Visser Jan 15 '14 at 15:28
  • Right. The output size should be 124,251,374,250 so I suppose you only waste half the time. – marshall Jan 15 '14 at 15:40
1
from itertools import combinations
n = 4
disjoints = [x for x in combinations(map(set, combinations(range(n), 2)), 2) 
    if not x[0] & x[1]]

Outputs:

[(set([0, 1]), set([2, 3])),
 (set([0, 2]), set([1, 3])),
 (set([0, 3]), set([1, 2]))]
Joel Cornett
  • 24,192
  • 9
  • 66
  • 88