Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
generation of random multiset permutation with restrictions

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 9 Aug, 2012 11:22:13

Message: 1 of 18

I am looking for MATLAB algorithm how to effectively generate any random multiset permutations with additional restrictions.

Example: I have a multiset of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. So, I am looking for permutations of items, but the first element must be 3, and the second must be 1 or 2, etc.

One such permutation that fits the restrictions is: {3,1,1,1,2,2,3,3}

Of course, any check if the restrictions are consistent, i.g. exist at least one possible permutation will important too.

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 10 Aug, 2012 07:10:25

Message: 2 of 18

"Michal Kvasnicka" wrote in message <k006h5$9e6$1@newscl01ah.mathworks.com>...
> I am looking for MATLAB algorithm how to effectively generate any random multiset permutations with additional restrictions.
>
> Example: I have a multiset of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. So, I am looking for permutations of items, but the first element must be 3, and the second must be 1 or 2, etc.
>
> One such permutation that fits the restrictions is: {3,1,1,1,2,2,3,3}
>
> Of course, any check if the restrictions are consistent, i.g. exist at least one possible permutation will important too.

You might use Hungarian's assignment, one of such implementation is on FEX
http://www.mathworks.com/matlabcentral/fileexchange/6543

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]};

% Engine
% Shuffle
p = a(randperm(length(a)));
% Distance matrix
D = cellfun(@(x) min(abs(bsxfun(@minus,x(:),p)),[],1), s, 'unif', 0);
D = cat(1,D{:});
[i cost] = assignmentoptimal(D);
if all(i) && cost==0
    p = p(i');
    disp(p)
else
    disp('No solution');
end

% Bruno

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 10 Aug, 2012 08:01:12

Message: 3 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k02c51$lo6$1@newscl01ah.mathworks.com>...
> "Michal Kvasnicka" wrote in message <k006h5$9e6$1@newscl01ah.mathworks.com>...
> > I am looking for MATLAB algorithm how to effectively generate any random multiset permutations with additional restrictions.
> >
> > Example: I have a multiset of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. So, I am looking for permutations of items, but the first element must be 3, and the second must be 1 or 2, etc.
> >
> > One such permutation that fits the restrictions is: {3,1,1,1,2,2,3,3}
> >
> > Of course, any check if the restrictions are consistent, i.g. exist at least one possible permutation will important too.
>
> You might use Hungarian's assignment, one of such implementation is on FEX
> http://www.mathworks.com/matlabcentral/fileexchange/6543
>
> 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]};
>
> % Engine
> % Shuffle
> p = a(randperm(length(a)));
> % Distance matrix
> D = cellfun(@(x) min(abs(bsxfun(@minus,x(:),p)),[],1), s, 'unif', 0);
> D = cat(1,D{:});
> [i cost] = assignmentoptimal(D);
> if all(i) && cost==0
> p = p(i');
> disp(p)
> else
> disp('No solution');
> end
>
> % Bruno

Bruno, thank you very much for your help!!! The Hungarian's assignment perfectly solve may problem.

Thanks again!

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 21 Aug, 2012 08:16:08

Message: 4 of 18

"Michal Kvasnicka" wrote in message <k02f48$vs$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k02c51$lo6$1@newscl01ah.mathworks.com>...
> > "Michal Kvasnicka" wrote in message <k006h5$9e6$1@newscl01ah.mathworks.com>...
> > > I am looking for MATLAB algorithm how to effectively generate any random multiset permutations with additional restrictions.
> > >
> > > Example: I have a multiset of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. So, I am looking for permutations of items, but the first element must be 3, and the second must be 1 or 2, etc.
> > >
> > > One such permutation that fits the restrictions is: {3,1,1,1,2,2,3,3}
> > >
> > > Of course, any check if the restrictions are consistent, i.g. exist at least one possible permutation will important too.
> >
> > You might use Hungarian's assignment, one of such implementation is on FEX
> > http://www.mathworks.com/matlabcentral/fileexchange/6543
> >
> > 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]};
> >
> > % Engine
> > % Shuffle
> > p = a(randperm(length(a)));
> > % Distance matrix
> > D = cellfun(@(x) min(abs(bsxfun(@minus,x(:),p)),[],1), s, 'unif', 0);
> > D = cat(1,D{:});
> > [i cost] = assignmentoptimal(D);
> > if all(i) && cost==0
> > p = p(i');
> > disp(p)
> > else
> > disp('No solution');
> > end
> >
> > % Bruno
>
> Bruno, thank you very much for your help!!! The Hungarian's assignment perfectly solve may problem.
>
> Thanks again!
Bruno, could you help me once again? I need to perform so called "consistency" check, which mean, that I need to perform check if the current permutation satisfy the predefined restrictions.

Example:
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]};

p1 = {3,1,1,1,2,2,3,3} -> OK
p2 = {1,3,1,1,2,2,3,3} -> not OK

Is there any simple way hot to use effectivelly Hungarian's assignment, too?

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 21 Aug, 2012 08:29:07

Message: 5 of 18

>
> Is there any simple way hot to use effectivelly Hungarian's assignment, too?

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

OK = @(p) all(cellfun(@ismember,p,s)) && isequal(sort(a),sort([p{:}]));

p1 = {3,1,1,1,2,2,3,3}
OK(p1)
p2 = {1,3,1,1,2,2,3,3}
OK(p2)

% Bruno

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 21 Aug, 2012 08:54:07

Message: 6 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0vgsi$bfu$1@newscl01ah.mathworks.com>...
> >
> > Is there any simple way hot to use effectivelly Hungarian's assignment, too?
>
> s = {[3],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[2,3],[2,3]};
> a = [1,1,1,2,2,3,3,3]
>
> OK = @(p) all(cellfun(@ismember,p,s)) && isequal(sort(a),sort([p{:}]));
>
> p1 = {3,1,1,1,2,2,3,3}
> OK(p1)
> p2 = {1,3,1,1,2,2,3,3}
> OK(p2)
>
> % Bruno
great! But I made the mistake. Testing permutations are not cells, p is only standard vector:

p1 = [3,1,1,1,2,2,3,3]
OK(p1)
p2 = [1,3,1,1,2,2,3,3]
OK(p2)

How to modify your OK function in this case? Just use cell2mat function?

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 21 Aug, 2012 09:03:07

Message: 7 of 18

This should work for standard array p:
 
OK = @(p) isequal(sort(a),sort(p)) && all(arrayfun(@(x,s) ismember(x,s{1}),p,s));

% Bruno

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 21 Aug, 2012 10:51:08

Message: 8 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0visb$hog$1@newscl01ah.mathworks.com>...
> This should work for standard array p:
>
> OK = @(p) isequal(sort(a),sort(p)) && all(arrayfun(@(x,s) ismember(x,s{1}),p,s));
>
> % Bruno

Your solution is very elegant and effective. Thanks again!

Is there any reason to completely eliminate cells (e.g. s = {[3],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[2,3],[2,3]};) from the numerical intensive computation and work only with standard arrays? OK function (and previous method for generation of random multiset permutation with restrictions) will be called very often (about 10^3-10^6 times), so I am looking for fastest method as possible.

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 21 Aug, 2012 11:01:07

Message: 9 of 18

"Michal Kvasnicka" wrote in message <k0vp6r$83h$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0visb$hog$1@newscl01ah.mathworks.com>...
> > This should work for standard array p:
> >
> > OK = @(p) isequal(sort(a),sort(p)) && all(arrayfun(@(x,s) ismember(x,s{1}),p,s));
> >
> > % Bruno
>
> Your solution is very elegant and effective. Thanks again!
>
> Is there any reason to completely eliminate cells (e.g. s = {[3],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[2,3],[2,3]};) from the numerical intensive computation and work only with standard arrays? OK function (and previous method for generation of random multiset permutation with restrictions) will be called very often (about 10^3-10^6 times), so I am looking for fastest method as possible.

If your set is not too large you might use logical array to store a set, e.g.
{3} is coded as [0 0 1]';
{1 2} is coded as [1 1 0]';

And s as
[0 0 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 0 1 1; 0 1 1]' ;

Bruno

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 21 Aug, 2012 11:32:08

Message: 10 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0vppj$9u1$1@newscl01ah.mathworks.com>...
> "Michal Kvasnicka" wrote in message <k0vp6r$83h$1@newscl01ah.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k0visb$hog$1@newscl01ah.mathworks.com>...
> > > This should work for standard array p:
> > >
> > > OK = @(p) isequal(sort(a),sort(p)) && all(arrayfun(@(x,s) ismember(x,s{1}),p,s));
> > >
> > > % Bruno
> >
> > Your solution is very elegant and effective. Thanks again!
> >
> > Is there any reason to completely eliminate cells (e.g. s = {[3],[1,2],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[2,3],[2,3]};) from the numerical intensive computation and work only with standard arrays? OK function (and previous method for generation of random multiset permutation with restrictions) will be called very often (about 10^3-10^6 times), so I am looking for fastest method as possible.
>
> If your set is not too large you might use logical array to store a set, e.g.
> {3} is coded as [0 0 1]';
> {1 2} is coded as [1 1 0]';
>
> And s as
> [0 0 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 0 1 1; 0 1 1]' ;
>
> Bruno
OK ... this looks very interesting.

How do I change the following lines of code to work with logical restriction array
s = [0 0 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 0 1 1; 0 1 1]' ?

D = cellfun(@(x) min(abs(bsxfun(@minus,x(:),p)),[],1), s, 'unif', 0);
D = cat(1,D{:});

and

OK = @(p) isequal(sort(a),sort(p)) && all(arrayfun(@(x,s) ismember(x,s{1}),p,s));

And how to convert these two restrictions representations between each other?

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 21 Aug, 2012 13:49:10

Message: 11 of 18

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

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 23 Aug, 2012 10:22:07

Message: 12 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k103kl$g6d$1@newscl01ah.mathworks.com>...
> 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

Thank you, this is good method.

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 29 Jan, 2013 16:37:08

Message: 13 of 18

Is possible to modify above mentioned methods to generate complete list of the multiset permutations with restrictions?

It would be very usefull at least for small dimension problems.

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 30 Jan, 2013 07:30:13

Message: 14 of 18

"Michal Kvasnicka" wrote in message <ke8trj$mbp$1@newscl01ah.mathworks.com>...
> Is possible to modify above mentioned methods to generate complete list of the multiset permutations with restrictions?
>
> It would be very usefull at least for small dimension problems.

Of course, there will be possible to generate all multiset permutations and then test each permutation on restrictions, but may be exist some more effective algorithm.
Any hints?

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 30 Jan, 2013 08:34:08

Message: 15 of 18

Dynamic programming:

function p= allpc(a, s)

s = cellfun(@sort, s, 'unif', 0);
[u, ~, J] = unique(a);
n = accumarray(J(:), 1);
p = fliplr(allpc_engine(s, u, n));

end % allpc

%%
function p = allpc_engine(s, u, n)

s1 = s{1};
[b, loc] = ismember(s1, u);
s1 = s1(b);
s = s(2:end);
if isempty(s)
    p = s1;
    return
end
loc = loc(b);
p = [];
for i = 1:length(s1)
    j = loc(i);
    n(j) = n(j)-1;
    old = u(j);
    if n(j) <= 0
        u(j) = Inf;
    end
    q = allpc_engine(s, u, n);
    if ~isempty(q)
        q(:,end+1) = s1(i);
        p = [p; q];
    end
    u(j) = old;
    n(j) = n(j)+1;
end

end % allpc_engine


%% Test
>> a = [1,1,1,2,2,3,3,3]

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]};

>> p = allpc(a,s)

p =

     3 1 1 1 2 2 3 3
     3 1 1 1 2 3 2 3
     3 1 1 1 2 3 3 2
     3 1 1 1 3 2 2 3
     3 1 1 1 3 2 3 2
     3 1 1 1 3 3 2 2
     3 1 1 2 1 2 3 3
     3 1 1 2 1 3 2 3
     3 1 1 2 1 3 3 2
     3 1 1 2 2 1 3 3
     3 1 1 2 3 1 2 3
     3 1 1 2 3 1 3 2
     3 1 1 3 1 2 2 3
     3 1 1 3 1 2 3 2
     3 1 1 3 1 3 2 2
     3 1 1 3 2 1 2 3
     3 1 1 3 2 1 3 2
     3 1 1 3 3 1 2 2
     3 1 2 1 1 2 3 3
     3 1 2 1 1 3 2 3
     3 1 2 1 1 3 3 2
     3 1 2 1 2 1 3 3
     3 1 2 1 3 1 2 3
     3 1 2 1 3 1 3 2
     3 1 2 2 1 1 3 3
     3 1 2 3 1 1 2 3
     3 1 2 3 1 1 3 2
     3 1 3 1 1 2 2 3
     3 1 3 1 1 2 3 2
     3 1 3 1 1 3 2 2
     3 1 3 1 2 1 2 3
     3 1 3 1 2 1 3 2
     3 1 3 1 3 1 2 2
     3 1 3 2 1 1 2 3
     3 1 3 2 1 1 3 2
     3 1 3 3 1 1 2 2
     3 2 1 1 1 2 3 3
     3 2 1 1 1 3 2 3
     3 2 1 1 1 3 3 2
     3 2 1 1 2 1 3 3
     3 2 1 1 3 1 2 3
     3 2 1 1 3 1 3 2
     3 2 1 2 1 1 3 3
     3 2 1 3 1 1 2 3
     3 2 1 3 1 1 3 2
     3 2 2 1 1 1 3 3
     3 2 3 1 1 1 2 3
     3 2 3 1 1 1 3 2

% Bruno

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 30 Jan, 2013 11:05:08

Message: 16 of 18

As always, very elegant solution, thanks!

Can I have few additional questions:
1. the "ismember" function is the most time consuming function during the computation. Is there any chance to create some faster aleternative, see for example http://www.mathworks.com/matlabcentral/newsreader/view_thread/306676#832549
2. Will be possible just count the succesful permutations, without permutation generation?
3. Will be possible to prealocate variables "p" and "q"? For bigger dimensions the expanding is slower and slower?

Subject: generation of random multiset permutation with restrictions

From: Bruno Luong

Date: 30 Jan, 2013 11:34:08

Message: 17 of 18

"Michal Kvasnicka" wrote in message <keaup4$i8g$1@newscl01ah.mathworks.com>...
> As always, very elegant solution, thanks!
>
> Can I have few additional questions:
> 1. the "ismember" function is the most time consuming function during the computation. Is there any chance to create some faster aleternative, see for example http://www.mathworks.com/matlabcentral/newsreader/view_thread/306676#832549
> 2. Will be possible just count the succesful permutations, without permutation generation?
> 3. Will be possible to prealocate variables "p" and "q"? For bigger dimensions the expanding is slower and slower?

At some point, you should try it on your own to adap to you need.

Bruno

Subject: generation of random multiset permutation with restrictions

From: Michal Kvasnicka

Date: 30 Jan, 2013 11:41:06

Message: 18 of 18

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <keb0fg$nm2$1@newscl01ah.mathworks.com>...
> "Michal Kvasnicka" wrote in message <keaup4$i8g$1@newscl01ah.mathworks.com>...
> > As always, very elegant solution, thanks!
> >
> > Can I have few additional questions:
> > 1. the "ismember" function is the most time consuming function during the computation. Is there any chance to create some faster aleternative, see for example http://www.mathworks.com/matlabcentral/newsreader/view_thread/306676#832549
> > 2. Will be possible just count the succesful permutations, without permutation generation?
> > 3. Will be possible to prealocate variables "p" and "q"? For bigger dimensions the expanding is slower and slower?
>
> At some point, you should try it on your own to adap to you need.
>
> Bruno

yes, of course.,anyway thank you again for your help.

Michal

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us