# Set partitions into singletons or pairs

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;
if sum(bs==k)>2
end
k = k + 1;
end

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

• Perhaps there are just too many answers? Have you calculated how many? May 21 at 16:28
• No it is manageable. The answer to that is known oeis.org/A000085 May 21 at 17:08
• Try coding your algorithm in C instead. May 21 at 17:59
• I don't think it will be enough. The problem is that I am going through too many useless values. May 21 at 18:03
• I’m not sure what your algorithm is. I only read pseudocode (or textual explanation). May 21 at 18:04

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.