Is there a fast algorithm for generating all partitions of a set into subsets of size 2 (and one subset of size 1)?

Partition should be viewed as a set and two partition differing only by order should be considered as the same one. So there are only 3 partitions of number set (1,2,3,4).

the number of partitions should be N!/(N/2)!/2^(N/2). Using Stirling's formula, it is approx. Sqrt(2)*(N/e)^(N/2) where e=2.71828... and very huge.

I leveraged @VirtualScooter's code and provide the recursive version of Partition, which runs faster than his itertools version (note this is not an apple-apple comparison because my Partition has no repeats).

import itertools
import timeit
t3 = (1, 2, 3)
t4 = (1, 2, 3, 4)
t6 = (1, 2, 3, 4, 5, 6)

def grouper(iterable, n, fillvalue=None):
    """Collect data into fixed-length chunks or blocks.
        Code from Python itertools page
    """
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return itertools.zip_longest(*args, fillvalue=fillvalue)

def partitionIntoPairs(collection):
    perms = itertools.permutations(collection)
    for p in perms:
        group = list(grouper(p, 2))
        if group[-1][-1] is None:
            group[-1] = (group[-1][0],)
        yield group

def Partition(Indexable):
    if len(Indexable)<=2:
        yield [Indexable]
    elif len(Indexable)%2==1:
        for i,x in enumerate(Indexable):
            for s in Partition(Indexable[:i]+Indexable[i+1:]):
                yield [[x]]+s
    else:
        for i,x in enumerate(Indexable):
            if i==0:
                x0=x
            else:
                for s in Partition(Indexable[1:i]+Indexable[i+1:]):
                    yield [[x0,x]]+s
def comp_timeit(collection, repeats=1_000):
    s1 = f"l1 = list(Partition({collection}))"
    s2 = f"l1 = list(partitionIntoPairs({collection}))"
    t1 = timeit.timeit(s1, globals=globals(),number=repeats)
    t2 = timeit.timeit(s2, globals=globals(),number=repeats)
    print(f"partition, {repeats:_} runs: {t1:,.4f}")
    print(f"itertools, {repeats:_} runs: {t2:,.4f}")
for p in Partition(t4):
    print(p)
comp_timeit(t3)
comp_timeit(t4)
comp_timeit(t6)

This recursive generator function yields partitions when the length of the partition is the same as the original input, and only makes recursive calls when it can either add to a subpartition in progress or retain a single subpartition (if len(data)%2 == 1) :

data = {1, 2, 3}
def partition(d, m, c = []):
   if len(l:=[j for k in c for j in k]) == len(d):
      yield c
   for i in filter(lambda x:x not in l, d):
      if not c or len(c[-1]) == m:
         yield from partition(d, m, c=c+[[i]])
      else:
         if sum(len(i) == 1 for i in c) == 1 and len(data)%2:
            yield from partition(d, m, c=c+[[i]])
         yield from partition(d, m, c=[*c[:-1], c[-1]+[i]])


print(list(partition(list(data), 2)))

Output:

[[[1], [2, 3]], [[1, 2], [3]], [[1], [3, 2]], [[1, 3], [2]], [[2], [1, 3]], [[2, 1], [3]], [[2], [3, 1]], [[2, 3], [1]], [[3], [1, 2]], [[3, 1], [2]], [[3], [2, 1]], [[3, 2], [1]]]

When len(data)%2 == 0:

data = {1, 2, 3, 4}
print(list(partition(list(data), 2)))

Output:

[[[1, 2], [3, 4]], [[1, 2], [4, 3]], [[1, 3], [2, 4]], [[1, 3], [4, 2]], [[1, 4], [2, 3]], [[1, 4], [3, 2]], [[2, 1], [3, 4]], [[2, 1], [4, 3]], [[2, 3], [1, 4]], [[2, 3], [4, 1]], [[2, 4], [1, 3]], [[2, 4], [3, 1]], [[3, 1], [2, 4]], [[3, 1], [4, 2]], [[3, 2], [1, 4]], [[3, 2], [4, 1]], [[3, 4], [1, 2]], [[3, 4], [2, 1]], [[4, 1], [2, 3]], [[4, 1], [3, 2]], [[4, 2], [1, 3]], [[4, 2], [3, 1]], [[4, 3], [1, 2]], [[4, 3], [2, 1]]]

This can be done with itertools, probably faster than a recursive algorithm, like partition in another answer (https://stackoverflow.com/a/66972507/5660315). I measured 4.5s runtime for t6 in my timeit sequence like below, versus times lower than 0.2s for mi_partition.

The first idea was to first list all permutations of the set, then split each in subsets, using the grouper algorithm from the itertools document page. Then, we cull the filler for the final odd-size subset if applicable.

As @Bing Wang points out, duplicates occur in this type of sequence. So, instead, I called upon the more_itertools.set_partitions function, which cuts down on the repetition. This also generates subsets with length greater than 2, so these are filtered out with itertools.filterfalse.

import itertools
import timeit
import more_itertools

t3 = (1, 2, 3)
t4 = (1, 2, 3, 4)
t6 = (1, 2, 3, 4, 5, 6)

def mi_partition(collection):
    k = len(collection) // 2 + len(collection) % 2
    s1 = more_itertools.set_partitions(collection, k)
    if False:
        p1, p2 = itertools.tee(s1)
        print(len(list(p1)))
        s1 = p2
    return itertools.filterfalse(lambda x: any(len(y)>2 for y in x), s1)

print(list(mi_partition(t3)))
print(list(mi_partition(t4)))

Output:

[[[1], [2, 3]], [[1, 2], [3]], [[2], [1, 3]]]
[[[1, 2], [3, 4]], [[2, 3], [1, 4]], [[1, 3], [2, 4]]]

A small timing comparison with the Partition algorithm from @Bing Wang's answer, suggests that their solution is faster:

def comp_timeit(collection, repeats=1_000):
    s3 = f"l1 = list(mi_partition({collection}))"
    s4 = f"l1 = list(Partition({collection}))"
    t3 = timeit.timeit(s3, globals=globals(),number=repeats)
    print(f"more_itertools, {repeats:_} runs: {t3:,.4f}")
    t4 = timeit.timeit(s4, globals=globals(),number=repeats)
    print(f"Partition, {repeats:_} runs: {t4:,.4f}")
comp_timeit(t3)
comp_timeit(t4)
comp_timeit(t6)

Output below. Note that for t3 to t4, the result list has length 3 in both cases, while for t5, it's length 15. It seems the Partitions solution is slightly faster, probably because it does not need to filter any solutions. For t6, set_partitions(t6, 3) generates 90 partitions, with only 15 making it into the final answer.

more_itertools, 1_000 runs: 0.0051
Partition, 1_000 runs: 0.0024
more_itertools, 1_000 runs: 0.0111
Partition, 1_000 runs: 0.0026
more_itertools, 1_000 runs: 0.1333
Partition, 1_000 runs: 0.0160```

Your examples didn't show what does mean "all the subsets". If you need to get all possible pairs of values in the given set just try to use set() and frozenset()

my_set = {1,2,3,}

res = set()
for value in my_set:
    current_set = set()
    current_set.add(value)
    for value in my_set:
        new_set = current_set.copy()
        new_set.add(value)
        res.add(frozenset(new_set))
        
if not len(my_set) % 2:
    res = [list(new_set) for new_set in res if len(new_set) > 1]
else:
    res = list(map(list, res))
print(res)