Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: generation of random multiset permutation with restrictions
Replies: 17   Last Post: Jan 30, 2013 6:41 AM

 Messages: [ Previous | Next ]
 Bruno Luong Posts: 9,822 Registered: 7/26/08
Re: generation of random multiset permutation with restrictions
Posted: Aug 21, 2012 9:49 AM

I will change the generate random permutation with restrictio. D will be different than my first post, but the goal of generaion is respected.

a = [1,1,1,2,2,3,3,3]
s = {[3],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[2,3],[2,3]};

%% Covert cell of sets to boolean array
m = max(a(:));
n = length(a);
j = arrayfun(@(j) j+zeros(size(s{j})), 1:n, 'unif', 0);
sbool = accumarray([s{:}; j{:}]',1, [m n])
clear m n j

%% Generate 100 vectors p, a permutation of a, and respecting the set-constraints
% p is ranged in 100 x 8 arrays, working with a and sbool
[m n] = size(sbool); % 3 x 8
[~, ia] = sort(rand(100,n),2);
p = a(ia);
c = m*(0:n-1)';
pp = permute(p, [3 2 1]);
D = 1-sbool(bsxfun(@plus,pp,c));
for k=1:size(p,1) % 100
[i cost] = assignmentoptimal(D(:,:,k));
if any(i==0) || cost>0
error('No solution exists');
end
p(k,:) = p(k,i);
end
disp(p)

%% Some p
p1 = [3,1,1,1,2,2,3,3];
p2 = [1,3,1,1,2,2,3,3];
p = [p1; p2]
clear p1 p2

% Check the validity of p
% working with a and sbool
[m n] = size(sbool);
OK = @(p) all(sbool(bsxfun(@plus,p,m*(0:n-1))) & bsxfun(@eq,sort(p,2),sort(a)),2);
OK(p)

% Bruno

Date Subject Author
8/9/12 Michal Kvasnicka
8/10/12 Bruno Luong
8/10/12 Michal Kvasnicka
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/21/12 Michal Kvasnicka
8/21/12 Bruno Luong
8/23/12 Michal Kvasnicka
1/29/13 Michal Kvasnicka
1/30/13 Michal Kvasnicka
1/30/13 Bruno Luong
1/30/13 Michal Kvasnicka
1/30/13 Bruno Luong
1/30/13 Michal Kvasnicka