串珠项链的独特组合

因此，我正在编写一个程序来确定一个串珠项链的独特组合，但我似乎无法做到正确。规则是你不能有同样的项链向前和向后，你不能有一个珠子滑到另一端的同一条项链。我附上了一些图片来澄清。串珠项链的独特组合

我写的代码吧，我想我已经达到了我要怎样做，但它不能正常工作。

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

从逻辑上讲，这对我很有意义，但我可能只是疯了。

来源

2014-10-10 Tony

你应该在任何循环之前做p = unique(p,'rows')。要明白为什么，请在命令行中拨打perms([1 1 1])。

这里有几个问题：

1）p的烫发，是一个二维矩阵，所以让每个你需要做p(i,:)让行烫发。 p(i)只是一个单一的数字。

2）你不会从你的列表中删除错误的答案，所以你会检查他们两次。例如，假设列表中的第一个是[1 2 3 4 2 4];，第二个是[4 2 4 3 2 1];。 fliplr检查将比较这两个组合，一次在第一个循环中，一次在第二个循环中。 3）如果你想确保任何排列是一个旋转排除（不只是移动一个珠子），你需要更多的循环。

考虑再次使用ismember和rows选项来将单个行（例如，您正在检查的行的翻转版本）与整个矩阵进行比较。

来源

2014-10-10 16:26:34 nkjt

我知道了。它可能有点草率，但我想我明白了。我试图用1x3矩阵来做同样的事情，并且在更小的层次上理解起来要容易得多。我犯的最大错误是使用p（i）而不是p（i，:)。谢谢您的帮助。 – Tony 2014-10-10 16:41:56

如果问题尺寸小，你可以向量化所有的比较（使用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

结果：

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

来源

2014-10-10 16:27:32

串珠项链的独特组合

回答

相关问题