Combinations from itertools behaving weird

Question

I need to identify pairs of subsets of the same size such that they are disjoint and that if we order the sets A={a_1<a_2<...<a_m} and B{b_1<b_2<...<b_m} then for every i=1,...,m a_i<b_i.

Here's my code:

n=7
cont=0
for m in range(2,n//2+1):
    combs=combinations(list(range(n)),m)
    combs=[set(comb) for comb in combs]
    print(combs)
    pairs=[(comb1,comb2) for comb1 in combs for comb2 in combs if comb1.intersection(comb2)==set()]
    pairs=[pair for pair in pairs if npmin(list(pair[0]))<npmin(list(pair[1]))]
    flag=True
    for pair in pairs:
        l1=list(pair[0])
        l2=list(pair[1])
        l1.sort()
        l2.sort()
        flag=True
        for n in range(m):
            flag=flag and l1[n]<l2[n]
        if not flag:
            cont+=1
cont

The expected output for this case, n=7, would be 70.

But, here's the thing, for the second iteration, m=3, the list combs is empty, so that for m=3 cont stays the same value, and the code then outputs a 35. I can't understand why. Any help is welcomed!

Answer 1

It's unclear what you're trying to do.

However, I made a few changes, that might help.

First, you can use SortedSet() so that you don't have to sort() every time.

Your question

For m == 3, it prints

combs

[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 1, 6), (0, 2, 3), (0, 2, 4), (0, 2, 5), (0, 2, 6), (0, 3, 4), (0, 3, 5), (0, 3, 6), (0, 4, 5), (0, 4, 6), (0, 5, 6), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 4), (1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (1, 5, 6), (2, 3, 4), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)]

Right?

---

• I guess you don't want the same var names for n, combs and pairs.

from itertools import combinations
import numpy as np
from sortedcontainers import SortedSet


def f(n):
    cont = 0
    for m in range(2, n // 2 + 1):
        if m > n:
            continue

        combs = combinations(list(range(n)), m)
        # if m == 3:
        #     print(list(combs))
        #     break
        scombs = [set(comb) for comb in combs]
        pairs = [(comb1, comb2) for comb1 in scombs for comb2 in scombs if comb1.intersection(comb2) == SortedSet()]
        spairs = [pair for pair in pairs if np.min(list(pair[0])) < np.min(list(pair[1]))]
        for l1, l2 in spairs:
            flag = True
            l1, l2 = list(l1), list(l2)
            for i in range(m):
                flag = flag and l1[i] < l2[i]
            if not flag:
                cont += 1
    return cont


print(f(7))

Outputs

70

Note

• Make sure you're passing the correct n (inclusive) to combinations, if that's what you want:

combs = combinations(list(range(n + 1)), m)

• You also forgot to add if m > n: continue.