Set partitions into singletons or pairs

Question

I am trying to build an algorithm to compute the partition of a set into singletons or pairs for a set of cardinality 16. I am doing it in MATLAB and came up with codes that either run forever or require more memory than available. Do you know any time and space efficient algorithm?

I have added my function below.

function out = partition2(n)

A000085 = [1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, 618884638912, 3257843882624, 17492190577600, 95680443760576, 532985208200576, 3020676745975552];
lenA000085 = length(A000085);
if n>length(A000085)
    error(['Cardinality of Y larger than ' num2str(lenA000085) ' not supported yet!']);
end

base = n+1;
lft = ones(1,n) * base.^(n-1:-1:0).';
rgt = (1:n) * base.^(n-1:-1:0).';
out = zeros(A000085(n),n);
cnt = 0;
m = ones(1,n-1)+1;
d = lft;
powers1 = base.^(1-n:0);
powers2 = base.^(n-1:-1:0).';
while d<=rgt
    bs = mod(floor(d.*powers1), base);

    vec = 1:n;
    ndx = vec(bs(2:end)>m);
    if isempty(ndx)
        k = 1;
        bad = false;
        while k<n && ~bad
            if sum(bs==k)>2
                bad = true;
            end
            k = k + 1;
        end
    
        if ~bad
            cnt = cnt + 1;
            out(cnt,:) = bs;
        end
        d = d + 1;
    else
        tmp = n-1:-1:1;
        d = d + base.^tmp(ndx);
        bsNew = mod(floor(d.*powers1), base);
        bsNew(ndx+1) = 1;
        d = bsNew * powers2;
    
        m = cummax(bsNew) + 1;
        m = m(1:end-1);
    
    end
end

Answer 1

Here is one way to generate all partitions of an input array $A$ into singletons and pairs:

1. Let $x$ be the first element of $A$.
2. Recursively generate all partitions of $A \setminus \{x\}$, and add $\{x\}$ to all of them.
3. Go over all elements $y \in A \setminus \{x\}$ (if any); for each one, recursively generate all partitions of $A \setminus \{x,y\}$, and add $\{x,y\}$ to all of them.

A naive python implementation generated all partitions of $1,\ldots,16$ in 18 minutes on my laptop.