Unique combinations of a beaded necklace

Question

So I'm writing a program to determine the unique combinations of a beaded necklace, but I can't seem to get it right. The rules are you can't have the same necklace forwards and backwards, and you can't have the same necklace with one bead being slid around to the other end. I've attached some pictures to clarify.

I wrote the code for it, and I thought I had achieved what I was trying to do, but it's not working correctly.

n = [1 2 3 4 2 4];
% green = 1
% blue = 2
% yellow = 3
% red = 4

p = perms(n);
total = max(size(p));
for i = 1:max(size(p))
    q = p;
    q(i) = [];
    for j = 1:max(size(q))
        if isequal(p(i),fliplr(q(j)))
            total = total - 1;
        elseif isequal(p(i),circshift(q(j),[1,1]))
            total = total - 1;
        elseif isequal(p(i),circshift(q(j),[length(q(j))-1,length(q(j))-1]))
            total = total - 1;
        end
        disp(total)
    end
end

Logically, this makes sense to me, but I could just be crazy.

Luis Mendo · Answer 1 · 2014-10-10T16:46:02.860

If the problem size is small, you can vectorize all the comparisons (using bsxfun):

n = [1 2 3 4 2 4];
%// green = 1
%// blue = 2
%// yellow = 3
%// red = 4

N = numel(n);
p = perms(n).'; %'// generate all permutations

p2 = NaN([size(p) N+1]); %// this will store permutations with flips and shifts
p2(:,:,1) = p; %// original
p2(:,:,2) = flipud(p); %// flips
for k = 1:N-1
    p2(:,:,2+k) = circshift(p,k); %// circular shifts
end

eqElem = bsxfun(@eq, p, permute(p2, [1 4 2 3]));
eqMat = squeeze(any(all(eqElem, 1), 4)); %// 1 if equal
remove = any(tril(eqMat, -1), 1); %// remove permutations that are "similar"
%// to a previous one, where "similar" means "equal up to circular shifts or
%// flips"
result = p(:,~remove).'; %'// all valid arrangements; one per row
resultNum = size(result, 1); %// number of arrangements

Results:

result =
     1     3     2     2     4     4
     1     3     2     4     4     2
     1     3     2     4     2     4
     1     3     4     2     2     4
     1     3     4     2     4     2
     1     3     4     4     2     2
     1     2     3     2     4     4
     1     2     3     4     2     4
     1     2     3     4     4     2
     1     2     2     3     4     4
     1     2     2     4     4     3
     1     2     2     4     3     4
     1     2     4     3     2     4
     1     2     4     3     4     2
     1     2     4     2     3     4
     1     2     4     2     4     3
     1     2     4     4     2     3
     1     2     4     4     3     2
     1     4     4     3     2     2
     1     4     4     2     2     3
     1     4     4     2     3     2
     1     4     3     4     2     2
     1     4     3     2     2     4
     1     4     3     2     4     2
     1     4     2     3     2     4
     1     4     2     3     4     2
     1     4     2     2     3     4
     1     4     2     2     4     3
     1     4     2     4     2     3
     1     4     2     4     3     2

resultNum =
    30

score 0 · Accepted Answer · answered Oct 10 '14 at 16:26

You should do p = unique(p,'rows') before any loops. To see why, call perms([1 1 1]) at the command line.

There are a few issues here:

1) p, the perms, is a 2D matrix, so to get each perm you need to do p(i,:) to get the row. p(i) is just a single number.

2) You don't remove wrong answers from your list, so you will check against them twice. For example, say the first in the list is [1 2 3 4 2 4]; and the second is [4 2 4 3 2 1];. The fliplr check will compare these two combinations twice, once in the first loop around, once in the second.

3) If you want to make sure that any permutation which is a rotation is excluded (not just moving one bead around), you'll need some more circshift.

Consider using ismember with rows option again to compare a single row (e.g. a flipped version of the row you're checking) to an entire matrix.

I got it. It may have been a bit sloppy, but I think I got it. I tried to the same thing with a 1x3 matrix and it was a lot easier to understand on a smaller level. The biggest mistake I made was simply using p(i) instead of p(i,:). Thanks for the help. — Tony, Oct 10 '14 at 16:41

Unique combinations of a beaded necklace

2 Answers2