请教一个排列问题

yanice

从n个不同的球中拿球，拿完后放回，拿m次，列出所有的可能情况

拿法应该一共有n^m种，如何用Matlab实现？

[ 本帖最后由 ChaChing 于 2010-1-6 08:26 编辑 ]

ChaChing

水平专业有限, 不太确定LZ要什么?
建议楼主举例说清楚些

yanice

比如有【1，2，3】三个数，可能的排列有，每次从上面三个数中拿一个出来，一共拿4次，组成一个数列例如【1 2 3 1】
【1 1 2 1】
【1 2 3 2】
等

[ 本帖最后由 friendchj 于 2010-1-7 02:13 编辑 ]

ChaChing

好像没现成的函数可用!
一时想不出好法子, 但m不大时, 使用for loop应该也能执行!
待高人路过

ChaChing

刚搜了下官网, 这个应该适用!
http://www.mathworks.com/matlabc ... ge/26242-vchoosekro
or
http://www.mathworks.com/matlabcentral/fileexchange/12724-picking-elements-from-a-set

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

复制代码

[ 本帖最后由 ChaChing 于 2010-1-6 10:22 编辑 ]