MATLAB: How to generate all possible combination from a sequence

sequence generation

how to generate all possible combination from a n-dimensional vector without repetition of numbers.. i wanted combination of vec = 1:11;

eg:

vec = [1 2 3]
result = [
1 2 3;
1 3 2;
2 3 1;
2 1 3;
3 2 1;
3 1 2];

Best Answer

>> perms(1:3)
ans =
     3     2     1
     3     1     2
     2     3     1
     2     1     3
     1     2     3
     1     3     2

Related Solutions

MATLAB: All combinations of two elements from a 3 by 7 matrix without repeating from the same column

If I presume that you only said you want a constraint on combinations from the same column, since you used that word more often, then there are several ways you might proceed.

The simple answer is to take all possible combinations of 2 elements (without replacement) from the entire array, then toss all cases where the elements came from the same column. This extends simply (in theory) to combinations or more elements. I'd call this a rejection scheme, where you start with the set of all possibilities, then toss those that fail your constraint.

For samples of size 2, that requires generating only 210 combinations.

nchoosek(21,2)
ans =
   210

In the end, it looks like you will have

3^2*nchoosek(7,2)
ans =
   189

possible combinations, so the constraint is not that significant.

You might generate the 210 possible combinations themselves as simply:

C2 = nchoosek(A(:),2);

Then just compute all combinations of two elements from the SAME column as the set of combinations you would exclude. A simple use of setdiff, with the 'rows' option to exclude the samples you don't want will now work.

Extending the latter part to exclude combinations of size n>2 and n<=7 will take a little thought. But I'm not here to write code for you. That would be your job. And really, I'm not advocating a rejection scheme, since it does not extend as nicely to combinations of larger order.

As well, a rejection scheme will grow in size quickly if your real problem is larger than the 3x7 array you initially stated. And people always seem to give a small example, and then assume the answer would be identical if they had a problem 1000 times as large, and that the person answering them would know their real problem was much bigger.

Anyway, rejection schemes might become problematic for larger arrays, or for problems where you want to sample all combinations of order larger than 2.

So while a rejection scheme is often the most obvious, an alternative is to go constructive. Just pick all combinations of two columns. There are

nchoosek(7,2)
ans =
    21

such choices. Then pick all combinations from each pair of columns. A simple scheme would have you just use a loop, over this set of columns:

nchoosek(1:7,2)
ans =
   1     2
   1     3
   1     4
   1     5
   1     6
   1     7
   2     3
   2     4
   2     5
   2     6
   2     7
   3     4
   3     5
   3     6
   3     7
   4     5
   4     6
   4     7
   5     6
   5     7
   6     7

This scheme also extends trivially to combinations of larger order.

How might you simply generate all combinations from two fixed columns? ndgrid will help there. Thus...

[C1,C2] = ndgrid(1:3,1:3);
[C1(:),C2(:)]
ans =
   1     1
   2     1
   3     1
   1     2
   2     2
   3     2
   1     3
   2     3
   3     3

Thus all combinations of 2 elements from two columns, each column of length 3.

Just make sure that you don't grow the array of all combinations in memory. Preallocate it in advance, since you know what the final size will be.

If you write the above code CAREFULLY, it can actually be quite efficient, given the set of combinations you would generate. I see that at most, the final set will be of maximum size 5103 combinations, so the above constructive scheme will be both easy to write and not time consuming at all.

A good thing is that the simple code I describe above will grow in time complexity not too badly if your real problem is larger. Of course, make things too big, and all code becomes nasty and inefficient.

Could you build the set of all such combinations in a vectorized way? Well, yes, you can do so. Is it worth the effort? Your choice, since I won't write it for you, and given the existence of a fairly efficient scheme that uses a loop, why bother? Don't pre-optimize code.

MATLAB: How to generate all possible permutations without using the function perms/randperm

Using random permutations to try to generate all possible permutations is simply insane. Sorry, but you will never be happy with that approach. Even for small sets of elements this will be terribly inefficient.

You can simply generate all possible permutations using a recursive scheme, given a vector v of elements, where v is not too long. For a vector of length n, there will be factorial(n) permutations, so if n is greater than about 10 or so, ANY scheme will take some effort.

function P = myperms(v)
% simple recursive scheme to generate all permutations of a vector v.
n = numel(v);
if n <= 1
  P = v;
else
  P = zeros(factorial(n),n);
  f = factorial(n-1);
  L = 1:f;
  for ii = n:-1:1
    P(L,1) = v(ii);
    P(L,2:n) = myperms(v(setdiff(1:n,ii)));
    L = L + f;
  end
end

As you can see, it works.

myperms([2 3 5])
ans =
     5     3     2
     5     2     3
     3     5     2
     3     2     5
     2     5     3
     2     3     5
perms([2 3 5])
ans =
     5     3     2
     5     2     3
     3     5     2
     3     2     5
     2     5     3
     2     3     5

Same set of permutations, even in the same order.

Best Answer

Related Solutions

MATLAB: All combinations of two elements from a 3 by 7 matrix without repeating from the same column

MATLAB: How to generate all possible permutations without using the function perms/randperm

Related Question