All possible permutation of a given vector.

Given a vector, e.g [1 2 3 4 1], I would like to obtain all the possible permutations with NO REPETITION and NO ROTATION.

With

v = [1 2 3 4 1];
P =  unique(perms(v),'rows');

I can avoid repetition but no rotation.

With rotation I mean that [1 2 1 4 3] and [2 1 4 3 1] are the same vector because the sequence is the same, just view from a different initial position.

I would like to be able to obtain all the possible combinations that avoid also this fact (rotation).

Thanks

[Rik]

I suspect there are two options:

1. looping through your array (from end to beginning) and remove all rotations (use circshift)
2. design your own implementation of perms that avoids rotations

Neither is likely to be fast, and the first will also require the generation of a very large array for slightly larger vectors.

Answer 1

[Stephen23]

V = [1,2,3,4,1];
N = numel(V);
% Permutations:
P = perms(V(2:N));
P(:,N) = V(1);
P = unique(P,'rows')
% Rotations:
R = P; % just to allow comparison.
X = hankel(2:N,[N,1:N-1]);
for k = size(R,1):-1:1
	T = R(k,:);
	if any(ismember(T(X),R,'rows'))
		R(k,:) = [];
	end
end

Giving a 12x5 matrix:

R =
  1  2  3  4  1
  1  2  4  3  1
  1  3  2  4  1
  1  3  4  2  1
  1  4  2  3  1
  1  4  3  2  1
  2  1  3  4  1
  2  1  4  3  1
  2  3  1  4  1
  2  4  1  3  1
  3  1  4  2  1
  3  2  1  4  1

See also:

https://en.wikipedia.org/wiki/Necklace_(combinatorics)

[luca]

thanks for helping me !