全遍历向量的生成问题

rocwoods

由bainhome那个循环素数问题构造1379全部序列想到的。简单说就是一个n位向量I，每一位可以取的值分别由A1-An这n个向量决定。问，如何构造全部的I?
马上端午假期了，祝版里的兄弟节日快乐！

rocwoods

我先来一个，抛砖引玉：

1. n = 4;a = [1 3 7 9];
   
2. A = repmat({a},1,n);
   
3. [B{n:-1:1}] = ndgrid(A{:});
   
4. cell2mat(cellfun(@(x) x(:),B,'uni',0))

复制代码

bainhome

这是一个很好的例子，还略微有些类似上次那个盒子放球球的问题。大致意思不知道是不是对向量a中的元素做n重可重复组合。
例如当

1. n=2;a=[1 2]

复制代码

时有：

1. ans =
   
2.      1     1
   
3.      1     2
   
4.      2     1
   
5.      2     2

复制代码

再比如

1. n=2,a=[1 3 5]

复制代码

有：

1. ans =
   
2.      1     1
   
3.      1     3
   
4.      1     5
   
5.      3     1
   
6.      3     3
   
7.      3     5
   
8.      5     1
   
9.      5     3
   
10.      5     5

复制代码

这个问题感觉类似完全析因设计(DOE)的泛化，这个模型在实际中是有意义的，例如前一段时间粗看过系统可靠度分析中的布尔真值法(状态穷举)，算法和这个模型构造的思路有些像，只是系统的n个单元其状态只有0和1两种，且做好序列统计还要计算可靠度而已，哪天我把模型细节发上来，集思广益讨论个MATLAB实现的最简版——至少有教学意义，呵呵。
lin2009兄在这里提到了fullfact命令的费解，我借本帖补充两句：
这个fullfact命令实际上就是用于完全析因分析的析因组合过程，例如最常见的例子是机床加工部件，产品性能的离散性可以由机床造成、也有可能由操作者造成，但如果总是同一个操作员操作同一台机床则原因难以分析，因此需要允许每个操作员遍历各台机床来区分差别：
4个操作员+3台机床：

1. x=fullfact([4 3])
   
2. x =
   
3.      1     1
   
4.      2     1
   
5.      3     1
   
6.      4     1
   
7.      1     2
   
8.      2     2
   
9.      3     2
   
10.      4     2
    
11.      1     3
    
12.      2     3
    
13.      3     3
    
14.      4     3

复制代码

例子来自以前的一本MATLAB学工程数学的教材，由于大家练cody，无论简洁性还是效率，其重点只能放在MATLAB上，加上各位都是熟练工，所以有时候好多命令都被拿来歪着用，使得其他人看的时候忘记了函数本身的含义，造成一些误解。所以多解释一下。
大家继续讨论本帖吧，这个模型还是很有意思的。

nwcwww

贴个regexp的，还是用之前的1379：

1. n = 4;
   
2. regexp(num2str(10^(n-1):10^n),'\<[1379]+\>','match'); %符合条件的整数
   
3. reshape([ans{:}], [n, numel(ans)])'-'0'; %从cell中取出字符串,整理并转化格式

复制代码

qibbxxt

来自于神经网络工具箱的一个函数combvec

1. c = [1,3,7,9];
   
2. n = 4;
   
3. d = repmat({c},1,n);
   
4. combvec(d{:})

复制代码

qibbxxt

1. c = [1,3,7,9];
   
2. n = 4;
   
3. c(dec2base(0:length(c)^n-1,length(c),n) - '/')

复制代码

liuyalong008

来个平淡无奇的常规做法：

1. n=4
   
2. m=reshape(sprintf(['%',n+48,'d'],(1:10^n-1)'),n,[])';
   
3. m((sum(m=='1'|m=='3'|m=='7'|m=='9',2)==n),:)

复制代码

lin2009

更基础的问题：

% 没安装fullfact对应的工具箱。(答复3#bainhome )
% 猜测fullfact函数没有实现“全遍历向量的生成问题”的功能，否则本帖无存在的必要。（必要的废话）

请大家参照3#描述的fullfact函数的功能，编写myfullfact函数。
该函数在实现“全遍历向量的生成问题”的基础上，能将之应用范围推广到更一般的情况。

% 函数功能描述：产生符合以下条件的所有组合：
% 输出n位数，每一位数的取值范围（对应于输入的各个参数）均可单独设定。
% 如4位数，【x,y,z,w】第一位为x，第二位为y,...，x,y,z,w 的取值范围可单独设定。
% 输出位数的由输入参数的个数决定。
% 在各位数的最小值均为1的情况下，也可以仅输入各位数的最大值。

调用形式：
[myperms,nums] = myfullfact([1:3],[2:6],[4,5],[2,4,6,7]) % nums为组合数，myperms为（nums x n）的数组。
myperms = myfullfact([1:3],[2:6],[4,5],[2,4,6,7])

调用形式：（输入参数全为标量时，调用形式与Matlab中的fullfact函数稍微有些不同）
[myperms,nums] = myfullfact(3,4)
myperms = myfullfact(3,4)
等同于
[myperms,nums] = myfullfact([1:3],[1:4])
myperms = myfullfact([1:3],[1:4])

n位全遍历向量的调用形式：
vscp = [1,3,7,9];  % vscp is the digit's scope in the particular position.
[myperms,nums] = myfullfact(vscp,vscp,vscp,vscp) % n = 4,为输入参数的个数
myperms = myfullfact(vscp,vscp,vscp,vscp)            % n = 4,为输入参数的个数

qibbxxt

lin2009 发表于 2013-6-16 00:54
更基础的问题：

% 没安装fullfact对应的工具箱。(答复3#bainhome )

捧个场，其实我上面已经写过这个函数了，combvec

1. function [myperms,nums] = myfullfact(varargin)
   
2. myperms = combvec(varargin{:});
   
3. nums = length(myperms);
   
4. end

复制代码

liuyalong008

lin2009 发表于 2013-6-16 00:54
更基础的问题：

% 没安装fullfact对应的工具箱。(答复3#bainhome )

狗尾续貂一个，不过没有解决标量的问题

1. function [ans,nums] = myfullfact_0(varargin)
   
2. % myfullfact_0([1:3],[2:6],[4,5],[2,4,6,7])
   
3. %
   
4. L=cellfun(@length,varargin);
   
5. nums=prod(L);
   
6. L1=[1 cumprod(L(1:end-1))];
   
7. L2=[nums./L1(2:end) 1];
   
8. cell2mat(arrayfun(@(i)reshape(repmat(varargin{i},L1(i),L2(i)),nums,[]),1:numel(varargin),'Unif',0))';
   
9. end

复制代码

winner245

好方法真多啊！我也来提供一个偏方，基本原理类似于matlab中不同进制的转换：

1. n = 4; a = [1 3 7 9];
   
2. d = [0:n^n-1].';
   
3. a(rem(floor(d*n.^[1-n:0]),n)+1)

复制代码

winner245

rocwoods 发表于 2013-6-9 17:15
我先来一个，抛砖引玉：

最近做一个Cody题，用到了全遍历算法，自然联想到了吴兄的这个讨论，后来采用了类似吴兄的算法，但在简化代码的时候发现这里的 cellfun 可以写成向量化的形式：

n = 4;a = [1 3 7 9];
[B{n:-1:1}] = ndgrid(a);
reshape(cat(n,B{:}),[],n)