Chinaunix

标题: 请教个排列算法 [打印本页]

---

作者: c/unix    时间: 2014-03-17 08:59
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: bruceteen    时间: 2014-03-17 11:09
假设有 n 行，各行分别有 a1、a2、a3 …… an 个数据
for( 整型 i=0; i!=a1*a2*a3……*an; ++i )
{
       第一行取第 i / (a2*a3……*an) 个数据
       第二行取第 i % (a2*a3……*an)/(a3……*an) 个数据
       ……
}
这样比较简单，但如果 a1*a2*a3……*an 太大的话，没有这样的内置整型能容纳下

另一种，就是自己做个栈
{第一行当前索引，第一行最大索引}
{第二行当前索引，第二行最大索引}
……

---

作者: selfrun    时间: 2014-03-17 11:20
1、用递归
2、模拟递归，作个长度等于行数的整数数组，每个数组元素是对应行的循环计数。

---

作者: selfrun    时间: 2014-03-17 11:20
1、用递归
2、模拟递归，作个长度等于行数的整数数组，每个数组元素是对应行的循环计数。

---

作者: bruceteen    时间: 2014-03-17 12:07
吃饭回来，瞎写的，给你参考一下

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     // 输入
   
8.     vector< vector<int> > buf;
   
9.     {
   
10.         vector<int> tmp;
    
11.         tmp.push_back( 1 );
    
12.         tmp.push_back( 2 );
    
13.         buf.push_back( tmp );
    
14. 
    
15.         tmp.clear();
    
16.         tmp.push_back( 44 );
    
17.         tmp.push_back( 55 );
    
18.         tmp.push_back( 66 );
    
19.         buf.push_back( tmp );
    
20. 
    
21.         tmp.clear();
    
22.         tmp.push_back( 88 );
    
23.         tmp.push_back( 99 );
    
24.         buf.push_back( tmp );
    
25.     }
    
26. 
    
27.     // 输出
    
28.     if( !buf.empty() )
    
29.     {
    
30.         vector<size_t> pro( buf.size(), 0 );
    
31. 
    
32.         for( ; pro.front() != buf.front().size(); )
    
33.         {
    
34.             for( size_t i=0; i!=pro.size(); ++i )
    
35.                 cout << buf[i][pro[i]] << ' ';
    
36.             cout << '\n';
    
37. 
    
38.             // next
    
39.             for( size_t i=pro.size(); i!=0; --i )
    
40.             {
    
41.                 if( pro[i-1]+1!=buf[i-1].size() || i-1==0 )
    
42.                 {
    
43.                     ++pro[i-1];
    
44.                     break;
    
45.                 }
    
46.                 else if( i-1 != 0 )
    
47.                 {
    
48.                     pro[i-1] = 0;
    
49.                 }
    
50.             }
    
51.         }
    
52.     }
    
53. 
    
54.     return 0;
    
55. }

复制代码

---

作者: c/unix    时间: 2014-03-17 12:27
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: folklore    时间: 2014-03-17 14:29
这个好办，　两个Loop就好了
原始数据：
1 2
44 555 66
88 9
有三行数据，设一个长度为两３的数组：
一个表示长度：　２　３　２
一个表示当前计数
０　０　０
当前计数加1，直到 121为止～
算法如下：

1. #include <vector>
   
2. #include <stdio.h>
   
3. void permulation_next(const std::vector<std::vector<int>>& meta, std::vector<int>& ic){
   
4.         // +1
   
5.         int icarry =1;
   
6.         for(size_t irow =0; irow <meta.size(); irow++){
   
7.                 int iv =icarry +ic[irow];
   
8.                 ic[irow] =iv;
   
9.                 if(iv ==(int)meta[irow].size()){
   
10.                         icarry =1;
    
11.                         ic[irow] =0;
    
12.                 }else{
    
13.                         icarry =0;
    
14.                         break;
    
15.                 }
    
16.         }
    
17. }
    
18. 
    
19. int main(){
    
20.         int params[][3]={
    
21.                 {1,2,},
    
22.                 {44, 555, 66,},
    
23.                 {88, 9,},
    
24.         };
    
25.         int nlen[] ={2,3,2};
    
26. 
    
27.         std::vector<std::vector<int>> meta;
    
28.         for(int irow =0; irow <_countof(params); irow ++){
    
29.                 std::vector<int> rows;
    
30.                 for(int iitem =0; iitem <nlen[irow]; iitem++){
    
31.                         rows.push_back(params[irow][iitem]);
    
32.                 }
    
33.                 meta.push_back(rows);
    
34.         }
    
35. 
    
36.         std::vector<int> ic;
    
37.         int nloops =1;
    
38.         for(int irow =0; irow <_countof(params); irow++){
    
39.                 ic.push_back(0);
    
40.                 nloops *=nlen[irow];
    
41.         }
    
42. 
    
43.         for(int iloop =0; iloop <nloops; iloop++){
    
44.                 for(size_t irs =0; irs <ic.size(); irs++){
    
45.                         printf("%d ",meta[irs][ic[irs]]);
    
46.                 }
    
47.                 puts(" --");
    
48.                 permulation_next(meta,ic);
    
49.         }
    
50. 
    
51.         return 0;
    
52. }

复制代码

---

作者: folklore    时间: 2014-03-17 14:33
回复 5# bruceteen
**nb,8741

   

---

作者: BlueGuy_    时间: 2014-03-18 00:39
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: BlueGuy_    时间: 2014-03-18 00:45
提示: 作者被禁止或删除 内容自动屏蔽

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2