1
$\begingroup$

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! Could you share your python code here? I think I could generate the Matlab one from it. $\endgroup$
    – Cesare
    May 21 at 21:12
  • 1
    $\begingroup$ This isn’t a programming site. I described the complete algorithm, and this should suffice for implementing it. $\endgroup$ May 21 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.