1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
% pick Picking elements from a set (combinations, permutations)
%
% s = pick(V,k,Type)
%
% Gives all possibilities of picking k elements from the
% set V with or without order and repetition. V can be an
% array of any size and any type.
%
% Type can have the following values: '', 'o', 'r', 'or'.
% 'o' means pick ordered set of k elements
% 'r' means replace elements after picking
%
% s is an array with all picks, one subset per row.
%
% Examples
% pick(1:2,5,'or')
% pick('abcd',2,'')
% pick(-1:1,4,'r')
% pick('X':'Z',3,'o')
% Stefan Stoll, ETH Zurich, 20 October 2006
function s = pick(V,k,Type)
errThirdMissing = 'Third argument Type ('''', ''o'', ''r'', or ''or'') is missing!';
errThreeExpected = 'Three arguments (V, k, Type) must be provided.';
switch nargin
case 3,
case 2, error(errThirdMissing);
case 1,
if strcmp(V,'test');
pick_test;
return;
else
error(errThreeExpected);
end
case 0, help(mfilename); return;
otherwise, error(errThreeExpected);
end
N = numel(V);
if (N==0)
error('First argument V must be an array with at least one element.');
end
if (numel(k)~=1) || rem(k,1) || (k<1)
k
error('Second argument k must be a positive integer. You gave the above.');
end
if ~ischar(Type)
Type
error('Third argument must be a string.');
end
if isempty(strfind(Type,'r')) && (k>N)
str = sprintf('Picking elements without repetition:\n k must not be larger than the number of elements in V.\n');
error([str 'You gave k=%d for %d elements in V.'],k,N);
end
switch sort(Type)
case '', idx = combinations_without_repetition(N,k);
case 'o', idx = permutations_without_repetition(N,k);
case 'r', idx = combinations_with_repetition(N,k);
case 'or', idx = permutations_with_repetition(N,k);
otherwise
Type
error('Third argument Type must be one of '''', ''o'', ''r'', ''or''.');
end
s = V(idx);
if (k==1), s = s(:); end
return
%=====================================================================
function m = combinations_with_repetition(N,k)
if (k==1), m = (1:N).'; return; end
if (N==1), m = ones(1,k); return; end
m = [];
for q = 1:N
mnext = combinations_with_repetition(N+1-q,k-1);
m = [m; q*ones(size(mnext,1),1), mnext+q-1];
end
%===================================================================
function p = permutations_without_repetition(N,k)
p = permutations_with_repetition(N,k);
ps = sort(p.').';
idx = any(ps(:,2:end)==ps(:,1:end-1),2);
p(idx,:) = [];
%===================================================================
function s = permutations_with_repetition(N,k)
if (k==1), s = (1:N).'; return; end
if (N==1), s = ones(1,k); return; end
[idx{1:k}] = ndgrid(1:N);
s = fliplr(reshape(cat(ndims(idx{1}),idx{:}),[],k));
%===================================================================
function c = combinations_without_repetition(N,k)
if (N>1)
c = nchoosek(1:N,k);
else
c = 1;
end
%===================================================================
function pick_test
disp('=========== pick() tests ======================');
Nmax = 6;
Type = {'','o','r','or'};
Name{1} = 'Combinations without repetition';
Name{2} = 'Permutations without repetition';
Name{3} = 'Combinations with repetition';
Name{4} = 'Permutations with repetition';
Repetition = [0 0 1 1];
for t = 1:4
disp(' ');
disp(Name{t});
for N = 1:Nmax
if Repetition(t), kmax = Nmax; else kmax = N; end
for k = 1:kmax
s = pick(uint8(1:N),k,Type{t});
m1 = size(s,1); k1 = size(s,2);
switch t
case 1, m = nchoosek(N,k);
case 2, m = prod(N-k+1:N);
case 3, m = nchoosek(N+k-1,k);
case 4, m = N^k;
end
fprintf(' N=%d, k=%d, expected %dx%d, found %dx%d\n',N,k,m,k,m1,k1);
if (m1~=m) | (k1~=k)
error('Unexpected size of output array!');
end
end
end
end
disp('All tests passed!');
|
