CODEWITHSUNDEEP
matlabpermutation
130wde
130wde

Reputation: 49

Generating permutations of a set with controlled output?

Is there an easy way to get the first x permutations of a set?

For example a set with 5 characters {a,b,c,d,e} will have

5*5*5*5*5= 3125 permutations output

(repetition is allowed e.g. {a,a,a,a,a})

But I would like to have only the first 100 values for example

Upvotes: 2

Views: 464

Answers (4)

Bas Swinckels
Bas Swinckels

Reputation: 18488

One way to generate all 'permutations' one at the time in lexicographical order, without having to store them all in memory:

function permute_chars(alphabet, nword, nmax)

if nargin < 3  % default to displaying all, this can be a huge number!
    nmax = nchar^nword;
end

nchar = length(alphabet);
ind = zeros(1, nword);
i = 0;

while i < nmax
    % just printing the permutaions, edit according to your needs
    disp(cell2mat(alphabet(ind + 1))); 

    % calculate next indices, classic elementary school addition with carry
    ind(end) = ind(end) + 1;
    for j = nword:-1:2
        if ind(j) == nchar 
            ind(j) = 0;  % wrap around
            ind(j-1) = ind(j-1) + 1;  % carry
        end
    end     
    i = i + 1;
end

For sure I am forgetting some obscure function which would allow to implement this in fewer lines, but written like this it is clear how it works. Quick test:

>> alphabet = {'a', 'b', 'c', 'd', 'e'};
>> permute_chars(alphabet, 1)
a
b
c
d
e
>> permute_chars(alphabet, 2)
aa
ab
ac
ad
ae
ba
[... snip ...]
ed
ee

Printing only a limited amount of permutations:

>> permute_chars(alphabet, 5, 8)
aaaaa
aaaab
aaaac
aaaad
aaaae
aaaba
aaabb
aaabc

Upvotes: 2

beaker
beaker

Reputation: 16811

For a bit more flexibility in which range of permutations you get, you can use a function that, given a permutation, produces the next permutation in the series. In this implementation I've chosen to have the permutations wrap back around to the first, even if the input permutation is out of range.

function newperm = nextPerm(oldperm, base)
   if any(oldperm >= base)
      newperm = zeros(1,numel(oldperm));
      return
   end
   idx = numel(oldperm);
   newperm = oldperm;
   while idx > 0
      newperm(idx) = newperm(idx) + 1;
      if newperm(idx) < base
         return;
      end
      newperm(idx) = 0;
      idx = idx - 1;
   end
end

Permutation elements are 0-based (so max element is base-1). 

p = [4 4 4 4 4]
nextPerm(p, 5)
ans =

   0   0   0   0   0

p = [0 0 0 0 0]
nextPerm(p, 5)
ans =

   0   0   0   0   1

p = [3 4 1 0 2]
nextPerm(p, 5)
ans =

   3   4   1   0   3

p = [3 4 5 0 2] %// invalid value '5'
nextPerm(p, 5)
ans =

   0   0   0   0   0

To get a range, just feed it through a loop:

myPerms = zeros(5);
myPerms(1,:) = [3 1 2 0 4];
for k = 2:5
   myPerms(k,:) = nextPerm(myPerms(k-1,:), size(myPerms,1));
end

myPerms =

   3   1   2   0   4
   3   1   2   1   0
   3   1   2   1   1
   3   1   2   1   2
   3   1   2   1   3

To map the permutation to your alphabet, just add 1 to the vector and use it as an index:

alphabet = ['a', 'b', 'c', 'd', 'e'];
word = alphabet(myPerms(1,:)+1)

word = dbcae

Upvotes: 1

nkjt
nkjt

Reputation: 7817

To select 100 random unique samples from numbers 1:n, with repetitions allowed (sampling with replacement), you can use randi or similar to create a list of a bit more than 100 x n random samples, unique them to remove duplicates, and then take the first 100.

For example, using randi:

% from numbers 1:n, create 200 by n random matrix
sample_list = randi(n,[200, n]);
% remove duplicates
sample_list = unique(sample_list,'rows'); 
% you should probably error check here
% presuming there's >100 options left, take 100 of them
sample_list = sample_list(1:100,:);

sample_list will be a numeric matrix, but you can easily use it as an index into other things if needed:

my_set = {'a','b','c','d','e'}; % 1 x 5 cell
my_permutes = my_set(sample_list); % 100 x 5 cell

This avoids having to calculate every single possible option, which for larger n would become problematic.

Upvotes: 1

cwissy
cwissy

Reputation: 513

You can use P = perms(S) to get all the permutations of set S, and then if you wanted 100 you could do P(1:100,:).

For random you could use P(randperm(size(P,1),100),:).

If you know need to be more specific about the permutations, then you can use permute with an order parameter - http://uk.mathworks.com/help/matlab/ref/permute.html

Upvotes: 2

Related Questions